
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:
Indepth 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, SpringerVerlag, accompanying

K.R. Reischuk:

Einführung in die Komplexitätstheorie
TeubnerVerlag, excerpts

Ch. Papadimitriou:

Computational Complexity
AddisonWesley

G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. MarchettiSpaccamela, M. Protasi:

Complexity and Approximation  Combinatorial optimization problems and their approximability properties
SpringerVerlag


Office Hours:
look here
