P vs NP asks whether every problem whose proposed solution can be quickly checked can also be quickly solved from scratch. Formalised in 1971, it is widely considered the single most important open question in theoretical computer science, carries a $1 million Clay Millennium Prize, and touches cryptography, optimization, and the fundamental limits of what computers can efficiently do.
Imagine a giant jigsaw puzzle with a million pieces. If someone hands you a completed puzzle, checking whether it's correctly assembled is fast — just look at it. But actually solving the puzzle from a pile of scrambled pieces could take enormously longer. P vs NP asks a version of this question with full mathematical precision: is there some clever shortcut that would make solving every such problem just as fast as checking it — or is checking fundamentally, unavoidably easier than solving, for at least some problems?
Thousands of important practical problems — from scheduling delivery routes to designing circuits to folding proteins — have this same frustrating character: nobody has ever found a fast way to solve them, despite decades of trying by brilliant researchers worldwide, yet checking a proposed solution is easy. The overwhelming intuition (though NOT a proof) is that P≠NP — that solving really is fundamentally harder than checking for at least some problems.
Modern internet security (online banking, encrypted messaging) relies on certain mathematical problems being hard to solve but easy to verify — precisely the P vs NP distinction. If it turned out that P=NP, and moreover that the fast solving method were practical (not just theoretically fast), most of today's encryption could potentially be broken efficiently — an outcome with enormous real-world consequences well beyond pure mathematics.
A problem is in class P ("polynomial time") if there exists an algorithm solving it in time bounded by some polynomial in the input size — O(nᵏ) for some fixed k (see the Big-O Notation entry). This is the standard mathematical formalisation of "efficiently solvable."
A problem is in class NP ("nondeterministic polynomial time") if, for any input with a "yes" answer, a proposed solution (a "certificate") can be verified in polynomial time — even if no known method can efficiently find that certificate in the first place. Every problem in P is automatically also in NP (if you can solve it quickly, you can certainly also just quickly re-derive and check the answer) — so P is a subset of NP. The open question is whether this containment is strict.
Stephen Cook (1971) and, independently, Leonid Levin, identified a special class of problems within NP called NP-complete: problems that are, in a precise technical sense, at least as hard as every other problem in NP. If even a single NP-complete problem could be solved in polynomial time, then P=NP would follow immediately, since every NP problem can be efficiently transformed ("reduced") into an NP-complete one. Richard Karp (1972) showed 21 diverse practical problems were all NP-complete, launching an enormous ongoing catalogue that now includes thousands of important problems across nearly every field of applied mathematics and computer science.
Cook's original 1971 NP-complete problem was SAT: given a logical formula built from AND, OR, and NOT operations on boolean (true/false) variables, does some assignment of true/false values to the variables make the whole formula true? This deceptively simple-sounding logical puzzle turns out to be exactly as hard as the hardest problems in all of NP.
Several rigorous "barrier" results explain why P vs NP has resisted proof for over 50 years, by showing that entire broad classes of proof techniques cannot possibly resolve it. Relativisation (Baker, Gill, and Solovay, 1975) showed that techniques treating computation as a "black box" cannot settle the question, since such techniques give contradictory answers when applied to modified (oracle) versions of the problem. Natural proofs (Razborov and Rudich, 1994) showed that an entire broad family of combinatorial lower-bound techniques cannot work, under a plausible cryptographic assumption — ironically suggesting that proving P≠NP might itself require techniques that, if too broadly applicable, would contradict standard cryptographic hardness assumptions.
Modern public-key cryptography (including RSA encryption, the basis of most secure internet communication) relies on the assumed hardness of certain specific NP problems (like integer factorisation, though factorisation itself is not known to be NP-complete). While a proof that P=NP would not automatically break cryptography (the fast algorithm might still be impractically slow in practice despite being "polynomial" in the formal sense), it would represent very strong theoretical evidence against the security assumptions underlying essentially all current internet security infrastructure.
A problem is NP-hard if it is at least as hard as every problem in NP, whether or not it is itself in NP (the halting problem — see the Gödel's Incompleteness Theorems entry for the related concept of undecidability — is NP-hard but not in NP, since it isn't even decidable at all, let alone quickly verifiable). The full landscape of complexity classes extends vastly beyond just P and NP, including PSPACE, EXPTIME, and many others, with P vs NP serving as the most famous single question within an enormous and still largely unmapped hierarchy of computational difficulty.
A 2019 survey of complexity theorists found the overwhelming majority believe P≠NP, largely because of the sheer scale of failed attempts to find fast algorithms for NP-complete problems across nearly 50 years of intense effort from many brilliant researchers. However, mathematics has produced genuine surprises before (see the Kepler Conjecture entry's centuries-long resistance, or Gödel's own incompleteness results defying prior expectations), and several serious mathematicians have cautioned that intuition built from failure-to-disprove is not the same as an actual mathematical proof — Donald Knuth has voiced measured skepticism about the field's confidence, illustrating that this remains a genuinely, formally open question in the strictest sense despite the strong consensus.