About  |  Study  |  Members  |  Projects  |  Publications  |  Events  |  Search  |  Internals  |  Contact & Imprint

Courses in Winter Term 2005/06  -  Complexity Theory

Course title:  Complexity Theory

Lecturer:  Dr. Axel Großmann

Modules:   F, TCSL

Status:  foundation unit

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

Credit points:  3

Examination method:

There will be a single 120 minute written exam in the examination period. In this exam, there will be two tracks:

• Logic and Science of Computational Logic
• Complexity Theory, Computer Algebra, and Science of Computational Logic

with 50% of the total points going to both, Logic and Science of Computational Logic, and 25% of the total points going to both, Complexity Theory and Computer Algebra.

Prerequisites:

none

Course description:

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.

References:

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

Additional information:

• the course web page