A student reads about the Cook-Levin theorem and concludes: 'This proves SAT cannot be solved in polynomial time — we know it requires exponential time.' What is wrong with this conclusion?
ASAT actually has a polynomial-time algorithm discovered after Cook's paper
BCook-Levin proves SAT is NP-complete, but NP-completeness does not prove any problem requires superpolynomial time — whether P=NP remains open
CCook proved SAT is NP-hard but not that it is in NP, so NP-completeness does not follow from his result
DThe theorem only applies to 3-CNF satisfiability, not general SAT, so the conclusion overstates the result
This is the central misconception flagged in the topic's Common Misconceptions. NP-completeness means SAT is in NP and every NP problem reduces to SAT in polynomial time. It does NOT prove SAT is hard in an absolute sense. If P=NP (still unresolved after 50+ years), then SAT would have a polynomial-time algorithm and Cook-Levin would still be true. The theorem identifies SAT as the right problem to study to resolve P vs. NP — it does not resolve the question itself.
Question 2 Multiple Choice
What is the key technique by which the Cook-Levin proof shows that every NP problem reduces to SAT?
AEncoding the problem's input as a binary string that a SAT solver tests by guessing all possible assignments
BConstructing a tableau formula that encodes an accepting computation history of a polynomial-time NTM, where satisfying assignments correspond exactly to valid accepting computations
CUsing a diagonal argument to show SAT can simulate any NTM by parallel nondeterministic branching
DShowing that SAT's search space has the same cardinality as any NP problem's solution space
The tableau construction is the heart of the proof. For any NP problem with a poly-time NTM M and input w, the proof constructs a propositional formula φ_{M,w} using three families of variables: cell variables (what symbol is on each tape cell at each time step), head variables (head position), and state variables (machine state). Clauses enforce the initial configuration, valid transitions, and acceptance. The formula has size O(t²) — polynomial. It is satisfiable if and only if M accepts w. This works for ANY NP problem's NTM, so every NP problem reduces to SAT.
Question 3 True / False
If SAT were shown to have a polynomial-time algorithm, then every problem in NP could be solved in polynomial time.
TTrue
FFalse
Answer: True
This is precisely what NP-completeness means. Every NP problem reduces to SAT in polynomial time (Cook-Levin gives the reduction for an arbitrary NTM; subsequent reductions from SAT to other NP-complete problems complete the chain). A polynomial-time SAT solver, combined with these polynomial-time reductions, would give polynomial-time algorithms for all of NP — resolving P=NP in the affirmative.
Question 4 True / False
The Cook-Levin theorem proves that SAT cannot be solved in polynomial time.
TTrue
FFalse
Answer: False
Cook-Levin proves SAT is NP-complete: SAT is in NP, and every NP problem reduces to SAT. It says nothing about whether polynomial-time algorithms for SAT (and hence all of NP) exist. Whether P=NP — whether NP problems genuinely require superpolynomial time — is the most famous open problem in computer science. Cook-Levin identifies SAT as the pivotal problem; it does not answer the question.
Question 5 Short Answer
Describe the tableau construction in the Cook-Levin proof: what does the formula represent, and why does this construction demonstrate that every NP problem reduces to SAT?
Think about your answer, then reveal below.
Model answer: The tableau is a t×t grid where rows are time steps (1 through t) and columns are tape positions. Three families of variables describe the machine's configuration at each step: cell variables (symbol on each tape cell), head variables (head position), and state variables (current machine state). Clauses enforce: (1) the initial configuration matches the input w, (2) each transition follows the NTM's rules, (3) an accepting state is reached by step t. The formula is satisfiable iff M accepts w. Since this construction works for any polynomial-time NTM, every NP problem (which by definition has a poly-time NTM witness) reduces to SAT.
The formula size is O(t²) — polynomial — because the tableau has t rows and t columns, and each variable or clause is defined for each cell. The reduction itself runs in polynomial time, which is required for the reduction to be valid. The elegance of the proof is that it doesn't use any special property of SAT — it uses only the fact that SAT can express arbitrary boolean constraints. This is what makes SAT the 'universal' NP problem: computation itself can be encoded as a satisfiability question.