Complexity theory

In addition to the question of how a problem can be solved algorithmically, the question of the efficiency of such an algorithmic solution is a fundamental component of computer science. The theory of complexity deals with the question of the required resources to solve a problem.

Since an absolute classification of problems has proved to be very difficult, a relative classification has been passed. The concept of reduction plays a central role here.

We work especially in the field of circuit complexity.

The course gives an insight into the classical complexity theory. The concepts of resource consumption and reduction known from computer science 3 are motivated, repeated and deepened.

The concept of the completeness of a problem is thoroughly investigated again by NP as an example, and complete problems are also presented for other complexity classes such as P, NL and PSPACE. Randomized complexity classes are also investigated.

In another chapter, the approximability of NP-complete problems is investigated.