The hardest problems in NP — and they are all secretly the same problem. CLIQUE, INDEPENDENT-SET and VERTEX-COVER wear three faces but a graph and its complement convert any one into the others in polynomial time. So a fast algorithm for one would be a fast algorithm for all of them at once. Down the center, data flows: a graph goes in, the engine brute-forces the certificates, the equivalence comes out. The blue team builds and defends it; the red team tries to break it.
source R. M. Karp, Reducibility Among Combinatorial Problems (1972), pp. 85–103 — doi.org/10.1007/978-1-4684-2001-2_9; built on S. A. Cook, The Complexity of Theorem-Proving Procedures (1971), doi:10.1145/800157.805047. Rendered, not quoted.
NP-complete = in NP (a witness is poly-checkable) AND NP-hard (everything in NP reduces to it). The reductions here are pure graph surgery — take the complement Ḡ (flip every edge to a non-edge):
C→I a k-clique in G is exactly a k-independent-set in Ḡ. I→V an independent set S is exactly the complement V∖S being a vertex cover. Same vertices, re-read.
For the current graph and target k, the three certificates live:
| problem | certificate | size | verifies? |
|---|
These three are one equivalence class under the-karp-reduction — Karp's 1972 list of 21 problems, each poly-reducible to the next, all crowned NP-complete by Cook's theorem that SAT is.
If any single one is easy, the reductions carry that ease to all of them, and the-p-vs-np collapses to P = NP. Each sphere is the next one's premise.
The blue team's live check: re-run every reduction over all 64 graphs on 4 vertices and all k, confirming the biconditionals hold exactly. If red slips in a false reduction, this badge is where it shows.
A certificate is a short proof you can check fast — that is what puts a problem in NP. Each of these asks "does a subset of size k exist with a property":
| problem | ask | certificate | check |
|---|---|---|---|
| CLIQUE | k mutually adjacent | a k-subset | O(k²) |
| IND-SET | k mutually non-adjacent | a k-subset | O(k²) |
| VTX-COVER | s vertices touch every edge | an s-subset | O(m) |
Checking is trivial; finding is the mountain. Feed a graph into the panel and watch one certificate become the other two by complementation.
Brute force over all 2ⁿ subsets — every number below is computed on the spot, never looked up.
Switch the reading — the highlighted set does not move; only the graph flips to Ḡ and the name of what it proves changes. One object, three problems.
What the machine proves, exhaustively: over all 64 graphs on 4 vertices and every k, a k-CLIQUE in G ⟺ a k-IND-SET in Ḡ ⟺ an (n−k)-VERTEX-COVER in Ḡ — zero mismatches. Each is in NP; each is NP-hard; a poly solver for one is a poly solver for all. NP-complete needs both halves — drop either and it is not complete.
The blue team's witness (left) confirms every reduction live; the red team (right) tries to smuggle a false one past it.
And the three faces are not equally approximable: VERTEX-COVER has a simple 2-approximation, yet CLIQUE and IND-SET admit no constant-factor approximation unless P=NP (Håstad). Poly-time inter-reducibility of the exact problem says nothing about approximating it — the reductions do not preserve approximation ratios.
"NP means non-polynomial." Cut. NP = nondeterministic polynomial: solutions are verifiable in poly time. Whether they are findable in poly time is the open question.
"NP-complete means no algorithm exists." Cut. Brute force always works — the engine here does exactly that. "Hard" means no known polynomial one, worst case.
"NP-hard implies in NP." Cut. NP-hard ⊇ NP-complete but is wider: the halting problem is NP-hard and not even decidable, let alone in NP.
The red team's move: claim EDGE (does G contain an edge? — i.e. 2-CLIQUE, which is trivially in P) is NP-complete, via a bogus reduction asserting "3-CLIQUE ⟺ EDGE". The blue team's witness (window 7) is watching.
The biconditional fails: a single edge with no triangle has EDGE=true but 3-CLIQUE=false. The witness recomputes, finds the counterexample, disagrees with the known truth, and turns red. Nothing is faked; the attack is real and it is caught.