A draft solution to the so-called "P versus NP" problem generated excitement in 2010 – will 2011 bring a correct proof?
Vinay Deolalikar made waves in August when his draft solution to a mathematical problem that haunts computer science hit the internet.
It's known as "P versus NP", and a correct solution is worth $1 million. Sadly for Deolalikar, of Hewlett-Packard Labs in Palo Alto, California, his work didn't check out. But the flurry of online activity surrounding the paper demonstrated a new way of doing mathematics - via blogs and wikis - and generated fresh excitement around the problem.
Formulated in 1971, P versus NP deals with the relationship between two classes of problems that are encountered by computers. P problems are relatively easy for computers to solve. But it can take an impracticably long time to solve NP problems, such as finding the shortest route between several cities - though it is easy to show whether a possible solution is correct.
If P = NP, computers may eventually be able to solve a host of complex problems, from protein folding to factorising very large numbers. The ability to solve the latter would spell trouble for algorithms that we rely on for internet security. Most people assume the opposite is true, that P ≠ NP; had Deolalikar's paper been correct, it would have proved this.
The Clay Mathematics Institute in Cambridge, Massachusetts, has promised $1 million to the first person who can prove it one way or the other. To find out how likely this is to happen in 2011, see "Prediction: Its time has not come".
Prediction: Its time has not come
Unlike many problems in science, highly theoretical enigmas like P versus NP are rarely solved piecemeal. Instead, they tend to remain unsolved for years and then, apparently out of nowhere, a proof that works pops up.
Predicting these breakthroughs might seem impossible, but we devised a way to estimate the likelihood of P versus NP being solved next year. We compared its "age", or the time since the problem was formulated, to other long-standing mathematical problems.
First we compared P versus NP with 18 mathematical problems, from Fermat's last theorem to the Poincaré conjecture, that were not solved until more than a decade after their "births" (see graph). This made arriving at a solution to P versus NP in 2011, when it will turn a sprightly 40, look premature: just 22 per cent of these other problems were solved before they turned 40. By the same logic, in 2024, we should be on the lookout for a solution to P versus NP. That's when it turns 53, the age by which 50 per cent of the problems we examined were solved.
Here's hoping that solving P versus NP turns out to be faster than proving the Honeycomb conjecture, which states that if you need to divide a surface into tiled shapes of equal size, a hexagon is the shape that requires the smallest length of dividing lines. Proving that took more than 1500 years.
We also compared P versus NP to 26 other problems that still haven't been solved. In 2011, it will be younger than 81 per cent of those. Samuel Arbesman and Rachel Courtland
- New Scientist
- Not just a website!
- Subscribe to New Scientist and get:
- New Scientist magazine delivered every week
- Unlimited online access to articles from over 500 back issues
- Subscribe Now and Save
If you would like to reuse any content from New Scientist, either in print or online, please contact the syndication department first for permission. New Scientist does not own rights to photos, but there are a variety of licensing options available for use of articles and graphics we own the copyright to.