P vs NP Complexity Classes

Definition: The central open problem in theoretical computer science, asking whether every decision problem whose solution can be verified quickly (the class NP) can also be solved quickly from scratch (the class P). Formalized by Stephen Cook and, independently, Leonid Levin in 1971, it is widely considered the most important open question in computer science and one of the seven Clay Mathematics Institute Millennium Prize Problems. Almost every computer scientist believes P ≠ NP, but no one has been able to prove it — decades of effort have produced a rich landscape of related classes and reduction techniques without settling the core question.

Formal Definition

P (Polynomial time): the set of decision problems solvable by a deterministic Turing machine in time O(n^k) for some constant k, where n is the input size
NP (Nondeterministic Polynomial time): the set of decision problems for which a proposed solution — a “certificate” or “witness” — can be checked for correctness by a deterministic Turing machine in polynomial time
Equivalently, NP is the set of problems solvable in polynomial time by a nondeterministic Turing machine, one allowed to “guess” the right branch of computation at each step (see Turing Machine)
NP-hard: a problem H such that every problem in NP polynomial-time reduces to H; H is at least as hard as anything in NP, but H itself need not be in NP
NP-complete: a problem that is both in NP and NP-hard — the hardest problems within NP itself, and the problems that matter most for resolving P vs NP
The question “does P = NP?” is exactly the question “if a solution can be checked quickly, can it also be found quickly?” — formalized, it asks whether P and NP denote the same set of languages

How It Works

Every problem in P is automatically in NP — if you can solve something quickly, you can trivially verify a claimed solution quickly, just by solving it yourself and comparing
The open question is the reverse direction — whether NP problems that seem to require exhaustive search actually admit some clever polynomial-time algorithm nobody has found yet
NP-completeness as a hardness ladder: Boolean satisfiability (SAT) was the first problem proven NP-complete, via the Cook-Levin theorem, and since then thousands of other problems have been shown NP-complete by reducing a known NP-complete problem to them
The domino effect: because NP-complete problems all reduce to one another in polynomial time, finding a polynomial algorithm for even one of them would immediately yield one for all of them, collapsing P and NP together
Certificates make verification cheap: for SAT, the certificate is simply a variable assignment; for the Traveling Salesperson decision variant, it’s a specific route; checking either against the instance takes only polynomial work, even though finding one from scratch may not
Exponential search space, polynomial check: the defining shape of an NP problem is a search space that grows exponentially with input size (e.g. 2^n possible truth assignments) paired with a check that grows only polynomially — that asymmetry is the entire mystery of P vs NP
No known counterexample, no known proof: despite over 50 years of trying, nobody has exhibited a polynomial-time algorithm for any NP-complete problem, nor proven that none can exist — both outcomes remain formally possible

Why It Matters

One of the seven Clay Mathematics Institute Millennium Prize Problems, carrying a $1,000,000 award for a correct proof in either direction — only one of the seven (the Poincaré conjecture) has been solved as of this writing
Modern cryptography leans heavily on the assumption that P ≠ NP (or at least that specific problems like integer factorization and discrete log are hard) — RSA, Diffie-Hellman, and most of e-commerce security would need to be rebuilt from scratch if P = NP turned out to be true with a practical algorithm
A proof that P = NP, if the resulting algorithm were actually efficient in practice, would revolutionize optimization, logistics, drug design, and scheduling — problems currently attacked with heuristics could be solved exactly and fast
Conversely, most researchers expect P ≠ NP, and this belief already shapes engineering practice — recognizing a problem as NP-hard is itself useful information, since it redirects effort toward approximation, heuristics, or restricted special cases rather than a futile search for an exact fast algorithm
It gives computer science a precise, shared vocabulary for “this is provably hard” versus “this is merely hard to find an algorithm for” — a distinction that matters enormously when deciding how to spend engineering time
It connects abstract theory directly to funding and hiring decisions in practice — companies routinely decide whether to invest in exact solvers or heuristic engineering based on whether a problem is known to be NP-hard

Under the Hood: What an NP Verifier Actually Looks Like

