Quick to check, quick to solve?
The P versus NP problem asks whether every problem whose proposed solution can be checked quickly can also be solved quickly from scratch — where quickly means in an amount of time that grows only polynomially with the size of the problem, rather than exponentially. Stephen Cook formally stated this question in a 1971 paper, and Leonid Levin arrived at an equivalent formulation independently in 1973, working from a different angle focused on search rather than yes-or-no decision problems. Neither paper claimed to answer the question; Cook’s central result was narrower and, in a sense, more useful than an answer — it showed that one specific problem, Boolean satisfiability, could stand in for the entire class of NP problems, so that solving satisfiability quickly would be enough to solve all of them quickly.
One problem standing for all of them
The Cook-Levin theorem proceeds by translating any problem in NP, together with the polynomial-time process used to verify a proposed solution to it, into a Boolean logic expression — a formula built from variables that are either true or false. Cook’s construction, for a nondeterministic verification process taking polynomial time, produces such an expression that is satisfiable exactly when the original problem has a solution, using a number of variables and logical clauses that itself grows only polynomially with the size of the problem. That is what makes the reduction meaningful rather than a trick: because the translation itself runs in polynomial time, a fast method for solving satisfiability would translate directly into a fast method for solving any NP problem at all, without exception.
A category of thousands, unsolved by any
The Cook-Levin theorem itself is settled mathematics, not a conjecture: satisfiability is definitively proven to be NP-complete, and Richard Karp’s 1972 follow-up work, showing twenty-one further problems reducible to satisfiability in the same way, established NP-completeness as a genuine and populated category rather than a one-off curiosity. Over three thousand problems are now known to be NP-complete by this kind of reduction, spanning scheduling, graph theory, logistics and cryptography, and not one of them has ever been solved by a general polynomial-time algorithm despite decades of effort directed at many of them individually. That consistent failure to find a fast algorithm for any NP-complete problem, across thousands of independent attempts on different specific problems, is itself treated as meaningful evidence, even though it falls short of proof.
Proof techniques that provably can’t work
What has not been achieved, despite over three thousand claimed proofs collected between 1986 and 2016, is an actual resolution of the question either way — every one of those attempted proofs has been found flawed. The material also records that several general proof strategies mathematicians tried, including relativizing, natural, and algebrizing proofs, have each been shown incapable of resolving the question, meaning the difficulty is not simply that no one has been clever enough yet but that whole categories of proof technique are provably insufficient. It would therefore be wrong to treat expert confidence that P does not equal NP, however widely shared, as equivalent to a proof: a 2018 poll found the large majority of surveyed researchers believing P and NP are unequal, but a belief held by nearly everyone in a field is still not the same thing as a demonstrated result.
Why encryption depends on the answer staying no
The practical stakes are concrete rather than abstract, because modern cryptography depends on certain problems being hard to solve but easy to verify — the definitional shape of an NP problem. If P were shown to equal NP, the material notes this would threaten to break widely used encryption systems, since the codebreaking problem those systems rely on being intractable would turn out to be solvable quickly after all; it also notes the more constructive possibility that mathematical proof itself could become substantially automatable, since Kurt Gödel had already observed that a fast general method for finding proofs would let a machine replace much of a mathematician’s work. That the question remains open is precisely why current encryption is considered secure and why P versus NP carries a one-million-dollar Millennium Prize rather than being treated as a settled matter of only theoretical interest.
Fifty years unresolved, and that’s the point
Worth engaging with for anyone curious why one of the seven Millennium Prize Problems has resisted solution for over fifty years despite enormous attention: the appeal here is not a satisfying resolution, since there isn’t one, but understanding exactly what has and hasn’t been proven, which is a more interesting and more honest story than most popular accounts of the problem convey. The Cook-Levin theorem is the part that is genuinely settled and worth understanding on its own terms, since it explains why a huge, seemingly unrelated set of practical problems are all, in a precise sense, the same problem in disguise. Anyone expecting an answer to whether P equals NP will not find one here or anywhere else yet — that remains the entire point.