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