Seminar: Complexity Theory
Summer Term 2022
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 creates a written reports and holds a presentation on a topic of the complexity theory.
Literature
The topics of the seminar will be assigned at the first meeting. Inital litearture to the seminar: