The second question is known as P versus NP. It was posed precisely by Stephen Cook in 1971, and remains an open problem today. It asks what problems can be solved by computers in a reasonable amount of time, where reasonable means that the time required to solve the problem does not grow exponentially with the size of the input (that is, when the input size increases by one, the amount of work to solve the problem does not multiply). Many interesting problems such as finding the shape of a protein, determining the best schedule for using a resource, finding the minimum number of colors needed to color a map, and winning the pegboard puzzle game, are deeply equivalent — a reasonable-time solution to any one of these problems can be used to also solve all of the other problems. What is not known, however, is whether all of the problems can be solved quickly, or none of them can. The question boils doing to determining if an omnipotent machine that can always guess the correct move at every step is able to solve problems significantly faster than a machine without this magical power. Although it seems obvious that omnipotence should help, we are surprisingly far away from being able to answer this question satisfactorily.
No comments:
Post a Comment