Take Boolean Satisfiability (SAT) as the running example. An instance is a Boolean formula, e.g. (x1 ∨ ¬x2) ∧ (x2 ∨ x3) ∧ (¬x1 ∨ ¬x3), and the question is whether some assignment of true/false to each variable makes the whole formula evaluate to true.

A verifier for SAT is a deterministic algorithm V(formula, certificate) that takes the formula and a proposed certificate — here, a specific assignment like x1=true, x2=false, x3=true — and checks it in polynomial time:

Read the certificate and record the truth value assigned to each variable
Substitute those values into every clause of the formula
Evaluate each clause (a clause is satisfied if at least one of its literals is true)
Accept if every clause evaluates to true, reject otherwise

Step 2 and 3 together take time proportional to the formula’s length — clearly polynomial, in fact roughly linear. The certificate itself has size proportional to the number of variables, also polynomial in the input. Crucially, V never has to search for the assignment — it only has to check one that’s handed to it. That’s the whole definition of NP: a polynomial-time verifier plus a polynomial-size certificate. Subset Sum works the same way — given a set of numbers and a target, the certificate is a subset, and the verifier just sums it and compares, again clearly polynomial regardless of how astronomically large the space of possible subsets is.

Proof Sketch: The Cook-Levin Theorem

The Cook-Levin theorem (1971) proves SAT is NP-complete — the founding result of NP-completeness theory, since it gives the first problem provably as hard as anything in NP, which every subsequent NP-completeness proof builds on by reduction. The construction sketch:

Start with an arbitrary NP problem. Let L be any language in NP, meaning some nondeterministic Turing machine M decides L in polynomial time p(n)
Encode a full computation as a table. Represent an accepting computation of M on input w as a grid — rows are time steps 0 through p(n), columns are tape cells — where each cell holds M’s tape symbol, state, and head position at that step
Write Boolean variables for every cell. Introduce a variable for “cell (i,j) holds symbol s at time i” for every relevant i, j, and s — polynomially many variables since the grid itself is polynomial in size
Add clauses enforcing the rules of computation. Construct clauses forcing: exactly one symbol per cell at each time step, the first row matches the actual input w, each transition obeys M’s transition function δ, and some cell reaches qaccept
Conjoin everything into one formula. The resulting formula φ is satisfiable if and only if there exists a valid accepting computation history of M on w — i.e., φ is satisfiable exactly when w ∈ L
Confirm the construction is itself polynomial. Building φ from M and w takes time polynomial in p(n), which is what makes this a valid polynomial-time reduction from L to SAT — since L was an arbitrary NP language, this shows every NP problem reduces to SAT, so SAT is NP-hard, and since SAT is also in NP itself (trivial verifier), SAT is NP-complete

co-NP: the class of problems whose no instances have polynomial-size certificates — e.g. proving a Boolean formula is UNsatisfiable, or that a number is NOT prime by exhibiting no easy witness; whether NP = co-NP is itself another major open question, believed false
PSPACE: problems solvable using polynomial space, regardless of time; contains both P and NP (P ⊆ NP ⊆ PSPACE), and whether any of those containments is strict is open — see Savitch’s Theorem for how nondeterministic and deterministic space relate
EXPTIME: problems solvable in exponential time 2^(n^k); known to strictly contain P by the time hierarchy theorem, and NP ⊆ EXPTIME trivially, since brute-force checking every certificate takes exponential time
BPP (Bounded-error Probabilistic Polynomial time): problems solvable in polynomial time by a randomized algorithm with bounded error probability; widely conjectured to equal P, unlike the NP question
#P (sharp-P): the class of counting problems asking “how many solutions exist,” rather than NP’s “does a solution exist” — provably at least as hard as NP, since counting solutions is at least as hard as detecting whether any exist
NP-intermediate problems: if P ≠ NP, Ladner’s theorem guarantees problems exist in NP that are neither in P nor NP-complete; integer factorization and graph isomorphism are the leading real-world candidates believed (but not proven) to live in this gap
L and NL (Logarithmic space): even more restrictive classes bounding memory rather than time to O(log n); known to satisfy L ⊆ NL ⊆ P, giving complexity theory a finer-grained hierarchy below P itself

