The idea: checking an answer vs finding one
Some problems are easy to check but seem hard to solve. Given the numbers 8, 6, 7, 5, 3, 10, is there a subset that adds up to 30? If someone hands you {8, 7, 5, 10}, you add four numbers and compare: done. Finding that subset yourself is another matter. P vs NP asks whether the two are really different: is every problem whose answers are easy to check also easy to solve?
P is the class of yes/no problems a computer can solve in polynomial time: n, n², n³ steps for an input of size n. Sorting, shortest paths and Euler paths are in P. NP is the class of yes/no problems where every "yes" has a short proof, a certificate, that can be checked in polynomial time. Every problem in P is in NP (you can check by solving), so P ⊆ NP. Nobody knows if P = NP.
Certificates and verifiers
For subset sum the certificate is the subset itself, written as one bit per number. The verifier reads the 6 bits, adds the numbers whose bit is 1, and compares the sum with the target: n + 1 = 7 steps (Demo 1: verify a certificate). A wrong certificate, like {3} for target 4, is simply rejected; it proves nothing about other subsets (Demo 3: target 4, no certificate exists).
| Problem | Certificate | Check |
|---|---|---|
| Subset sum | the subset | add it up, compare with T |
| SAT | a true/false value per variable | evaluate every clause |
| Clique | k vertices | every pair is joined |
| 3-colouring | a colour per vertex | no edge joins two equal colours |
| TSP (decision) | a tour | visits every city once, length ≤ L |
Brute force and 2ⁿ
Without a certificate, the sure method is to try them all. n numbers have 2ⁿ subsets. The page counts them in binary order and checks each in 7 steps: target 30 is found at subset 46 after 322 steps; target 4 needs all 64 subsets and 448 steps to answer "no" (Demo 2: brute force searches the subsets). Every extra number doubles the work.
The chart compares a polynomial n² with 2ⁿ on a log scale (Demo 4: brute force blows up). At n = 30 that is 900 against 1 073 741 824. At a microsecond a step, 0.9 ms against about 18 minutes; at n = 60, 3.6 ms against 36 000 years. Cleverer exact algorithms exist (dynamic programming solves subset sum in about n·T steps, see 0/1 Knapsack), but T can be a number with n digits, so that is still exponential in the input size.
Reductions: 3-SAT → Clique
A reduction turns any instance of problem A into an instance of problem B in polynomial time, so that the answers match. Then a fast solver for B gives a fast solver for A: B is at least as hard as A.
3-SAT asks whether a formula made of clauses with 3 literals each, like (x₁ ∨ x₂ ∨ ¬x₃) ∧ (¬x₁ ∨ x₂ ∨ x₃) ∧ (¬x₁ ∨ ¬x₂ ∨ x₃), can be made true. The reduction builds a graph: one vertex per literal per clause (9 here), and an edge between two vertices in different clauses unless one is x and the other ¬x (21 edges here). Ask for a clique of size k = number of clauses.
- A k-clique has one vertex per clause (there are no edges inside a clause) and never both x and ¬x. Set those literals true: every clause is satisfied.
- A satisfying assignment makes at least one literal per clause true. Those k literals never conflict, so they are all joined: a k-clique.
On the page the search picks x₁, rejects ¬x₁ from C2, takes x₂, rejects ¬x₁ and ¬x₂ from C3, and takes x₃: the clique {x₁, x₂, x₃} gives x₁ = x₂ = x₃ = true (Demo 5: reduce 3-SAT to Clique).
NP-complete and NP-hard
A problem is NP-hard if every problem in NP reduces to it. It is NP-complete if it is NP-hard and also in NP. The Cook–Levin theorem (1971) showed that SAT is NP-complete: the run of any polynomial-time verifier can be written as a Boolean formula that is satisfiable exactly when some certificate is accepted. After that, one reduction per problem is enough. Karp listed 21 NP-complete problems in 1972, including clique, graph colouring (see Graph Coloring), Hamiltonian cycle and knapsack in its subset-sum form; thousands are known now.
NP-hard problems need not be in NP. The halting problem is NP-hard but not solvable at all. The optimisation version of TSP ("find the shortest tour") is NP-hard; heuristics such as those on Travelling Salesman Heuristics find good tours without a guarantee. Small changes matter: an Euler path, which uses every edge once, is in P (Euler Path and Circuit), while a Hamiltonian path, which visits every vertex once, is NP-complete.
What P = NP would mean
If any one NP-complete problem had a polynomial algorithm, every problem in NP would, through the reductions. Finding a proof, a schedule or a circuit would be about as easy as checking one. It would also break most public-key cryptography: recovering an RSA or elliptic-curve private key is a problem whose answers are easy to check, so it is in NP. Cryptography relies on the opposite belief, that some easy-to-check problems are hard to solve. A proof of P = NP could still be impractical (an n¹⁰⁰ algorithm), but nobody expects one.
An open problem
P vs NP is one of the seven Millennium Prize Problems of the Clay Mathematics Institute, with $1 000 000 for a proof either way. Most researchers believe P ≠ NP. Known proof techniques (relativization, natural proofs, algebrization) have been shown unable to settle it on their own, which is part of why it has stayed open since 1971.
What the page leaves out
The formal definitions with Turing machines, nondeterminism as the original meaning of the N in NP, co-NP (short certificates for "no"), the polynomial hierarchy and PSPACE, the full Cook–Levin construction, the reductions from 3-SAT to subset sum and 3-colouring, pseudo-polynomial time and strong NP-completeness, approximation hardness (PCP theorem), average-case hardness, and SAT solvers that handle millions of variables in practice despite the worst case.