By Gemma Penson and Danny Leboff - Computer Science Students @ Trinity Hall, Cambridge
In 2000, the Clay Mathematics Institute announced the Millennium Prize problems. These were a collection of seven significant but unsolved mathematical problems which each carried a US $1,000,000 prize for the first correct solution. In 2003, one of these problems - a proof related to a shape known as a glome - was solved but mathematician Griogori Perelman declined the prize money. Today, the remaining six problems are still unsolved with one of these being known as P vs NP.
How long would it take you to solve a sudoku puzzle? Most people would say somewhere between 10 minutes and an hour depending on difficulty. But how long would it take you to verify that a given filled-in grid is a correct solution? One or two minutes at the most, I’d say. At its core, the P vs NP problem asks if it takes the same ‘amount’ of time to verify a solution as it does to find the solution.
Formally, P is defined as the set of all decision problems that can be solved by a Turing machine (specifically, a deterministic Turing machine) in polynomial time. Polynomial time is referring to the time complexity of the algorithm, defined as the rate at which the runtime of the algorithm increases with respect to the size of the input. For example, if we have a list of N integers, we can sort the list in Nlog2N time (e.g. using merge sort). That means the runtime of the sorting algorithm increases at a rate of Nlog2N as the number of integers in the list increases linearly. NP, on the other hand, is defined as the set of all decision problems that can be verified, instead of solved, by a (deterministic) Turing machine in polynomial time.
The problem of P vs NP asks if these two sets are equal, i.e. are all problems in P also in NP and are all problems in NP also in P. We know the former to be true (we could verify a problem by simply solving it ourselves, hence all problems in P are in NP), but the million dollar question is about the latter. Can we solve a problem as quickly as we can verify its solution?
A proof that P ≠ NP would be inconsequential for society as we have been living in a world where we assume that result by default. However, a proof that P = NP would have a significant impact on both theoretical computer science and wider society. A proof would lead to the groundbreaking ability to compute certain exponentially difficult tasks in much less time than can be done at the moment. This could lead to breakthroughs in other disciplines such as medicine (as we’d be able to create easily-produced personalised cancer drugs), artificial intelligence, and logistics. This last issue could be solved thanks to a polynomial-time solution to problems like the Travelling Salesperson problem, discussed in another Oxbridge Intelligence article linked below.
Even 20 years after the million dollar question was announced, there is still uncertainty around the timescale and solution of this problem. In a 2019 poll conducted by computer scientist Lane A. Hemaspaandra, 84 respondents anticipated a solution before 2100 compared with 58 expectations for a solution after 2100, in a long time or even never. In the same poll, 88% believed that the solution was P ≠ NP with a minority 12% believing that P = NP.
As scientists and mathematicians alike solve larger and more complex problems, those
that continue to be unsolved become evermore important. The 2012 film titled Travelling Salesman was based solely on this Millennium Prize problem and research into this exciting research area is constantly ongoing. Its solution will bring fame and fortune to whomever is able to solve it and its answer may revolutionise practices across a vast array of professionals.
“People like to describe it as ‘probably the central unsolved problem of theoretical computer science.’ That’s a comical understatement. P vs NP is one of the deepest questions that human beings have ever asked.” - Scott Aaronson
Further reading:
2021. P vs NP Problem. Clay Mathematics Institute. Available at: <https://www.claymath.org/millennium-problems/p-vs-np-problem>
2017. Fortnow, Lance. Princeton: Princeton University Press. "The Golden Ticket," in The Golden Ticket: P, NP, and the Search for the Impossible. Page 14.
2013. Scott Aaronson. "P, NP and Friends". Quantum Computing Since Democritus. Cambridge University Press. Page 56.
2019. Hemaspaandra, Lane A. University of Rochester. SIGACT News Complexity Theory Column 100. Available at: <https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/pollpaper3.pdf>