Seminar: Complexity Theory
Summer Term 2021
Content
The topic of the complexity theory are the principle boundaries of efficient computability. For that the complexity theory questions "inherent difficulties" of algorithmic problems. Therefore the question is not, how efficient the algorithm solves a problem, but how efficient a problem can be solved in general. Efficiency will be measured as consumption of resources, like computation time, used memory, or used bandwidth.
Especially the comparison of the different resource dimensions is tricky. This leads to questions like " Can every memory efficient algorithm be simulated through a time efficient algorithm?" or " Do randomized algorithms in principle work better than deterministic ones?".Based on the lecture "Computability and Complexity" this lecture is a more in-depth introduction of the central topics of the complexity theory.
Prerequisites
Requirement to complete this seminar is a firm grasp of the topics of data structures, algorithms and the computability and complexity. Knowledge from the course "Complexity Theory" is beneficial but not required.
Organization
The dates of the presentations will be set up during the inital meeting.
Instructor
Requirements
Each participant of the seminar will work out a 5 sided paper and a 45 minute talk about a algorithmic topic of the complexity theory. With help from original literature and books on the topic the participants will work out their assignments.
Literature
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