MILLENNIUM PRIZE SERIES: The Millennium Prize Problems are seven mathematics problems laid out by the Clay Mathematics Institute in 2000. They’re not easy – a correct solution to any one results in a US$1,000,000 prize being awarded by the institute.
Russian mathematician Grigori Perelman was awarded the Prize on March 18 last year for solving one of the problems, the Poincaré conjecture – as yet the only problem that’s been solved. Famously, he turned down the $1,000,000 Millennium Prize.
Over the coming weeks, each of these problems will be illuminated by experts from the Australian Mathematical Sciences Institute (AMSI) member institutions.
Here, Marcel Jackson explains the P vs NP problem. Enjoy.
In the 1930s, Alan Turing showed there are basic tasks that are impossible to achieve by algorithmic means. In modern lingo, what he showed was that there can be no general computer program that answers yes or no to the question of whether another computer program will eventually stop when it is run.
The amazing unsolvability of this Halting Problem contains a further perplexing subtlety. While we have no way of finding in advance if a program will halt, there is an obvious way, in principle, to demonstrate that it halts if it is a halting program: run it, wait, and witness it halting!
In other words, Turing showed that, at the broadest level, deciding whether a statement is true is computationally harder than demonstrating that it’s true when it is.
A question of efficiency
Turing’s work was a pivotal moment in the history of computing. Some 80 years later, computing devices have pervaded almost every facet of society. Turing’s original “what is computable?” question has been mostly replaced by the more pertinent, “what is efficiently computable?”
But while Turing’s Halting Problem can be proved impossible in a few magical lines, the boundary between “efficient” and “inefficient” seems far more elusive. P versus NP is the most famous of a huge swathe of unresolved questions to have emerged from this modern take on Turing’s question.
So what is this NP thing?
Roughly speaking, P (standing for “polynomial time”), corresponds to the collection of computational problems that have an efficient solution. It’s only an abstract formulation of “efficient”, but it works fairly well in practice.
The class NP corresponds to the problems for which, when the answer is “yes”, there is an efficient demonstration that the answer is yes (the “N” stands for “nondeterministic”, but the description taken here is more intuitive). P versus NP simply asks if these two classes of computational problems are the same.
It’s just the “deciding versus demonstrating” issue in Turing’s original Halting Problem, but with the added condition of efficiency.
A puzzler
P certainly doesn’t look to be the same as NP. Puzzles are good examples of the general intuition here. Crossword puzzles are popular because it’s a challenge to find the solution, and humans like challenge. But no-one spends their lunchtime checking already completed crosswords: checking someone else’s solution offers nowhere near the same challenge.
Even clearer is Sudoku: again it is a genuine challenge to solve, but checking an existing solution for correctness is so routine it is devoid of entertainment value.
The P=NP possibility is like discovering that the “finding” part of these puzzles is only of the same difficulty to the “checking” part. That seems hard to believe, but the truth is we do not know for sure.
This same intuition pervades an enormous array of important computational tasks for which we don’t currently have efficient algorithms. One particularly tantalising feature is that, more often than not, these problems can be shown to be maximally hard among NP problems.
These so-called “NP-complete” problems are test cases for P versus NP: if any one of them has an efficient algorithmic solution then they all do (and efficient checking is no harder than efficient finding).
But if even just one single one can be shown to have no efficient solution, then P does not equal NP (and efficient finding really is, in general, harder than efficient checking).
Here are some classic examples of NP-complete problems.
Partition (the dilemma of the alien pick-pockets). On an alien planet, two pick-pockets steal a wallet. To share the proceeds, they must evenly divide the money: can they do it? Standard Earth currencies evolved to have coin values designed to make this task easy, but in general this task is NP-complete. It’s in NP because, if there is an equal division of the coins, this can be easily demonstrated by simply showing the division. (Finding it is the hard part!)
Timetabling. Finding if a clash-free timetable exists is NP-complete. The problem is in NP because we can efficiently check a correct, clash-free timetable to be clash-free.
Travelling Salesman. A travelling salesman must visit each of some number of cities. To save costs, the salesman wants to find the shortest route that passes through all of the cities. For some given target distance “n”, is there a route of length at most “n”?
Short proofs. Is there a short proof for your favourite mathematical statement (a Millennium Prize problem perhaps)? With a suitable formulation of “short”, this is NP-complete. It is in NP because checking formal proofs can be done efficiently: the hard part is finding them (at least, we think that’s the hard part!).
In every case, we know of no efficient exact algorithm, and the nonexistence of such an algorithm is equivalent to proving P not equal to NP.
So are we close to a solution? It seems the best we know is that we don’t know much! Arguably, the most substantial advances in the P versus NP saga are curiously negative: they mostly show we cannot possibly hope to resolve P as different to NP by familiar techniques.
We know Turing’s approach cannot work. In 2007, Alexander Razborov and Steven Rudich were awarded the Gödel Prize (often touted as the Nobel Prize of Computer Science) for their work showing that no “natural proof” can prove P unequal to NP.
Of course, we’ll keep looking!
This is the third part of the Millennium Prize Series. To read the other instalments, follow the links below.