Seminar: Complexity Theory


Winter Term 2015/2016



The topic of the complexity theory are the principle boundaries of efficient computability. For that the complexity theory questions "inherent dificulties" of algorithmic problems. Therefor the question is not, how efficient the algorithm solves a problem, but how efficient a problem can be solved in general. Efficency will be measured as consumption of ressources, like computation time, used memory, or used bandwith.
Especially the comparison of the different ressource dimensions is tricky. This leads to questions like " Can every memory efficent algorithm be simulated through a time efficent algorithm?" or " Do randomized algorithms in principle work better than deterministic ones?".

Based on the lecture "Compuatbility and Complexity" is this lecture a more in-depth introduction of the central topics of the complexity theory.

Previous Knowledge

Requirment to complete this seminar is firm grasp of the topics of data structures, algorithms and the computability and complexity. Knowlege from the course "complexity theory" are beneficial but not required.



The dates of the presentations will be set up during the inital meeting.


Pascal Schweitzer


Each participant of the seminar will work out a 5 sided paper and five a 45 minute talk about a algorithmic topic of the complexity theory. With help from originalk literature and books on the topic the participants will work out their assignments.



The topics of the seminar will be assigned at the first meeting. Inital litearture to the seminar:

Computational complexity, Christos H. Papadimitriou; Addison-Wesley 1994
Computational Complexity - A Modern Approach, Sanjeev Arora and Boaz Barak Cambridge University Press 2009
Theory of Computation, Dexter Kozen; Springer 2006


External Links