Lesson · Algorithms and Complexity · Limits

P, NP and NP-Completeness

P is what can be solved in polynomial time; NP is what can be verified in polynomial time. Whether they are equal is the central open question, and the NP-complete problems are the ones on which it turns.

Open the interactive lesson Practice

P solvable in polynomial time NP a proposed solution is VERIFIABLE in polynomial time P ⊆ NP; whether P = NP is OPEN NP-complete: in NP, and everything in NP reduces to it

Two classes and an open question

Core ideas

What this lesson establishes

The classification is about the problem, not about any particular algorithm, and knowing it changes what you should attempt.

NP is about verification, not non-determinism

A problem is in NP when a claimed solution can be checked quickly. The name comes from an older definition and misleads.

NP-complete problems are the hardest in NP

Everything in NP reduces to them, so a polynomial algorithm for one gives one for all.

The classification is practical information

"NP-complete" means stop looking for an exact efficient algorithm and consider approximation, heuristics or special cases.

The material

The classes

Definitions, examples, reductions, and what the classification means in practice.

Definition · P

The class of decision problems solvable by an algorithm running in time O(nᵏ) for some constant k, where n is the input size. Informally: efficiently solvable.

Definition · NP

The class of decision problems for which a proposed solution can be verified in polynomial time. Informally: if someone hands you an answer, you can check it quickly.

The name stands for nondeterministic polynomial, from an older definition using a machine that guesses. The verification definition is equivalent and far more intuitive: NP is not "not polynomial", and P is a subset of NP.

problem in P? in NP? is n prime? yes yes sort a list yes yes shortest path yes yes is this formula satisfiable? unknown yes does a Hamilton circuit exist? unknown yes graph colouring with 3 colours unknown yes does this program halt? NO NO — undecidable

Every problem in P is in NP: if you can solve it quickly you can verify a claimed answer quickly by solving it and comparing. The reverse inclusion is the open question.

Reductions

Definition · Polynomial-time reduction

Problem A reduces to B if any instance of A can be transformed in polynomial time into an instance of B with the same answer. Then an efficient algorithm for B gives one for A, so B is at least as hard as A.

Definition · NP-complete

A problem is NP-complete if it is in NP and every problem in NP reduces to it. It is NP-hard if the second condition holds whether or not it is in NP.

Theorem · Cook-Levin theorem (1971)

SAT — deciding whether a propositional formula is satisfiable — is NP-complete. It was the first problem shown to be so, and every subsequent NP-completeness proof reduces from a problem already known to be complete.

“Tautology, Contradiction, Satisfiability” in Logic and Proof raised the question and named the result; here is what it means. Thousands of problems are now known to be NP-complete: Hamilton circuit, 3-colouring, subset sum, the travelling salesman decision problem, 0/1 knapsack, and clique among them.

They are all equivalent in the sense that matters: a polynomial-time algorithm for any one would give one for all of them, and hence P = NP. Fifty years of effort has produced neither such an algorithm nor a proof that none exists.

What the classification means in practice

In P. Look for a good polynomial algorithm and expect to find one.
NP-complete. Stop looking for an efficient exact algorithm. Consider approximation algorithms with proved ratios, heuristics with no guarantee, exact methods on restricted inputs, or solvers that are fast in practice.
Undecidable. Stop entirely. No algorithm exists, and “Decidability and the Halting Problem” is about what that means.

Being NP-complete is a worst-case statement and does not mean instances are hard in practice. Industrial SAT solvers routinely handle formulas with millions of variables, because real instances have structure. The classification tells you what to expect in general and not what will happen on your data.

If P = NP were proved constructively, essentially every optimisation problem would become tractable and public-key cryptography would collapse. Most researchers expect P ≠ NP; nobody has proved it, and it is one of the Clay Millennium Problems.

Interactive

Algorithms and growth

Counts from running, not from quoting

The line the classification draws

Polynomial curves and 2ⁿ on one log-scale plot, opened at n = 64: n² is 4 096 and 2ⁿ is about 1.8 × 10¹⁹, which at a billion operations a second is 585 years. That gap is the practical content of "tractable", and it is why the boundary is drawn at polynomial: 2ⁿ is the cost of trying every subset, and n² the cost of checking one.

What to examine

f(n)

g(n)

Input order

Growth policy

a (subproblems)

b (shrink factor)

d (combining cost n^d)

n16

measured—

predicted—

Method

Placing a problem

Verification first; it is the cheapest test.

Can a claimed solution be checked quickly?

If yes, the problem is in NP. This is usually obvious and is the first step.

Is there a known polynomial algorithm?

Then it is in P. Shortest path, sorting, primality, matching, minimum spanning tree.

Does it resemble a known NP-complete problem?

Hamilton circuit, SAT, 3-colouring, subset sum, clique. A reduction from one of these proves NP-hardness.

Act on the answer

In P: find the algorithm. NP-complete: approximate, restrict or use a solver. Undecidable: change the question.

Complexity classes

Score 0 / 0

Choose the answer you can justify.

Two similar problems, opposite sides

The clearest pair on this path.

EULER CIRCUIT — does a circuit using every edge once exist? criterion: connected, all degrees even check: one pass over the vertices Θ(n + |E|) IN P HAMILTON CIRCUIT — does a circuit visiting every vertex once exist? criterion: none known verification of a claimed circuit: check n edges Θ(n) ⟹ IN NP best known exact algorithm: exponential NP-COMPLETE Nothing in the two statements reveals which is which. The difficulty is a fact about the problems, not about the wording.

“Euler and Hamilton Paths” in Graphs and Trees presented both and noted the contrast; this is what the contrast means. Verifying a Hamilton circuit is easy, which puts it in NP; finding one is believed hard, which is the P versus NP question in miniature.

Common mistakes

Reading NP as "not polynomial"Every problem in P is in NP. The name is historical and actively misleading.

Treating NP-complete as "unsolvable"It is a worst-case statement. SAT solvers handle industrial instances with millions of variables.

Confusing NP-complete with undecidableNP-complete problems have algorithms that are slow. Undecidable problems have no algorithm at all, which is “Decidability and the Halting Problem”.

Check your understanding

✓

Finish when you can say what the classification changes.

For a problem you are handed, decide whether a solution is quickly verifiable, whether it resembles a known complete problem, and what you would attempt in each case. The last part is the point.

Note: P versus NP is one of the seven Clay Millennium Problems, with a million-dollar prize. It was posed by Cook in 1971 and, unusually for a problem of that stature, is stated in terms an undergraduate course can reach.