394. Why is 2-SAT solvable in polynomial time while 3-SAT is NP-complete?
HardComplexity classes
Show model answer
Each 2-SAT clause (a ∨ b) is equivalent to two implications ¬a → b and ¬b → a. Build an implication graph on 2n literals and find strongly connected components (Tarjan or Kosaraju). The formula is unsatisfiable exactly when some variable x and ¬x lie in the same component; otherwise assign values in reverse topological order of components. That is O(n + m) for n variables and m clauses.
With three literals per clause, a clause no longer forces a single implication, and the chain-of-implications structure disappears. 3-SAT is NP-complete (every SAT formula reduces to 3-SAT by splitting long clauses with fresh variables). Max-2-SAT, maximising satisfied 2-clauses, is also NP-hard, so the boundary is subtle.