Complexity Theory

Vorlesung, 3-std., Johannsen; Übungen 1-std., Maio

Content

Complexity Theory is concerned with the classification of algorithms and computational problems according to their ressource consumption. Ressources considered are running time, memory usage and others. Problems of similar ressource requirements are collected into complexity classes. The best known complexity classes are P and NP, the classes of problems solvable in polynomial time by deterministic and non-deterministic algorithms, respectively.

The classes P and NP are just two examples of complexity classes. Other classes occur when studying the memory usage of algorithms, the efficient parallelizability of problems, the solvability by probabilistic or quantum algorithms or the approximate solution of problems, to name just a few more examples.

The course studies complexity classes, their relationships w.r.t. inclusion and separation, as well as implication between these. To this end, upper bounds are shown by exhibiting algorithms, and some techniques for proving lower bounds are introduced.

Overview

• Motivation and introduction
• Time complexity
• The classes P and NP
• Space complexity
• Alternation and hierarchies
• Circuit complexity
• Communication complexity
• Fine-grained complexity

Prerequisites

Knowledge of basic algorithmic techniques, as taught in the module Algorithmen und Datenstrukturen, and of the basics of computational complexity, as taught in the modules Formale Sprachen und Komplexität or Theoretische Informatik für Medieninformatiker, is required.

Organisation

The course will be held in English. The lecture and tutorial will take place in person at the time and place given below. The tutorial will take place approximately every 2nd week in the Friday slot. The tentative dates for the tutorials are: 25.10., 15.11., 29.11., 13.12., 10.1., 24.1. and 7.2.

• Hours: 3+1 SWS
• Time and Place: Tuesdays 14:15-15:45 hrs, Room M 101 (HGB) and Fridays 14:15-15:45 hrs, Room M 101 (HGB)
• Lecture: Dr. Jan Johannsen
• Tutorial: Luca Maio

Please register for the course in Moodle. All further information will be provided there. The registration key is: complexity24

Communication

There is an official chat-stream TCS-24W-Complexity for the course at the institute’s chat server, where the topics and organisation of the course can be discussed, and questions will be answered. This is our preferred communication channel, therefore, all participants are encouraged to subscribe to this channel.

Credits

The course can be credited for the modules Algorithmik und Komplexität or Vertiefende Themen der Theoretischen Informatik in the Informatik Master program, or Vertiefende Themen der Informatik für Master in the Informatik or Medieninformatik/MCI master program, as well as for Vertiefende Themen der (Medien-)Informatik in the Informatik or Medieninformatik bachelor programs.