Skip to interview prep
Apexed

394. Why is 2-SAT solvable in polynomial time while 3-SAT is NP-complete?

HardComplexity classes

Technical
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.

Why is 2-SAT solvable in polynomial time while 3-SAT is NP-complete — Data structures & algorithms interview question — Apexed