For many important problems no polynomial time algorithms are known.
Many of them are *NP*-complete and therefore there is currently
little hope that a polynomial time algorithm can be found in the near
future (or ever). On the other hand, the problems *are*
important and have to be solved in practice. Theoretical computer
science provides a lot of possibilities to deal with hard problems:

- Approximation algorithms are fast, but provide only a nearly optimal
solution. There is, however, a guarantee how far the provided
solution is from optimal.
- Parameterized Algorithms are fast for some, but not all, instances
of a given problem. They can be very helpful for solving
practical problems whose cases that imply hardness do not
occur in practice.
- Exponential time algorithm can be used, if there exponential
grows starts moderately and the instances are not too big.
A 1.28
^{n} algorithm can be quite practical.

A good example for a hard problem is vertex cover. The input is a
graph and the task is to find a set of vertices that cover all edges.
In the following picture, the nodes of a vertex cover are highlighted
in red.

### Publications:

Peter Rossmanith