Key Theorems and Results

Cook-Levin Theorem (1971): SAT is NP-complete — the foundational result that made the entire field of NP-completeness possible, discussed step by step above
Karp’s 21 NP-complete problems (1972): Richard Karp showed 21 classic combinatorial problems — including Vertex Cover, Independent Set, Hamiltonian Cycle, and Graph Coloring — are all NP-complete, demonstrating the phenomenon is widespread rather than a quirk of SAT
Ladner’s Theorem (1975): if P ≠ NP, then NP-intermediate problems must exist — languages in NP that are neither in P nor NP-complete, ruling out a clean two-tier hierarchy
Time Hierarchy Theorem: more time strictly buys more computational power for deterministic Turing machines, proving P is strictly contained in EXPTIME even though P vs NP itself remains open
Baker-Gill-Solovay (1975): shows P vs NP cannot be resolved by “relativizing” proof techniques (arguments that still work when both sides get access to the same oracle) — a formal explanation for why so many natural proof attempts have stalled
PCP Theorem (1990s): every NP proof can be rewritten so a verifier needs to check only a constant number of randomly chosen bits of it — a surprising strengthening of verification that underlies most modern hardness-of-approximation results

Comparison: P vs NP vs NP-Complete vs NP-Hard

	P	NP	NP-Complete	NP-Hard
Solvable in poly time?	Yes, by definition	Unknown (open question)	Unknown — would resolve P vs NP	No known poly algorithm, and may not even be a decision problem
Verifiable in poly time?	Yes (trivially, since solvable)	Yes, by definition	Yes	Not necessarily
Relationship to the other classes	Subset of NP	Superset of P, contains NP-Complete	Subset of NP, hardest problems in it	Superset of NP-Complete, may sit outside NP entirely
Example	Sorting, shortest path (Dijkstra)	SAT, TSP (decision form), Subset Sum	3-SAT, Vertex Cover, Hamiltonian Cycle	The Halting Problem, TSP (optimization form)
Closed under complement?	Yes	Unknown (this is the NP vs co-NP question)	Unknown	Not generally applicable
Believed relationship to P	P = P	Believed P ⊊ NP	Believed disjoint from P (if P ≠ NP)	Believed disjoint from P

Common Pitfalls

Confusing “NP” with “not polynomial” — NP stands for Nondeterministic Polynomial time, and P is in fact a subset of NP, not its opposite
Treating “NP-hard” and “NP-complete” as synonyms — every NP-complete problem is NP-hard, but NP-hard problems needn’t be in NP at all (they may not even be decision problems, e.g. optimization or undecidable problems)
Believing NP-complete problems are always intractable in every practical instance — many NP-complete problems have efficient heuristics or approximation algorithms that work extremely well on real-world inputs, worst-case hardness isn’t the same as “never solvable in practice”
Assuming a problem is NP-complete just because it “feels combinatorial” — proving NP-completeness requires an actual reduction from a known NP-complete problem, not intuition
Thinking P = NP would make all currently-hard problems instantly trivial — even if P = NP were proven, the resulting algorithm’s polynomial could have an astronomically large exponent or constant, offering no practical speedup at all
Forgetting that NP is about decision problems (yes/no answers) — the optimization version of TSP (“find the shortest route”) isn’t technically in NP, only its decision version (“is there a route shorter than k?”) is
Assuming exponential worst-case time means exponential time on every input — many NP-hard problems are solved exactly and fast in practice via branch-and-bound, SAT solvers, or ILP solvers that exploit structure absent from adversarial worst cases
Conflating “NP-complete” with “impossible” — it means no known polynomial algorithm, not that the problem can’t be solved at all; even brute force eventually finds the answer, just not within a practical time bound for large inputs

Worked Example: Verifying a 3-SAT Certificate

Consider the 3-SAT formula φ = (x1 ∨ x2 ∨ ¬x3) ∧ (¬x1 ∨ x2 ∨ x3) ∧ (x1 ∨ ¬x2 ∨ x3) and the proposed certificate x1 = true, x2 = false, x3 = true.

Checking clause by clause: clause 1 needs x1, x2, or ¬x3 true — x1 = true satisfies it. Clause 2 needs ¬x1, x2, or x3 true — x3 = true satisfies it. Clause 3 needs x1, ¬x2, or x3 true — both x1 and x3 satisfy it. All three clauses are true, so the certificate is verified in linear time, without ever having searched through the 2^3 = 8 possible assignments to find it.

Worked Example: Subset Sum Verification

Consider the set {3, 7, 12, 19, 24} and target sum 31. The decision question is: does some subset sum to exactly 31? A brute-force solver would need to check up to 2^5 = 32 subsets, and the exponent grows with every extra element added to the set.

Given the proposed certificate {7, 24}, verification is immediate:

Read the certificate: the subset {7, 24}
Sum its elements: 7 + 24 = 31
Compare to the target: 31 = 31, so accept

That check took three trivial steps regardless of how large the full set was — the certificate collapses an exponential search into a linear-time confirmation, the same pattern as the SAT example above and the defining shape of every problem in NP.

Applications Beyond Pure Theory

Cryptography: RSA’s security rests on integer factorization being computationally hard in the worst case — a fast general factoring algorithm (which would not even require proving P = NP, just breaking this specific problem) would break most of today’s public-key infrastructure overnight
Optimization and logistics: delivery routing, airline scheduling, and warehouse packing are all NP-hard in their exact form, which is why real logistics software leans on approximation algorithms, integer programming solvers, and metaheuristics like simulated annealing rather than exact brute force
Chip design and verification: circuit layout and formal hardware verification frequently reduce to SAT or related NP-complete problems, which is exactly why modern SAT solvers, despite worst-case exponential behavior, are engineered to be extremely fast on the structured instances that show up in real chips
Machine learning: training certain model classes optimally (e.g. exact decision tree learning, some neural network training formulations) is NP-hard, which is part of the justification for using gradient-based heuristics that only find locally, not globally, optimal solutions
Engineering triage: recognizing “this is NP-complete” during a design review is a practical red flag — it tells a team to stop hunting for an exact polynomial algorithm and instead budget for heuristics, approximations, or restricting the problem’s scope

Best Practices (How to Reason About Likely-Hard Problems)

Before searching for an efficient algorithm, check whether the problem resembles a known NP-complete problem — a quick literature or reduction check can save weeks of futile algorithm design
If a problem is confirmed NP-hard, shift the question from “solve it exactly, fast” to “solve it approximately, fast” or “solve small/structured instances exactly” — these are usually the only tractable options
Look for restricted special cases that may be easier — e.g. 2-SAT is in P even though 3-SAT is NP-complete, and planar graph problems are often easier than their general-graph counterparts
Consider approximation algorithms with provable guarantees (e.g. a 2-approximation for Vertex Cover) when an exact answer isn’t strictly required
Consider parameterized complexity — some NP-hard problems become tractable when a specific parameter (like solution size) is small, even if the input as a whole is large
Don’t assume worst-case hardness dooms practical performance — try modern SAT/ILP solvers or branch-and-bound on real instances before concluding a heuristic is necessary, since real-world structure often makes them fast in practice

FAQ

Has anyone proven P = NP or P ≠ NP? No — it remains completely open as of this writing, despite being one of the most studied questions in computer science since 1971.

What happens if someone proves P = NP? It depends entirely on whether the resulting algorithm is practically efficient — a proof could be purely existential or have an astronomically large polynomial, in which case daily life would change little, but a genuinely fast algorithm would upend cryptography and enable exact solutions to huge classes of optimization problems.

Is factoring integers NP-complete? No — factoring is in NP (and in co-NP), but it isn’t known to be NP-complete, and most experts believe it isn’t; it’s a leading candidate for an NP-intermediate problem.

