Does P equal NP?

The question

Solving a sudoku can take a long time; checking a filled-in grid takes a minute. Finding the factors of a huge number seems hopeless; checking that two given numbers multiply to it is trivial. For a great many problems, checking an answer is easy and finding it seems hard.

The question is whether this difference is real or only reflects our lack of cleverness. In computer science terms, P is the class of problems that a computer can solve quickly — in a time that grows reasonably, "polynomially", with the size of the problem. NP is the class of problems whose solutions can be checked quickly. Every problem in P is in NP. The question is whether the reverse holds: is every problem whose solution is easy to check also easy to solve?

What we know

The question was formulated precisely in 1971 by Stephen Cook, and independently by Leonid Levin in the USSR. Kurt Gödel had asked essentially the same thing in a 1956 letter to John von Neumann, a letter that was only found decades later.
Cook showed that some problems in NP are "hardest": any problem in NP can be translated into them. In 1972 Richard Karp showed that 21 well-known problems are of this kind, called NP-complete. Today thousands are known: scheduling, route planning, packing, protein folding models, even generalised versions of games like Tetris and sudoku.
They stand or fall together. A fast algorithm for any single NP-complete problem would give fast algorithms for all of NP.
Most researchers believe P ≠ NP. In a 2019 poll of computer scientists, almost nine in ten said so.
Three known "barriers" — relativization, natural proofs and algebrization — show that whole families of proof techniques cannot settle the question. Any successful proof must avoid all three.
Announced proofs appear regularly, in both directions. So far all have turned out to be wrong.

Main hypotheses

P ≠ NP, and the difficulty is real

This is the majority view. Decades of attempts by thousands of very capable people to find fast algorithms for NP-complete problems have failed, and the world looks as if searching is fundamentally harder than checking. Proving it, however, would require showing that no algorithm at all can succeed, including algorithms nobody has imagined yet. That is much harder than showing that known algorithms fail.

P = NP, but uselessly

A minority, including the respected computer scientist Donald Knuth, considers P = NP possible. But even then, the fast algorithm might be so enormous in practice, or its existence proved without showing how to build it, that nothing in the real world would change.

Independent of the axioms

Some think the question may not be decidable within standard mathematics at all. There is no strong evidence for this, but the barriers show how unusual a proof would have to be.

Where understanding ends

The core problem is that we can hardly prove that anything is hard. We know how to show that a problem can be solved quickly: give an algorithm. We have almost no tools for proving that no fast algorithm exists. For most natural problems we can't even rule out that they can be solved in linear time, simply by reading the input.

A second gap separates theory and practice. NP-completeness concerns the worst case, yet programs called SAT solvers routinely solve industrial instances of NP-complete problems with millions of variables. We don't fully understand why real-world instances are so often easy.

And there is a gap between P ≠ NP and security. Modern cryptography needs problems that are hard on average, for randomly chosen keys, not just in the worst case. Proving P ≠ NP would not by itself prove that encryption is safe. Factoring, the basis of RSA, isn't even known to be NP-complete.

What would settle it

A proof that P ≠ NP, which will almost certainly require a fundamentally new mathematical technique that passes all three barriers. Programmes such as geometric complexity theory aim at this, but are considered to be decades away from the goal.
A fast algorithm for any NP-complete problem, which would prove P = NP at once.
Proof that the question is independent of the standard axioms of mathematics.