A computer scientist claims: 'The Cook-Levin theorem proves that SAT cannot be solved efficiently — it shows SAT requires exponential time.' Why is this claim incorrect?
AThe theorem only applies to 3-SAT, not general SAT, so the claim is about the wrong problem
BThe theorem proves SAT is NP-complete — that it is in NP and NP-hard — but does not prove SAT has no polynomial-time algorithm; if such an algorithm exists, it would imply P = NP
CThe theorem proves SAT requires exponential time only on nondeterministic machines, not deterministic ones
DThe theorem proves SAT is hard in practice but allows for polynomial algorithms on structured instances
NP-completeness is not a lower bound proof. It says SAT is NP-hard (every NP problem reduces to it) and in NP (solutions can be verified in polynomial time). Whether SAT can be solved in polynomial time is exactly the P vs. NP question — still open. If a polynomial algorithm for SAT were found, it would solve every NP problem in polynomial time (proving P = NP). Cook-Levin establishes universality, not intractability.
Question 2 Multiple Choice
After Cook-Levin proved SAT is NP-complete, Karp showed the Clique problem reduces to SAT in polynomial time. What does this reduction establish about Clique?
AClique is harder than SAT, since it requires an extra encoding step
BClique is NP-complete: it is in NP, and because every NP problem reduces to SAT which reduces to Clique, Clique is NP-hard
CClique is in P, since polynomial reductions preserve polynomial-time solvability in both directions
DClique is equivalent to SAT only for graphs with specific structure
A polynomial-time reduction from SAT to Clique means that any SAT instance can be converted to a Clique instance in polynomial time. Since every NP problem already reduces to SAT (by Cook-Levin), every NP problem now reduces to Clique through the chain. Clique is also in NP (a clique of size k can be verified in polynomial time by checking all edges). Therefore Clique is NP-complete. The cascade of reductions — each far simpler than Cook-Levin — is the key payoff of establishing the first NP-complete problem.
Question 3 True / False
The Cook-Levin tableau construction directly proves that 3-SAT (where nearly every clause has exactly three literals) is NP-complete.
TTrue
FFalse
Answer: False
The tableau construction proves that general SAT is NP-complete. To show 3-SAT is NP-complete, a separate polynomial-time reduction from SAT to 3-SAT is needed — one that introduces auxiliary Boolean variables to break long clauses into groups of exactly three literals. This reduction is relatively straightforward but is a distinct step. Cook-Levin does the heavy lifting for SAT; the SAT-to-3-SAT reduction handles the rest.
Question 4 True / False
If a polynomial-time algorithm for SAT were discovered tomorrow, every problem in NP would also be solvable in polynomial time.
TTrue
FFalse
Answer: True
This is the direct implication of SAT being NP-hard. Since every NP problem can be reduced to SAT in polynomial time (Cook-Levin's proof), a polynomial-time SAT solver could be composed with each of these reductions to solve any NP problem in polynomial time. The discovery would prove P = NP, one of the most consequential open problems in mathematics.
Question 5 Short Answer
Explain the unique challenge the Cook-Levin proof faces compared to subsequent NP-completeness proofs, and describe at a high level how the tableau construction addresses it.
Think about your answer, then reveal below.
Model answer: Subsequent NP-completeness proofs work by reducing from a known NP-complete problem — they can simply invoke Cook-Levin. But Cook-Levin cannot do this because it establishes the first NP-complete problem; no prior NP-complete problem exists to reduce from. Instead, the proof must work directly from the definition of NP. The tableau construction does this by encoding an arbitrary nondeterministic Turing machine computation as a Boolean formula: variables represent every cell in a 2D grid of configurations, and CNF clauses enforce that the initial configuration is correct, each step follows from valid transition rules, and the machine accepts. The formula is satisfiable if and only if the machine accepts, so SAT can express any NP computation.
The circularity of 'reduce from NP-complete to prove NP-complete' is broken by going directly to the definition. An NP computation is a polynomial-time nondeterministic TM accepting an input. The computation history fits in a polynomial-size tableau. Encoding that tableau as Boolean variables and writing clauses that enforce consistency is the key idea — and it works for every NP problem simultaneously, making SAT the universal NP problem.