作者：韩硒梏 发布时间：2019-03-01 03:06:08

By Jacob Aron 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 “easy” 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’t 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 ≠ NP and many problems are fundamentally difficult to solve. A proof either way is worth $1 million from the Clay Mathematics Institute in Cambridge, Massachusetts. In 2002, William Gasarch, a computer scientist at the University of Maryland in College Park, polled 100 researchers on the question, and 61 per cent thought P ≠ NP. Just 9 per cent believed the opposite, with the rest saying that they didn’t 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 ≠ NP supporters are up to 81 per cent. An attempt at proving P ≠ NP hit the headlines in 2010, but turned out to be faulty. Gasarch says this is unlikely to have influenced people’s 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 ≠ NP and a proof will take 200 to 400 years. The full poll results will be published in the Association for Computing Machinery’s Special Interest Group on Algorithms and Computation Theory newsletter later this year. More on these topics:

Copyright © 网站地图