Algorithmics - The Computing Universe: A Journey through a Revolution - page 100

The noncomputable

Fig. 5.19. This igure from David Harel's topic shows the main problem categories: noncomputable
problems have no algorithmic solution. Algorithms for intractable problems do exist but only with
exponential or higher order of complexity: tractable problems can be solved with polynomial time
algorithms.

The intractable

The tractable

transformation between the two problems takes only a polynomial amount of
time, this leads to the claimed result.
We can now see the significance of the title of this section. Figure 5.19
shows how we can divide the world of algorithmic problems into tractable,
intractable, and, as we shall see in the next chapter, noncomputable problems.
The tractable problems are in the class P and have polynomial time solutions;
the intractable problems do not have reasonable polynomial time algorithms.
The location of the NP-complete problems is unknown. The question arose
from the work of the complexity theorists Steven Cook ( B.5.7 ), Leonid Levin
( B.5.8 ), and Richard Karp ( B.5.9 ) in the early 1970s. Despite more than thirty
years of work by computer scientists, the question of whether P = NP is still
unresolved.

Algorithmics and computability

Numerical simulations of complex physical systems are still a major appli-
cation area for today's computers. For problems that are very complex, such
as weather forecasting or global climate modeling, scientists need to use the
fastest, most expensive machines - supercomputers with multiple processors.
However, we have also seen how computers can be used to address a variety of
different types of problems, from sorting to graph problems. It is here that we
have seen the need to use clever algorithms that enable us to solve these prob-
lems as quickly as possible. But we have also seen that there are some problems

B.5.8. Leonid Levin discovered the
class of NP-complete problems inde-
pendently from Stephen Cook.

B.5.9. In 1972 Richard M. Karp wrote a groundbreaking paper, “Reducibility among Combinatorial
Problems,” in which he identified twenty-one combinatorial problems belonging to the class of
NP-complete problems that can be reduced to a common problem - the so-called satisfiability
problem. In 1985 he received the Turing Award for his contribution to algorithmic research.