HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Why can $2$-SAT be solvable efficiently, but $3$-SAT not?

Submitted by: @import:stackexchange-cs··
0
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.

Context

StackExchange Computer Science Q#145822, answer score: 5

Revisions (0)

No revisions yet.