patternMinor
Why can $2$-SAT be solvable efficiently, but $3$-SAT not?
Viewed 0 times
satwhyefficientlycanbutsolvablenot
Problem
I am aware that 2SAT is polynomial while 3SAT is not, but I am looking for an intuition why its so. After all, even in 2SAT we can attempt all possible truth functions and its $2^n$. So I am hoping not for a formal proof, but for intuition or explanations that distinguishes the language from 3SAT?
Solution
As was mentioned in a comment we can only say that 3SAT is NP-hard. In 2SAT you can take a variable $x$ and set it to true (or false). Then you can throw out any clauses where $x$ appears, or if a clause becomes unsatisfiable from previous assignments you know that $x$ cannot be true (or false). By proceeding in this manner we can efficiently obtain a satisfying formula or verify that the clauses are not all simultaneously satisfiable.
If you try to extend this intuition to 3SAT and set the truth value of $x$ then you will end up still having to check an exponential number of clauses before shrinking the problem size. This doesn't show that 3SAT is not polynomial-time solvable but it does show that the obvious approach for solving 2SAT fails when extended to 3SAT.
If you try to extend this intuition to 3SAT and set the truth value of $x$ then you will end up still having to check an exponential number of clauses before shrinking the problem size. This doesn't show that 3SAT is not polynomial-time solvable but it does show that the obvious approach for solving 2SAT fails when extended to 3SAT.
Context
StackExchange Computer Science Q#145822, answer score: 5
Revisions (0)
No revisions yet.