Complexity Theory
Lecture in Summer Term 2016
Contact
Name
Content
The topic of complexity theory are the boundaries of efficient computability. For that purpose, complexity theory questions the "inherent dificulties" of algorithmic problems. Therefore the main question is not how efficient the algorithm solves a problem but how efficient a problem can be solved by the best possible algorithm.
Thereby efficiency is measured by the consumption of ressources like computation time, memory usage, or used bandwith.
Especially difficult is the comparison of different ressources such as time and memory. This leads to questions like " Can every memory efficent algorithm be simulated through a time efficent algorithm?" or " Do randomized algorithm in principle work better than deterministic ones?".
The lecture is based the basic lecture "Computability and Complexity" and gives a more in-depth introduction to central topics complexity theory.
Previous Knowledge
Knowledge from the lectures "Discrete Structures", "Linear Algebra", "Computability and Complexity" as well as "Data Structures and Algorithms" is required.
Organization
Lecture will be held in english.
Lecturer