JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Proving New Problems Hard, and What P vs NP Means

Cook-Levin gave us one anchor of hardness; now we turn it into a tool you can wield. This guide is the practical recipe for proving your own problem NP-complete, a tour of the zoo of problems already known to be hard, and an honest look at what P versus NP would — and would not — change.

One hard problem becomes a crowbar

By the end of the last guide you had two things in hand. From the Cook-Levin theorem, a single problem — SAT — proven to be NP-complete from first principles, meaning it is both in NP and at least as hard as everything in NP. And from the reductions guide, the polynomial-time reduction, a way to say "problem B is at least as hard as problem A" by transforming any instance of A into an equivalent instance of B in polynomial time. This guide is about what happens when you put those two together: one proven-hard problem becomes a crowbar for prying open the hardness of thousands of others.

Here is the key chain of logic, and it is worth slowing down on, because every later proof is just this chain re-run. Suppose A is already known NP-complete, and you build a polynomial-time reduction from A to your new problem B. The reduction direction matters: a reduction from A to B shows B is at least as hard as A — A is the hard thing you are leaning on, B is the thing you are pushing into. So B inherits A's hardness; and because A was as hard as all of NP, by transitivity B is too. That makes B NP-hard. Add a quick check that B is itself in NP, and B is NP-complete: it has joined the club at the very ceiling of the class.

The four-line recipe for proving a problem NP-complete

Almost every NP-completeness proof you will ever read or write fits the same template. Memorise its shape and the rest is filling in details for your specific problem. The cleverness lives entirely in step three — the gadget that turns one problem's structure into another's — but the surrounding scaffolding never changes.

  1. Show B is in NP. Exhibit a short certificate for any yes-instance and a polynomial-time verifier that accepts it. Skipping this is a real error: a problem can be NP-hard yet sit far above NP, so 'NP-hard' alone does not give you 'NP-complete'.
  2. Pick a known NP-complete problem A to reduce FROM. Choose one whose structure already resembles B — that choice is half the battle. Good starting points are 3-SAT for logical constraints, vertex cover or independent set for graphs, and subset-sum for number-packing.
  3. Describe a polynomial-time map f that turns any instance x of A into an instance f(x) of B. This is the gadget: small widgets in B that mimic the variables and clauses (or vertices and edges) of A. f must run in polynomial time, which also bounds how big f(x) can be.
  4. Prove the equivalence in BOTH directions: x is a yes-instance of A if and only if f(x) is a yes-instance of B. The 'only if' (yes maps to yes) and the 'if' (no maps to no, i.e. a yes for f(x) forces a yes for x) are separate arguments, and forgetting the second is the classic way a 'proof' silently breaks.

Notice the division of labour. Step one is about B alone; steps two through four are about the bridge from A. The polynomial-time bound appears twice — on the verifier and on the map f — and both matter: a reduction that took exponential time would prove nothing, because it could simply solve A by brute force along the way. The honest engine under the whole edifice is still the open status of P versus NP; we will return to exactly what that buys and costs at the end.

A worked sketch: 3-SAT to Independent Set

Let us run the recipe on a concrete, classic gadget so the abstraction lands. Take 3-SAT — a boolean formula in which every clause is an OR of exactly three literals, like (x OR not-y OR z) AND (not-x OR y OR w) — and reduce it to Independent Set: "does this graph have k mutually non-adjacent vertices?" Independent Set is in NP (a proposed set of k vertices is trivially checked for non-adjacency), so step one is done. Now the gadget.

Formula:  (x OR not-y OR z) AND (not-x OR y OR w)

Gadget:   one triangle per clause, vertex = literal

   clause 1            clause 2
     x                  not-x
    /  \                /   \
 not-y -- z          y ----- w

 + connect EVERY literal to its negation across triangles
   (x -- not-x,  y -- not-y,  ...)

Ask:  is there an independent set of size k = #clauses ?
One triangle per clause forces one true literal each; negation edges keep the choice consistent.

The construction is two moves. First, for each clause make a triangle of three vertices, one per literal; because all three are mutually adjacent, an independent set can pick at most one vertex from each triangle. Second, draw an edge between every literal and its negation wherever they appear, so you can never select both x and not-x. Now set k equal to the number of clauses. Building this graph is plainly polynomial — a few vertices and edges per clause — so the map f is fast. Everything hinges on the equivalence claim, which we now check both ways.

Forward: if the formula is satisfiable, each clause has at least one true literal; pick one true literal's vertex from every triangle. That is k vertices, one per triangle so no triangle edge is violated, and because a variable's truth value is fixed we never pick both x and not-x, so no negation edge is violated either — a valid independent set of size k. Backward: if there is an independent set of size k, it must take exactly one vertex per triangle (k triangles, at most one each, k total), and the negation edges guarantee the chosen literals are consistent, so setting those literals true satisfies every clause. Yes maps to yes, and a yes for the graph forces a yes for the formula. The reduction is complete, and Independent Set is NP-complete.

The zoo, and what membership really means

Once SAT cracked open, the dam broke. Independent set, vertex cover, clique, graph 3-coloring, Hamiltonian cycle, the travelling salesman decision problem, subset-sum and partition, bin packing, and hundreds more were each chained back to a known-hard problem by exactly the kind of gadget you just built. They form one giant equivalence class — the NP-complete zoo — and the chaining means something startling: a polynomial-time algorithm for any single one of them would, by composing reductions, yield one for all of them, and indeed for all of NP. They sink or swim together.

There is also a quieter possibility worth naming. Some problems sit in NP, look hard, yet resist every reduction proving them NP-complete — the suspected NP-intermediate problems, with integer factoring and graph isomorphism the famous candidates. If P is not NP, a theorem of Ladner guarantees such middle-dwellers must exist; we just cannot point at one with certainty. So the landscape is not a clean two-bucket split into "easy P" and "hard NP-complete" — there may be a layer in between, which is one more reason to state every hardness claim with care.

So what does P vs NP actually mean?

Strip away the mystique and the P versus NP question is brutally simple to state: is every problem whose solutions are easy to check also a problem whose solutions are easy to find? If P equals NP, then the gap between recognising a good answer and producing one collapses everywhere at once — for SAT, for protein folding posed as search, for theorem-proving, for breaking the cryptography that secures your bank login, all of it. If P does not equal NP — the way essentially every expert bets — then that gap is real and permanent, and the NP-complete problems are genuinely, structurally beyond efficient solution. Either way the answer reshapes computation; and to this day, nobody knows which it is.

Now the sober part — what proving a problem NP-complete does and does not buy you in practice. It does not mean give up. It means stop hunting for a fast exact, general, worst-case algorithm and spend your effort where progress is still possible. You might design an approximation algorithm that guarantees a solution within, say, a factor of 2 of optimal — though remember that a 2-approximation is a worst-case promise, not a typical-case one. You might exploit that real inputs are small or special, via parameterized or exponential-but-practical methods. Or you might lean on heuristics that are usually excellent and occasionally bad. NP-completeness redirects the search; it does not end it.

Step back and see what this rung gave you. A precise meaning for "efficient" (polynomial time), a precise meaning for "verifiable" (NP), a tool for transferring hardness (the reduction), one foundation stone laid by hand (Cook-Levin), and a four-line recipe for convicting new problems by chaining them to that stone. The honest frontier is that the central question stays open: "NP-complete" is the strongest evidence of intractability we know how to give, built on the gap between polynomial and exponential growth — but it is evidence, not a verdict. Holding that distinction firmly, without overclaiming and without despairing, is what it means to have truly understood this rung.