4.6.25 · D5Theory of Computation
Question bank — NP-completeness — Cook's theorem (SAT is NP-complete), reduction
Before we start, three words we lean on again and again — pinned here so nothing is used before it is meant:
True or false — justify
Every answer below is a full reason, never a bare "true/false".
TRUE or FALSE: If SAT could be solved in polynomial time, then every problem in NP could be too.
TRUE — because every NP reduces to SAT (Cook's theorem), and a poly reduction plus a poly SAT-solver compose into a poly solver for ; this would collapse P = NP.
TRUE or FALSE: NP-hard problems are all inside NP.
FALSE — NP-hard only means "at least as hard as everything in NP"; a problem can be much harder (e.g. undecidable) and still be NP-hard. Only NP-complete ones sit inside NP.
TRUE or FALSE: Every problem in P is also in NP.
TRUE — if you can solve it in poly time you can certainly verify a "yes" in poly time (ignore the certificate and just resolve it), so .
TRUE or FALSE: Showing proves is NP-hard.
FALSE — that direction shows is no harder than SAT (it puts in NP if SAT-checkable), the opposite of hardness. To prove hard you need (or any NP-complete problem into ).
TRUE or FALSE: The name "NP" means "not polynomial".
FALSE — NP = Nondeterministic Polynomial, i.e. verifiable in poly time given a guess (a Nondeterministic Turing machine accepts in poly time). Many NP problems are actually easy.
TRUE or FALSE: If and , then .
TRUE — reductions are transitive: compose the two poly-time maps and the composite is still poly-time, so hardness flows all the way through . This transitivity is the entire engine behind Karp's 21 NP-complete problems.
TRUE or FALSE: Once one NP-complete problem is known, proving others requires re-running Cook's tableau argument.
FALSE — that is the whole payoff of an anchor: you just reduce an already-known NP-complete problem to your new one, letting transitivity carry Cook's proof for free.
TRUE or FALSE: A satisfying assignment of corresponds to a legal accepting run of on .
TRUE — the clause groups force the truth values to spell a valid tableau that starts correctly, obeys transitions, and reaches the accept state.
TRUE or FALSE: If a problem is in NP but nobody has reduced an NP-complete problem to it, it must be in P.
FALSE — it might be NP-complete with the reduction simply not yet found, or it might live in the mysterious "NP-intermediate" gap (if P ≠ NP). Absence of a reduction proves nothing.
TRUE or FALSE: Independent Set, Vertex Cover, and Clique are essentially the same problem in disguise.
TRUE in the reduction sense — is an independent set in iff is a vertex cover, iff is a clique in the complement ; each reduces to the others by trivial poly-time rewrites, so they are all NP-complete together.
Spot the error
Each line states a flawed claim; the reveal names the flaw.
"Cook's formula is built in poly time, so SAT itself must be solvable in poly time."
The flaw: constructing a hard question fast is not answering it fast. Building is cheap; deciding whether is satisfiable is the hard part we never showed is easy.
"To prove Independent Set is NP-hard, reduce Independent Set to 3-SAT."
Wrong direction. That shows IS is no harder than 3-SAT. Hardness needs — map the known-hard problem INTO your new one.
"A reduction can be any computable map; size and time don't matter."
The flaw: an exponential-size map destroys the poly-time argument. The map must be poly-time (hence poly-size) or hardness does not transfer.
"SAT is in P because we can verify a given assignment quickly."
Verifying an assignment fast puts SAT in NP, not P. P would require finding a satisfying assignment (or proving none exists) fast, with no certificate handed to you.
"In the 3-SAT → Independent Set reduction, we set the target size to the number of variables."
Wrong quantity. Set , the number of clauses: we pick exactly one true literal per clause-triangle, so the independent set has one vertex per clause.
"The window in Cook's proof checks the whole tape at once."
No — the window is local. A Turing head only touches the cell under it and its neighbours per step, so legality is checked window-by-window; the AND of all local checks yields global legality, and locality is what keeps polynomial.
"Because P ⊆ NP, every NP problem is really just a P problem we haven't optimized yet."
The flaw assumes P = NP. That is famously open. does not imply equality; NP-complete problems are the frontier where we don't know.
Why questions
Why does SAT specifically make a good "anchor" (first NP-complete) problem?
Because a Boolean formula can directly encode the step-by-step operation of any NTM — computation itself is expressible in AND/OR/NOT — so every NP problem reduces to it, no problem-specific cleverness needed.
Why must the reduction run in polynomial time and not merely be computable?
If took exponential time or produced exponential output, composing it with a poly-time solver for would no longer give a poly-time solver for , so "as hard as" would not transfer in the P-vs-NP sense.
Why does a triangle per clause appear in the 3-SAT → Independent Set reduction?
A triangle lets an independent set choose at most one of its three vertices, mirroring "pick one literal to satisfy this clause"; forcing the set to include one vertex per triangle = satisfying every clause.
Why do we add edges between complementary literals ( and ) in that graph?
To forbid an independent set from picking both a variable's TRUE and FALSE literal, which would be a contradictory truth assignment; the edge makes them mutually exclusive.
Why is "SAT ∈ NP" the easy half of Cook's theorem?
Given an assignment as certificate, you just plug it in and evaluate in linear time — a trivial verifier. The deep half is NP-hardness: showing everything reduces to SAT.
Why does clause-splitting () preserve satisfiability?
The chain of fresh variables can be satisfied internally only when at least one original literal is TRUE; if all originals are FALSE, no assignment of the satisfies the whole chain — exactly the OR condition of the long clause.
Why isn't a fast SAT solver's mere existence enough to claim P = NP without reductions?
You also need each NP problem to map to SAT in poly time; the reductions (Cook's construction) are what convert "SAT is easy" into "everything in NP is easy". Both pieces are required.
Edge cases
What if a Boolean formula has NO variables (a constant like TRUE)?
It is a valid SAT instance: TRUE is trivially satisfiable, FALSE is trivially unsatisfiable. The empty-variable case still fits the definition — satisfiability is just "does some (possibly empty) assignment make it TRUE".
What if a 3-SAT clause has only 1 or 2 literals instead of 3?
Pad it: repeat an existing literal (e.g. becomes ). Duplicates don't change the clause's meaning, so the reduction to true 3-literal form preserves satisfiability.
What happens in Cook's tableau if accepts before step ?
The remaining rows simply copy the halted configuration forward (the machine "stalls"); permits this stationary window, and only needs the accept state to appear somewhere, so an early accept is still captured.
Is a problem trivially reducible to itself, i.e. is ?
Yes — the identity map is poly-time and preserves membership, so is reflexive. Combined with transitivity, is a preorder, which is why "hardness" behaves like an ordering.
Can a problem in P be NP-complete?
Only if P = NP. If P ≠ NP, no P problem is NP-complete, because NP-completeness would force every NP problem (including the presumed-hard ones) down into P. So this edge case is equivalent to the open question itself.
What if the target independent-set size exceeds the number of clauses ?
Then no independent set that large can exist under this construction (each triangle contributes at most one vertex, capping the set at ), so the reduced instance is a "no" — consistent, since we only ever ask for exactly .
Does reducing an unsatisfiable formula still produce a valid graph in the IS reduction?
Yes — the graph is always built the same way; unsatisfiability just means no independent set of size exists, faithfully mirroring the "no" answer. The map never inspects satisfiability, only structure.
Recall One-sentence self-test
Which direction proves hardness, and why? ::: Reduce a known NP-complete problem INTO your new one (), because that shows can answer questions about the famously-hard , so is at least as hard.