Cook-Levin proved satisfiability NP-complete without reducing from an earlier complete problem - why was there no alternative?
answer
- nothing was complete yet
- the first link is special
- one argument covers all of NP
- a verifier's run becomes a formula
- assignment plays the certificate
basics
~20 sA hardness proof normally transfers hardness from a problem already known complete, and at the time none existed. Cook-Levin therefore argued about every problem in NP at once, encoding an arbitrary verifier's computation directly as a Boolean formula.
solid answer
~40 sEvery later NP-completeness proof is a mapping from a problem already known complete into the new one, so the chain needs a first link that cannot be built that way. Cook-Levin builds it generically: take any language in NP, which by definition has a polynomial-time verifier that checks a short certificate; for a given input, write a Boolean formula whose variables describe the verifier's entire run on that input together with an unknown certificate, and whose clauses say `this run is legal and it accepts`. Satisfying assignments then correspond exactly to accepting certificates, so the input is a yes-instance precisely when the formula is satisfiable. Because the formula is emitted in polynomial time, every language in NP maps into satisfiability, which makes satisfiability NP-hard; satisfiability is itself in NP, so it is complete.
go deeper
Remember the headline: satisfiability was the first problem shown to be as hard as anything in NP, and the whole catalogue of hard problems leans on that one result.
Be able to explain the bootstrap. Later proofs map a known-complete problem into a new one, so the very first proof had no source to map from and had to quantify over every language in NP directly.
Show where the weight sits: the hardness half needs the generic encoding plus a mapping computable in polynomial time, while membership is the cheap half. Be ready to state clearly what the theorem does not claim.
Frame it as the reason hardness claims are cheap today - one expensive argument was paid for once. So when someone calls a problem hard, ask for the transformation they used, not the intuition behind it.
## The claim, stated precisely **NP** is the class of decision problems whose yes-instances have a short, quickly checkable proof. Formally, a language `L` is in NP when there is a **verifier** - a deterministic procedure `V(x, w)` running in time polynomial in the length of `x` - and a polynomial bound `p`, such that `x` is in `L` exactly when some **certificate** `w` with length at most `p(|x|)` makes `V(x, w)` accept. A problem `B` is **NP-hard** when *every* language `L` in NP has a mapping `f` computable in time polynomial in its input, with `x` in `L` if and only if `f(x)` in `B`. `B` is **NP-complete** when it is NP-hard *and* itself in NP. The Cook-Levin theorem says that **satisfiability of Boolean formulas is NP-complete**: given a formula in conjunctive normal form, deciding whether some assignment of true and false to its variables makes every clause true is as hard as anything in NP. ## Why the first proof cannot itself be a reduction Read the definition of NP-hard again and notice the quantifier: *every* language in NP. A later proof discharges that quantifier cheaply. To show a new problem `C` is NP-hard you exhibit one mapping from a problem `B` already known to be NP-hard into `C`; because polynomial-time mappings compose, every `L` in NP now reaches `C` by going through `B`. That is a single concrete transformation between two named problems, and it is why modern hardness arguments are short. In 1971 there was no such `B`. The quantifier had to be discharged the expensive way - by an argument that works for an arbitrary language in NP given nothing but the definition of the class. | | A later completeness proof | The first one | |---|---|---| | Starts from | one problem already complete | the bare definition of NP | | Quantifies over | nothing; composition does it | every language in NP at once | | Must build | one transformation between two problems | a formula scheme covering any verifier | | Rests on | the theorem below it | the model of computation itself | ## The shape of the direct argument 1. Take an arbitrary `L` in NP and fix its verifier `V` together with the polynomial time bound `t`. 2. Fix an input `x`. The question *is `x` in `L`?* is exactly *does some certificate `w` make `V(x, w)` accept within `t(|x|)` steps?* 3. Introduce Boolean variables that describe a whole **run** of `V` on `x` alongside an unknown `w` - every intermediate step, not merely the answer. 4. Emit clauses that are all satisfied exactly when those variables describe a legal run that accepts. 5. Observe that a satisfying assignment *is* an accepting run, whose certificate part spells a valid `w`, and that emitting the clauses is a mechanical walk over indices, so the construction runs in polynomial time. Steps 3 and 4 are the technical content of the theorem; step 5 is the part candidates forget, and it is what makes the whole thing a reduction rather than a restatement. ## Why Boolean satisfiability was the right target - A clause set is a **general language of constraints**: anything expressible as *these bits must relate like this* is a clause. - The requirements of one step of computation are **local**, and a clause is local by nature - it mentions a handful of variables and no more. - Conjunctive normal form is a **flat conjunction**, so independent requirements simply concatenate and the construction can emit them in one pass with no global bookkeeping. - Free variables supply the **existential quantifier for free**: *some assignment satisfies it* is precisely *some certificate exists*. ## What the theorem bought, and what it does not say The payoff is leverage. One expensive argument was paid for once; afterwards, showing a new problem NP-hard costs one transformation from something already in the catalogue. Almost every hardness claim made in practice is a short step resting on this single foundation, which is why the result is usually the first thing taught in the subject and the last thing anyone re-proves. Levin published an equivalent statement independently, phrased for search problems rather than decision problems, which is why the theorem carries two names. What it does **not** claim: - It does not say satisfiability is unsolvable, or that useful instances cannot be decided - only that a *general* polynomial method for it would be a general method for everything in NP. - It proves no exponential lower bound. Whether NP differs from P is open; completeness is a statement about *relative* difficulty. - It does not say every instance is hard. Hardness here is a worst-case property of a problem, not a promise about the inputs a system actually receives. - It does not make satisfiability special among hard problems in any way except one: it was first.
- What breaks if the formula cannot be written down in time polynomial in the input length?It stops being a polynomial-time reduction and proves nothing. A construction allowed unlimited time could simply decide the input itself and emit a trivially satisfiable or trivially unsatisfiable formula, transferring no difficulty at all. Cheapness of the mapping is exactly what forces the difficulty to stay in the target problem.
- Why is a single complete problem enough to launch a whole catalogue?Polynomial-time mappings compose. Once every language in NP maps into satisfiability, one further mapping from satisfiability into a new problem makes that problem NP-hard too, by going through the chain. The expensive generic argument runs once; every later proof is one concrete transformation between two named problems.
- Levin published an equivalent result independently - what was different in his formulation?He stated it for search problems rather than decision problems: given an instance, produce a witness, and he exhibited a universal search procedure that is essentially optimal. The content is the same - one problem standing in for all of them - which is why the theorem carries both names.
saying these in an interview costs you the question
- Thinks Cook-Levin reduced satisfiability to some already-hard problem.
- Says the theorem proves satisfiability requires exponential time.
- Believes the mapping runs from formulas into each NP problem.
- Treats membership in NP as the hard half of the proof.
- Assumes every satisfiability instance is therefore hard to solve.