Complexity Classes: P, NP, PSPACE

Tractable versus intractable gave us the headline split: problems a computer can solve in a reasonable time, versus problems that blow up. To reason about that split precisely, computer scientists sort every problem into complexity classes — buckets defined by how much time or memory (space) a Turing machine needs to solve them, measured with big-O notation.

This page maps the landscape: the three headline classes P, NP and PSPACE, how they nest inside one another, and the single most famous open question in all of computer science that lives right in the middle of the picture.

P — solvable quickly

P ("polynomial time") is the class of decision problems a deterministic Turing machine can solve in a number of steps bounded by a polynomial in the input size n — O(n), O(n^2), O(n^3\log n), and so on. Polynomial time is the mathematician's stand-in for "efficient" or "tractable": as the input grows, the work grows gently, not explosively.

Sorting a list, finding a shortest path, testing whether a number is prime, matching people to jobs — all in P. If a problem is in P, we are basically happy: we have a real algorithm that scales.

NP — answers you can quickly check

NP ("nondeterministic polynomial time") is the class of problems where a proposed solution can be verified in polynomial time — even if finding that solution might be dreadfully hard. The tell-tale shape of an NP problem: a lucky guess (a "certificate") plus a fast checker.

Sudoku: filling in a giant grid is hard, but if someone hands you a completed grid you can check it against the rules in a flash.
Boolean satisfiability (SAT): finding truth values that make a formula true may take exponential search — but hand me the assignment and I plug it in and check it instantly.
Hamiltonian path: finding a route through every city once is brutal; checking a proposed route is a quick walk down the list.

The definition has two equivalent faces: "solvable in polynomial time by a nondeterministic machine that can explore all guesses at once" and "a solution is verifiable in polynomial time with a certificate." The verification view is the one to keep in your head.

NP does not stand for "non-polynomial". It is the single most common misconception about complexity. The "N" is for nondeterministic, and NP is defined by fast checking, not slow solving. In fact every problem in P is also in NP (if you can solve it fast, you can certainly check it fast — just re-solve it and compare). So P is a subset of NP, not the opposite of it.

PSPACE — solvable with modest memory

PSPACE is the class of problems solvable using a polynomial amount of memory, with no limit at all on time. Space is a far more forgiving resource than time: a machine can reuse the same cells over and over, so a polynomial-space machine can afford to run for an exponential number of steps, methodically trying possibilities as long as it never needs more than n^k cells at once.

This makes PSPACE roomy. It comfortably contains both P and NP, and it captures problems that feel even harder — like deciding who wins a two-player game (chess, Go, or the abstract game of "geography") where you must reason about every reply to every move. You can search that whole game tree while only ever remembering the single line you are currently exploring.

How they nest

The classes sit inside one another like Russian dolls. Every containment below is a proven theorem; the one thing nobody knows is whether any of them is actually an equality.

In symbols: \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} \subseteq \mathrm{EXPTIME} and we do know the two ends are different — \mathrm{P} \ne \mathrm{EXPTIME} (a consequence of the time hierarchy theorem). So at least one of those \subseteq signs is really a \subsetneq — but which ones is a mystery.

The million-dollar question: does P = NP?

We know \mathrm{P} \subseteq \mathrm{NP}. The staggering open question is whether they are actually the same class:

Is every problem whose answer is quick to check also quick to solve? That is precisely the question of whether \mathrm{P} = \mathrm{NP}.
Almost everyone believes \mathrm{P} \ne \mathrm{NP} — that some problems are genuinely hard to solve even though solutions are easy to verify — but nobody has proved it either way.
It is one of the seven Clay Millennium Prize Problems: a correct proof is worth $1,000,000.

The stakes are enormous. Vast swathes of the problems we wish we could solve efficiently — scheduling, routing, protein folding, breaking cryptography — are in NP but not known to be in P. If \mathrm{P} = \mathrm{NP}, efficient algorithms for all of them exist and much of modern encryption collapses. If (as expected) \mathrm{P} \ne \mathrm{NP}, that hardness is real and permanent.

Here is the intuition for why people bet on \mathrm{P} \ne \mathrm{NP}. Recognising a brilliant proof once you're shown it is far easier than discovering it; appreciating a symphony is easier than composing one. NP is the world of problems where a good answer, once found, is obviously good — and it would be almost too good to be true if finding were always as easy as recognising. But "almost too good to be true" is not a proof, which is exactly why the question is still open after fifty years.