A software engineer's SAT solver successfully handles one million real-world industrial SAT instances per day with 100% success. She argues this demonstrates P = NP. What is the critical flaw in this reasoning?
ASAT is not NP-complete, so solving it efficiently does not imply P = NP
BPractical performance on real-world instances does not establish polynomial worst-case complexity — structured instances that yield to heuristics are not the adversarial inputs that determine complexity
CHer solver uses randomization, which places it outside the deterministic polynomial class P
DNP-completeness requires solving all instances simultaneously, not one at a time
Complexity classes are defined by worst-case behavior. A SAT solver can be extraordinarily fast on structured, real-world instances — exploiting unit propagation, conflict-driven clause learning, and clever branching — while still requiring exponential time on carefully constructed adversarial inputs. Proving P = NP requires an algorithm that solves every SAT instance in polynomial time bounded by a polynomial in the input size, without exception. The practical tractability of real-world SAT is an empirical observation about the structure of instances that appear in practice, not a complexity-theoretic result.
Question 2 Multiple Choice
The Cook-Levin theorem establishes that SAT is NP-complete. The most important consequence of this result is:
ASAT requires exponential time on all inputs, confirming P ≠ NP
BEvery problem in NP can be transformed into a SAT instance in polynomial time, so a polynomial-time SAT algorithm would solve all of NP in polynomial time
CSAT is harder than all other NP-hard problems, making it uniquely difficult
DSAT-solvers are always as efficient as any other algorithm for NP problems
NP-completeness combines two facts: (1) SAT ∈ NP (a satisfying assignment can be verified in linear time), and (2) every problem in NP is polynomial-time reducible to SAT. Together, these mean that if SAT could be solved in polynomial time, every NP problem could be solved in polynomial time (P = NP). Cook-Levin does NOT prove SAT requires exponential time — it establishes SAT as the universal representative of NP hardness. The P vs. NP question remains open precisely because no polynomial SAT algorithm has been found, but none has been ruled out.
Question 3 True / False
Because each assignment to n Boolean variables can be checked in linear time, SAT can be solved in polynomial time.
TTrue
FFalse
Answer: False
This confuses verification with solving — the core distinction in NP theory. Verifying a *given* assignment takes O(n) time: evaluate each clause under the proposed truth values. But *finding* a satisfying assignment (or proving none exists) requires searching among 2^n possible assignments in the worst case. The ability to quickly verify a candidate solution is exactly what places SAT in NP. It says nothing about how quickly the solution can be found. This gap between easy verification and apparently hard search is the defining feature of NP-complete problems and the heart of the P vs. NP question.
Question 4 True / False
If a polynomial-time algorithm for SAT were discovered, it would prove that P = NP.
TTrue
FFalse
Answer: True
By Cook-Levin, every problem in NP can be reduced to SAT in polynomial time. If SAT ∈ P, then by composition of reductions, every NP problem could be solved in polynomial time: solve the SAT reduction in poly time, giving a poly-time algorithm for the original NP problem. Since P ⊆ NP always holds, this would give P = NP. A polynomial-time SAT algorithm would simultaneously unlock polynomial-time solutions to planning, scheduling, graph coloring, protein structure prediction, integer factoring, and every other NP problem.
Question 5 Short Answer
Why does the fact that SAT can be verified in linear time not imply that SAT can be solved in polynomial time?
Think about your answer, then reveal below.
Model answer: Verification is easy because we are given the answer — just evaluate the formula under the proposed assignment, checking each clause in linear time. Solving requires finding a satisfying assignment without being given one, which means searching a space of 2^n possible truth assignments. No algorithm is known that avoids worst-case exponential exploration of this space. The ability to verify quickly defines membership in NP; solving quickly would require SAT ∈ P. Whether P = NP — i.e., whether every problem with efficient verification also has efficient search — is the central open question in computer science.
The asymmetry between verification and search is the defining structural feature of NP-complete problems. For any specific satisfying assignment, checking it is trivial. The difficulty is that we don't know which of the 2^n assignments satisfies the formula, and eliminating candidates requires exponential work in the worst case. SAT-solvers use heuristics that short-circuit this search for structured instances, but they offer no polynomial worst-case guarantee — consistent with SAT remaining an open problem for worst-case polynomial solvability.