Limits of Computation

Computer technology has advanced at a pace unprecedented by other technologies. Although such achievements have transformed the human experience, they have also fueled misconceptions about the limits of computation itself. From a popular perspective, the scope of problems that can be solved by computers may seem unlimited. In reality, computers are limited by several factors—some contingent and others more fundamental.

Contingent limitations apply to the current state of computer technology. Actual computers are artifacts of engineering; as such, they are subject to certain physical limitations and may lack sufficient resources (e.g., speed, memory) to solve certain problems. For example, to list all possible partitions of 100 countries into two even halves (the city partition problem) would require at least 2100 steps, which would take more than 30 trillion years on a computer at the speed of 1 billion steps per second. Note that this is a problem that is solvable by computers in principle but that we just cannot afford the waiting time given the speed of the current computers. Moreover, further improvement in computer power does not seem to help much. For example, even with the computer speed improved by 1,000 times, the city partition problem still would require more than 30 billion years of computer time.

Other contingent limitations apply to our current knowledge of computer algorithms. Computer algorithms have been a very active research area in computer science. Many powerful algorithmic techniques have been developed during the past four decades. For example, now it is a trivial task using computers to schedule a minimum cost trip from a given city to another given city (the shortest path problem). The problem on a map of 100 cities takes a computer only miniseconds. This algorithm has been used very popularly by travel agents. On the other hand, if we add the condition that the tour must pass through all cities on the map (the traveling salesman problem), a seemingly moderate condition, the problem becomes much more difficult. The problem is solvable in principle; we can simply enumerate all possible such tours and pick the one with the minimum cost. However, such an enumerating algorithm would take more than 2100 steps on a computer, and this, as already[Page 278] calculated for the city partition problem, would require an unaffordable waiting time.

On the other hand, in spite of much effort by computer scientists and mathematicians over the past four decades, no one has been able to develop an algorithm for the traveling salesman problem that is essentially better than the trivial enumerating algorithm. Therefore, currently no known computer program is able to solve the problem in a practical manner. Note that the traveling salesman problem is different from the city partition problem; the 2100 computer steps are necessary for solving the city partition problem, whereas much faster computer algorithms might exist for the traveling salesman problem but simply have not been discovered yet. During the past 40 years of research in a variety of areas in computer science, a class of more than 1,000 problems, all similar to the traveling salesman problem, has been identified. It is known that if any of these problems can be solved efficiently, all problems in the class can be solved efficiently using a technique of problem reductions. On the other hand, many of these problems have been studied for decades, and no efficient algorithms have been found for any of them. Thus, it is natural to conjecture that no efficient algorithms exist for these problems and that all of the problems in the class are computationally intractable. These problems have been named NP-complete problems. Many important computational problems in a large variety of areas are known to be NP-complete. Studying NP-completeness has been central in the research in theoretical computer science.

...