Read more: āIn with the New ŠÓ°ÉŌ““: Our predictions for 2011ā
A draft solution to the so-called āP versus NPā problem generated excitement in 2010 ā will 2011 bring a correct proof?
Advertisement
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 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
Read more: āIn with the New ŠÓ°ÉŌ““: Our predictions for 2011ā
