Thank you for visiting this site. This article covers computer science’s greatest unsolved problem: “P versus NP.”
Solving a sudoku is hard work, but double-checking someone’s claimed solution takes a moment. Assembling a jigsaw puzzle is a struggle, but comparing the finished result to the box photo takes one glance. Push this everyday intuition to its limit and you arrive at an outrageous question: “Could every problem whose answer can be checked in an instant actually be solved in an instant too?” Surely not, you think. And yet no one has ever proven that “surely not.” This is the P vs NP problem, and its resolution carries a one-million-dollar prize.
“Solving” and “Checking” Are Different Jobs
The star of P vs NP is the idea of measuring a problem’s “hardness.” Computer science measures hardness by how computation time grows as the problem scales up.
P is the collection of problems whose computation time grows only at a realistic pace as they scale. Multiplication, sorting, finding the shortest route on a map: make these 10 times bigger and the time grows only gently. They are called “efficiently solvable.”
NP is the collection of problems where, given a candidate answer, you can efficiently check whether it is correct. Sudoku is the classic example: as the grid grows, solving becomes brutally harder, but verifying a filled-in board finishes quickly.
The key point: any problem that can be solved efficiently can certainly be checked efficiently (solve it yourself, then compare). So P is contained in NP. The question is the reverse direction. “Is every problem that’s fast to check also fast to solve?” In other words, are P and NP the same thing, or genuinely different? That is the entire text of the P vs NP problem.
1971: The Discovery That Problems Have a “King”
The question entered mathematics proper with Stephen Cook’s 1971 paper (Leonid Levin in the Soviet Union made the same discovery independently). What Cook proved was astonishing.
Among the problems in NP there exists a universal problem such that, if you could solve just that one efficiently, you could solve every problem in NP efficiently. Problems of this kind are called “NP-complete.” The first problem proven NP-complete was the logical-consistency puzzle known as the satisfiability problem.
The following year, 1972, Richard Karp showed that 21 famous real-world problems were all NP-complete. The list has grown ever since; today thousands of problems are known to be NP-complete. Some examples:
- The traveling salesman problem: what is the shortest route visiting every city?
- The knapsack problem: which combination of items maximizes value within a capacity limit?
- Timetabling: does an assignment of classes exist satisfying every constraint?
- Sudoku (generalized): does an n×n sudoku have a solution?
NP-complete problems form a fellowship of mutual translation, bound to a common fate. Find an efficient algorithm for any one of them, and they all fall together — P=NP is settled. Prove any one of them unsolvable efficiently, and they all stand unconquerable — P≠NP is settled. Thousands of problems holding hands at the edge of the same cliff: the vividness of that picture is what makes P vs NP special.
To head off a misunderstanding: NP-complete does not mean “hopeless in practice.” Programs called “SAT solvers,” which attack that first NP-complete problem of logical consistency, routinely solve real instances with millions of variables — worst-case theory notwithstanding — and do real work in chip design verification and software testing. Why the theoretical worst case and the practical typical case diverge this much is, in fact, not well understood either. In this field, small mysteries pile up at the feet of the big one.
How Would P=NP Change the World?
Most unsolved problems, even solved, would leave daily life untouched. P vs NP is different — it is said to be a problem where the answer changes the landscape of civilization, with direct practical stakes.
If P=NP were proven (with a practical algorithm attached), then first, public-key encryption on the internet collapses. Today’s cryptography stakes its security on computations that are “easy to check but effectively impossible to crack” — and in a P=NP world, “effectively impossible” evaporates.
The windfalls, meanwhile, would be equally staggering. Optimal logistics routes, protein design in drug discovery, factory scheduling — the NP-complete problems of industry would all become efficiently solvable. Stranger still, since “verifying a theorem’s proof can be done mechanically,” it would follow that machines could efficiently discover any mathematical theorem with a short proof — raising serious discussion that part of mathematicians’ creativity would reduce to computation.
So which way do the experts lean? In surveys of researchers, more than 80 percent expect P≠NP — the view that “fast to check does not mean fast to solve; genuinely hard problems exist.” It fits everyday intuition, plus the rule of thumb that if P=NP were true, someone would surely have stumbled on the magic algorithm by now. And yet: no proof. In being “a piece of common sense everyone believes, with no proof,” it stands shoulder to shoulder with the Riemann hypothesis.
The “Proofs of Walls” That Block the Proofs
The delicious twist of P vs NP is that “why we cannot prove it” has itself become a subject of research — and of theorems.
After an era of vigorous proof attempts, researchers noticed something odd. The promising proof techniques shared common templates — and for each template, it was proven, as a theorem, that techniques of that type cannot, in principle, resolve P vs NP. These results — the relativization barrier, the natural proofs barrier, and others — are, in effect, signs at the trailhead reading “this mountain cannot be climbed with this equipment.”
So the current state is not merely that the mountain is high: nearly every known route has a proven roadblock standing on it. A resolution is believed to require genuinely new mathematics fitting none of the existing templates. Among the seven Clay Millennium Prize Problems, P vs NP is often rated “the furthest from solution.”
To me, this accumulation of impossibility proofs is the most science-fictional scenery in the genre. Humanity cannot solve the problem — but can prove “it cannot be solved this way.” The self-referential power and eeriness of mathematics, distilled.
Could a Quantum Computer Settle It?
Can’t Supercomputers or Quantum Computers Solve This?
No. P vs NP asks not “does a fast machine exist” but “does a fast procedure (algorithm) exist” — a mathematical question that hardware progress cannot settle. As for quantum computers: they are known to speed up certain problems like integer factoring, but factoring is not believed to be NP-complete, and quantum computers are not expected to solve NP-complete problems efficiently. Treat headlines like “quantum computing resolves P vs NP” with caution.
How Does Industry Cope with NP-Complete Problems?
By giving up on head-on optimality and making peace. Concretely, three pillars: approximation algorithms that settle for “good enough,” heuristics that run fast on real-world inputs, and solvers that brute-force smaller instances. Car navigation, logistics, and factories all run on this technology of compromise. NP-complete means not “absolutely unsolvable” but “intractable if you demand the exact optimum in the worst case” — confuse the two and practical conversations stop making sense.
How Do I Claim the Million Dollars?
Proving either P=NP or P≠NP qualifies. Under the Clay Mathematics Institute’s Millennium Prize rules, the proof must be published in a recognized journal and withstand the mathematical community’s scrutiny for two years. Papers claiming a proof appear nearly every year and crumble under expert review — there is even a website chronicling the attempts. Anyone is free to try, but starting with one good textbook on NP-completeness is, though it looks like a detour, the true shortcut.
Related Unsolved Problems and Puzzles
See the fellow Millennium Prize Problem “the Riemann hypothesis,” the limits of computation and infinity in “Cantor’s diagonal argument,” and a hands-on taste of NP-style search in “the zebra puzzle.”
Summary
This article covered “the P vs NP problem.”
It starts from the everyday feel of checking a sudoku or eyeballing a jigsaw, and the stakes pile up to the fate of encryption and the future of mathematics. In the gap between how low the doorway is and how much is wagered inside, I think it ranks near the top of all unsolved problems.
“Are solving and checking fundamentally different activities?” Before computers existed, this was not even a mathematical question. As a mystery that became visible only once humanity built calculating machines, P vs NP is the youngest and most modern problem in the unsolved canon.
To return to the full list of unsolved problems, follow the link below.
Thank you for reading. We hope to see you in the next article.
📚 Series: Unsolved Problems in Math & Science (8/16)
