麻豆传媒

The biggest problem in computer science remains unsolved, but researchers are more confident than ever about what the answer should be. A new poll reveals opinions on the P versus NP problem, the solution of which will answer fundamental questions about computation聽 鈥� and earn the solver $1 million.

Computer scientists group problems according to how much time the problems take to solve. P is the class of 鈥渆asy鈥� problems that can be solved by an algorithm in a relatively short time. NP is the class of problems that are easy to check聽 鈥� if you are given an answer, you can verify it in a short time.

All problems in class P are also in NP, but it isn鈥檛 known whether all NP problems are also in P.

If they are, then P聽=聽NP, with potentially wide-ranging consequences. With the right algorithm, all NP problems could be solved rapidly, including a variety of real-world issues. An example is the travelling salesman problem, finding the shortest route that visits a list of cities just once each, crucial in the field of logistics. Otherwise, P聽鈮犅燦P and many problems are fundamentally difficult to solve. A proof either way is worth from the Clay Mathematics Institute in Cambridge, Massachusetts.

Survey says

In 2002, , a computer scientist at the University of Maryland in College Park, polled 100 researchers on the question, and 61 per cent thought P聽鈮犅燦P. Just 9 per cent believed the opposite, with the rest saying that they didn鈥檛 know or that the problem was impossible to solve. Now Gasarch has re-run the poll with more than 150 respondents and discovered that P聽鈮犅燦P supporters are up to 81 per cent.

An attempt at proving P聽鈮犅燦P hit the headlines in 2010, but turned out to be faulty. Gasarch says this is unlikely to have influenced people鈥檚 opinions, but it did get them talking about the problem. Instead, the shift may be because, despite another 10 years of effort, computer scientists have failed to find a fast algorithm that would let them solve all NP problems.

Either way, we may have a long wait for a proof. In the earlier poll, 62 per cent of respondents said an answer would emerge before 2100, but that has now shrunk to 53 per cent. Gasarch believes that P聽鈮犅燦P and a proof will take 200 to 400 years. The full poll results will be published in the Association for Computing Machinery鈥檚 Special Interest Group on Algorithms and Computation Theory later this year.