The P versus NP problem asks whether problems whose solutions can be quickly verified can also be quickly solved, and proving either answer would have profound implications—from breaking all modern encryption to solving previously intractable problems like cancer research and world hunger.
The P versus NP problem is one of seven Millennium Prize Problems designated by the Clay Mathematics Institute in 2000, each carrying a $1 million prize for the first correct solution. Stephen Cook formalized the notions of polynomial-time reduction and NP-completeness in his seminal 1971 paper "The Complexity of Theorem Proving Procedures," proving that the Boolean satisfiability problem (SAT) is NP-complete. This theorem was proven independently by Leonid Levin in the Soviet Union. In 1955, mathematician John Nash wrote a letter to the National Security Agency speculating that the time required to crack a sufficiently complex code would increase exponentially with the length of the key. If proved (and Nash was skeptical), this would imply what is now called P ≠ NP, since a proposed key can be verified in polynomial time.
The problem informally asks whether every problem whose solution can be quickly verified can also be quickly solved. Here, "quickly" means an algorithm exists that solves the task and runs in polynomial time, meaning the task completion time is bounded above by a polynomial function on the size of the input to the algorithm. SAT is the first problem that was proven to be NP-complete—this is the Cook–Levin theorem. This means that all problems in the complexity class NP, which includes a wide range of natural decision and optimization problems, are at most as difficult to solve as SAT. Richard M. Karp showed in 1972 that the Hamiltonian cycle problem was NP-complete, which implies the NP-hardness of TSP. This supplied a mathematical explanation for the apparent computational difficulty of finding optimal tours.
No polynomial-time method for factoring large integers on a classical computer has yet been found, but it has not been proven that none exists. Currently, if n has a minimum of 1024 bits, no technique currently exists that can factor n in polynomial time. A solution showing P = NP could upend the field of cryptography. A constructive and efficient solution to an NP-complete problem such as 3-SAT would break most existing cryptosystems including existing implementations of public-key cryptography. If P = NP, then finding a pre-image that hashes to a given value can take polynomial time, through reduction to SAT. There are enormous benefits that would follow from rendering tractable many currently mathematically intractable problems. Many problems in operations research are NP-complete, such as types of integer programming and the travelling salesman problem. Efficient solutions to these problems would have enormous implications for logistics. Many other important problems, such as some problems in protein structure prediction, are also NP-complete; making these problems efficiently solvable could considerably advance life sciences and biotechnology.
The P versus NP problem asks whether every problem whose solution can be quickly verified can also be quickly solved—a question that could either break all encryption or revolutionize fields from medicine to logistics.