Why do most computer scientists believe P ≠ NP? Decades of trying and failing to find polynomial algorithms for thousands of NP-complete problems, combined with formal barriers like relativization that explain why the obvious proof strategies don’t work, have pushed the field toward that consensus, though it remains a belief, not a proof.

Is NP-complete the same as “worst possible” complexity? No — problems can be far harder than NP-complete, including undecidable problems like the Halting Problem, which have no algorithmic solution at all, polynomial or otherwise; NP-complete only means “hardest within NP.”

Does quantum computing solve P vs NP? No — quantum computers are believed to offer speedups for specific problems (like factoring, via Shor’s algorithm) but are not believed to solve NP-complete problems in polynomial time in general; the class BQP (quantum poly-time) is not known to contain NP.

Could P vs NP simply be unprovable, like some statements in mathematics? It’s a live possibility — some researchers have raised the prospect that P vs NP is independent of standard axiomatic set theory (ZFC), meaning it could be neither provable nor disprovable within it, though most working researchers still treat it as an open problem awaiting a genuine proof rather than a case of formal independence.

Do approximation algorithms “solve” NP-hard problems? Not exactly — they solve a relaxed version of the problem, finding a solution provably within some bound of optimal in polynomial time, which is often good enough in practice even though it isn’t an exact solution to the original question.

History

Stephen Cook formalized the question and proved the Cook-Levin theorem in his 1971 paper “The Complexity of Theorem-Proving Procedures,” introducing NP-completeness
Leonid Levin independently discovered essentially the same result in the Soviet Union around the same time, working in relative isolation from Western academia — hence “Cook-Levin”
Richard Karp’s 1972 paper “Reducibility Among Combinatorial Problems” showed 21 well-known problems were NP-complete, proving the phenomenon was pervasive rather than an isolated curiosity about SAT
The Clay Mathematics Institute named P vs NP one of its seven Millennium Prize Problems in 2000, attaching a $1,000,000 prize to a correct resolution
Numerous purported proofs — of both P = NP and P ≠ NP — have been submitted and publicly refuted over the decades, none surviving peer scrutiny
The problem’s difficulty has itself become a subject of meta-study, including formal “barrier” results (relativization, natural proofs, algebrization) explaining why entire categories of proof techniques cannot resolve it
The PCP theorem, developed through the late 1980s and early 1990s, unexpectedly reshaped the field by tying NP-completeness to the hardness of even approximating solutions to many optimization problems
Popular culture and mainstream media occasionally cover purported P vs NP proofs, most of which are informally reviewed and dismissed by the theoretical computer science community within days

Common Interview Questions

“What’s the difference between P, NP, NP-hard, and NP-complete?” — expect a clear statement of each definition and how they nest, plus an example problem for each
“Is the Traveling Salesperson Problem NP-complete?” — expect a distinction between the decision version (NP-complete) and the optimization version (NP-hard, not strictly NP)
“How would you prove a new problem is NP-complete?” — expect two parts: show the problem is in NP (give a poly-time verifier), then reduce a known NP-complete problem to it in polynomial time
“If P = NP, does that mean we could break all encryption?” — expect a nuanced answer distinguishing a purely existential proof from a genuinely efficient constructive algorithm
“Why is verifying a Sudoku solution easy but solving one hard?” — expect an explanation connecting this everyday example to the definition of NP: cheap certificate-checking versus expensive search
“What’s the difference between NP-hard and undecidable?” — expect a clear line drawn between “no known efficient algorithm” (NP-hard) and “provably no algorithm at all, ever” (undecidable), with the Halting Problem as the canonical undecidable example

Example

The Traveling Salesperson Problem (TSP) and Boolean Satisfiability (SAT) are the two most commonly cited NP-complete problems — TSP’s decision form asks “is there a route visiting every city with total distance under k?”, and SAT asks “does some assignment of variables make this formula true?” Both admit certificates that are trivial to check (a specific route, a specific assignment) but, as far as anyone has proven, require exponential effort to find from scratch — which is precisely the gap that P vs NP asks whether we can close.

Referenced by

Dig deeper

Spot an error in this note?