Complexity Theory

Lecturer:    Dr. Axel Großmann

SWS (lectures/tutorial/practical):    1/1/0

none

Computational complexity is a fundamental area of computer science; it studies the reasons why some problems are difficult to solve by computers. The course will basically follow Papadimitriou's textbook, and will cover the following topics:

• Problems and algorithms
• Turing machines
• Computability
• Boolean logic
• NP-completeness

There are no prerequisites, but at some point notions will be assumed that will be developed in the parallel Logic course.

• Christos H. Papadimitriou. Computational Complexity, Addison Wesley, 1994
• Michael Sipser. Introduction to the Theory of Computation, PWS, 1997

Time and location:    Friday DS2, GRU 350

Additional information:    The course web page