Department of Computer Science at the Technische Universität München
Chair for Efficient Algorithms
Postal address: 80290 München; Premises: Arcisstr.21, 80333 München

Complexity Theory (WS 01/02)

* Lecturer:
Prof. Dr. Ernst W. Mayr

* Area:
4 lectures per week in area III (Theoretical Computer Science)
core course , topic complexity

* Time and Place:
Tue 8:30 - 10:00, lecture hall N1070
Fri 8:30 - 10:00, lecture hall N1070
Start: 16. October

* Exercises:
2 hours per week exercises accompanying the lectures
Tue 16h s.t. - 17:30, lecture hall 2705
Start: 30. October
Teaching Assistant: Ulrich Rührmair
Course Certificate: To get a course certificate students must get at least 40% on the homework assignments and pass the final exam.

* Audience:
graduate students of computer science
students with computer science as minor

* Prerequisites:
1st and 2nd year courses
Course Efficient Algorithms and Data Structures I advantageous, but not necessary

* Recommended for:
In-depth knowledge in topic Complexity

* Contents:
  • Basics and Models of Computation
  • Time and Space restricted Computations
  • Important Complexity Classes (P, NP, PSPACE,EXPSPACE)
  • Time Restricted reductions
  • Circuits, Nonuniform Complexity
  • Probabilistic Machines
  • Polynomial Hierarchy

* Related and Advanced Courses:
Efficient Algorithms and Data Structures

* Lecture Notes:
Not available.

* References:
J.L. Balcázar, J. Díaz, J. Gabarró:
Structural Complexity I (and II)
EATCS Monographs, Springer-Verlag, accompanying
K.R. Reischuk:
Einführung in die Komplexitätstheorie
Teubner-Verlag, excerpts
Ch. Papadimitriou:
Computational Complexity
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi:
Complexity and Approximation --- Combinatorial optimization problems and their approximability properties

* Office Hours:
look here