Seminar: Complexity Theory
Winter Term 2016/2017
Content
The topic of the complexity theory are the principle boundaries of efficient computability. For that the complexity theory questions "inherent dificulties" 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. 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 "Computability and Complexity" this lecture is a more in-depth introduction of the central topics of the complexity theory.
Previous Knowledge
Requirment to complete this seminar is a firm grasp of the topics of data structures, algorithms and the computability and complexity. Knowlege 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