Seminar on Complexity Theory
Michaela Krüger
Comments
Contents
The well known complexity classes P and NP classify decision problems. Usually, one is interested in the solution itself though, and not just whether a solution exists or not. In this seminar we will look at search problen complexity classes and how the complexity of search and decision versions of problems differ.
In particular we will look at total seach problems, i.e. problems for which there always exists a solution, which is still hard to find. Classes considered are for example PLS, PPAD, PPP, CLS/EOPL/PLS intersected PPAD and UEOPL.
The literature will be in English, talks can be in German or English, depending on the audience.
Target audience
Masters students in computer science and mathematics.
Recommended prerequisites
- "Advanced algorithms" or a similar class.
- P, NP and the concept of reductions is known.
Suggested reading
Spezialliteratur aus Zeitschriften
13 Class schedule
Regular appointments
Contents
The well known complexity classes P and NP classify decision problems. Usually, one is interested in the solution itself though, and not just whether a solution exists or not. In ... read more