Complexity Theory

 

Lecture in the winter term 2018/2019

Contact

Phone

work
+49 241 80 21725

Email

E-Mail
 

Dates

Lecture
Mon, 08:30 - 10:00 Uhr (AH III)
Thu, 14:30 - 16:00 Uhr (AH III)

Exercise Class
Thu, 16:30 - 18:00 Uhr (5056)

 
 

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 acording to the 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

Knowledge from the lectures "Discret Structures", "Linear Algebra", "Computability and Complexity" and "Data Structure and Algorithms" is required.

 

Organization

The first lecture will be on 11th October, 2018

The course will be held in English.

Exams

Dates of exams will be announced soon.

Lecturer

Martin Grohe

 

External Links