What is P vs NP? The biggest open question in computer science

P vs NP is the question of whether every problem whose answer can be checked quickly can also be solved quickly. P is the class of problems a computer can solve fast; NP is the class whose proposed answers it can check fast. Everything in P is in NP. Whether the two are the same class has been open since 1971, and in November 2026 it remains unsolved.

In short

• P means solvable in polynomial time, fast in a precise sense; NP means a proposed answer can be checked in polynomial time.
• Thousands of practical problems, called NP-complete, stand or fall together: a fast method for any one of them would give a fast method for all of NP.
• Most experts polled believe P is not equal to NP, but nobody has proved it either way, and a $1 million prize waits for whoever does.

What do P and NP actually mean?

Both are about how the work grows as a problem gets bigger, measured the way Big O notation measures it. A problem is in P if some algorithm solves it in polynomial time: a number of steps like n², or n³, where n is the size of the input. Sorting a list, finding the shortest route between two places on a map, and checking whether a number is prime are all in P.

A problem is in NP if, when someone hands you a proposed answer, you can check it in polynomial time. The name is a common trap. NP stands for "nondeterministic polynomial time", not "not polynomial": it comes from an imaginary machine that could guess the right answer and then only needs to check it, a variant of the Turing machine. Every problem in P is in NP, because if you can solve it fast you can check an answer by solving it yourself. The open question is whether the reverse holds. As the Clay Mathematics Institute puts it: "If it is easy to check that a solution to a problem is correct, is it also easy to solve the problem?"

Why is checking easier than solving? A Sudoku example

A finished 9 × 9 Sudoku is easy to check. There are 27 groups, 9 rows, 9 columns and 9 boxes, and each must hold the digits 1 to 9 once. That is 27 groups of 9 cells, 243 cell checks, and you are done. Make the grid 16 × 16 or 100 × 100 and checking grows only with the number of cells.

Solving is different. A 9 × 9 puzzle is small enough for computers to crack in moments, but the general puzzle, on n² × n² grids, is NP-complete, which means no method is known that stays fast as the grid grows. A solver fills in a guess, follows its consequences, and backs up when it hits a contradiction, and in the worst case the number of guesses to try grows exponentially. The gap between a few hundred checks and an exponential search is the gap P vs NP asks about.

What does NP-complete mean?

NP-complete problems are the hardest problems in NP, in a precise sense: every problem in NP can be translated into any one of them, with only polynomial extra work. In 1971 Stephen Cook showed the first one, a logic puzzle called Boolean satisfiability; Leonid Levin found the same idea independently in the Soviet Union. In 1972 Richard Karp showed 21 well-known problems were NP-complete, and thousands more have followed, in scheduling, chip design, protein folding models and packing.

The traveling salesperson problem shows the stakes. A delivery driver must visit n cities once each and return home by the shortest route. Its yes-or-no version, "is there a route shorter than 1,000 km?", is NP-complete: given a route, adding up its length is quick. Finding one by trying every route is hopeless, because a round trip through n cities has (n − 1) × (n − 2) × … × 2 × 1 ÷ 2 possible orders: every whole number from 1 to n − 1 multiplied together, then halved, because a route and its reverse are the same length.

Cities	Possible round trips	Time to try all, at 1 billion a second
10	181,440	Under a thousandth of a second
20	about 61 million billion	About 2 years
25	about 310 billion trillion	About 10 million years

Cleverer methods than brute force exist, and real software routinely finds the best tour through thousands of cities. But every known method that always finds the best tour still takes exponential time in the worst case. If anyone found a polynomial-time method for one NP-complete problem, every problem in NP would become polynomial: P would equal NP.

Why would P = NP break encryption?

Because most of today's encryption relies on problems that are easy to check and believed hard to solve. Breaking a key means finding a secret that, once found, is quick to verify, which puts the attack in NP. Stephen Cook's official problem description for the Clay Institute puts it plainly: if P = NP, the assumptions behind internet security "are all false", and an algorithm solving 3-SAT, a form of satisfiability, in n² steps "could be used to factor 200-digit numbers in a few minutes". Factoring large numbers is what keeps RSA, one form of public key cryptography, secure.

Two cautions keep this honest. A proof that P = NP might give an algorithm that is polynomial but useless in practice, taking n¹⁰⁰ steps, so the consequences would depend on how it was proved. And a proof that P ≠ NP would not, by itself, make encryption safe: cryptography needs problems that are hard on typical inputs, not only in the worst case, and factoring isn't known to be NP-complete at all. Even quantum computers, which could factor fast, are not believed to solve NP-complete problems quickly.

There would be an upside too. Cook's paper notes that a practical method would let computers find a proof of any theorem with a reasonably short proof, since checking a written mathematical proof is easy.

Who is trying to solve it, and what is the prize?

In 2000 the Clay Mathematics Institute named P vs NP one of seven Millennium Prize Problems and set aside $1 million for each. In November 2026 its page still lists the problem as unsolved. Claimed proofs, in both directions, appear online regularly; none has survived expert checking. Part of the difficulty is known: researchers have shown that whole families of proof techniques, the ones that settled earlier questions, cannot by themselves resolve this one.

Still argued

Which way the answer goes is a matter of expert belief, not proof. In William Gasarch's 2019 poll, published in the computer theory newsletter SIGACT News, 109 of 124 respondents, 88%, said they believe P ≠ NP, up from 61% in 2002 and 83% in 2012; 15, or 12%, said P = NP. The reasons usually given for P ≠ NP are that decades of effort on thousands of NP-complete problems have found no fast method for any of them, and that a world where finding is as easy as checking seems too strange. Those who doubt it point out that surprising fast algorithms have turned up before, and that intuition is not a proof. Respondents also disagreed widely on when, or whether, it will be resolved.

Check yourself

• Without looking back, explain the difference between P and NP using Sudoku.
• Why does a fast method for one NP-complete problem give a fast method for all of NP?
• Give one reason a proof that P = NP might not break encryption in practice, and one reason a proof that P ≠ NP wouldn't guarantee it is safe.

Sources

• P vs NP — Clay Mathematics Institute
• The P versus NP problem, official problem description — Stephen Cook, Clay Mathematics Institute
• Millennium Prize Problems — Clay Mathematics Institute
• The third P =? NP poll — William Gasarch, SIGACT News, 2019
• P versus NP problem — Wikipedia