Computationally Hard Problems

• to design an input representation for a given problem
• define the various levels of hardness of problems
• define when a problem is hard
• identify the abstract structure behind a real world problems
• determine whether a given problem is computationally hard
• analyse a given problem with respect to its complexity
• analyse randomized algorithms with respect to the use of resources
• analyse randomized algorithms with respect to quality of the solution they provide
• recognize the potential for a randomized solution in a given hard problem
• design randomized algorithms for specific problems
• evaluate and assess different solution methods and select the most promising one

There are many important problems in Computer Sciences and other areas for which optimal solutions can be found but the time to do so is so long that it is not practical. Examples of such problems are optimal assignment of tasks to processors, finding an optimal tour for the local postman, optimal packing of a suitcase, optimizing the payload for a space mission or selecting a profitable stock portfolio.

In the course we will first specify what we mean by a “computationally hard” problem. Then some examples of such that problems are presented and methods are described to identify a problem as being hard. In order to become accessible to an analysis real world problems have to be converted into abstract mathematical models which capture the essence of the original problem.

We shall then look at problems where randomization helps in solving them. This means that there are fast algorithms for solving the problem that use “coin flips”, i.e. a random number generator. Hence repeatedly running such an algorithm on the same input might lead to different solutions. We shall consider problems where a “good” solution will be found with high probability by randomized algorithms.

• 36 – 49 (Tues 8-12)

02110/02141/02402/02403/02405, Knowledge of theory of algorithms and basics of formal languages and statistics/probability theory. Mathematical maturity.

Lectures and exercises, some of which are mandatory.