Checking a Sudoku is easy, but nobody knows whether solving one must be hard
Hand someone a filled-in Sudoku and they can confirm it in moments by scanning rows, columns and boxes. Whether a fast method exists to solve every enlarged version of the puzzle is unknown. That gap, between checking an answer and finding one, is the P versus NP problem, worth a million dollars to whoever settles it.
In computer science, quickly means in polynomial time: the steps needed grow no faster than some power of the input's size, rather than exploding exponentially. P is the class of yes-or-no questions that can be answered that fast. NP is the class whose yes answers can be verified that fast when someone supplies a candidate. Every P problem is in NP. The open question is whether the reverse holds. Stephen Cook stated it precisely in 1971, and Leonid Levin independently in 1973.
Hints came earlier. In 1955 John Nash wrote to the National Security Agency suggesting that cracking a sufficiently complex code would take time growing exponentially with key length, which, if proved, would mean P and NP differ. A year later Kurt Gödel asked John von Neumann in a letter whether proving theorems could be done in linear or quadratic time, noting that if so, mathematical discovery could be automated.
The key tool is NP-completeness. An NP-complete problem is one to which every NP problem can be translated efficiently, so a fast solution to any one of them would crack them all. Boolean satisfiability was the first natural example, shown by the Cook–Levin theorem, and a chain of such translations links it to generalised Sudoku, Latin squares and a vast family of practical problems that are, in a sense, the same problem. No fast algorithm is known for any.
Most researchers expect the classes to differ. William Gasarch's polls found 61 percent believed P is not NP in 2001, rising to 88 percent in 2018, with 99 percent among experts; opinion, though, proves nothing. The Clay Mathematics Institute lists it among its seven Millennium Prize Problems, and a proof either way would ripple through cryptography, artificial intelligence, economics and philosophy. Some problems are already known to lie outside P, such as finding a perfect strategy in chess on an arbitrarily large board.
Source: P versus NP problem
