Complexity Theory - Winter Term 2005/06


Lecturer:   Dr. Axel Großmann,

See the official Course Summary page for more details.

Time and Place

Fridays, 2nd DS (from 9.20am until 10.50am), in GRU 350

The lectures commence on 18th November. The time and place for the tutorials is still to be decided.


During the Open House


Recommended text:

Christos H. Papadimitriou. Computational Complexity, Addison Wesley, 1994

Other useful texts:

List of Topics Arranges by Weeks

Please note this arrangement is tentative. Along with each topic, there is a reference to the relevant chapters or sections of the main text.

Week 1  (18th Nov.)   2 lectures, 1 tutorial

Introduction (Slides)

Languages for specificaton and the need for formalism. Algorithms, polynomials and polynomial time algorithms. (Ch. 1)

Week 3  (2nd Dec.)   2 lectures, 1 tutorial

Turing machines as formalised algorithm. Complexity classes. Space complexity and nondeterminism (Ch. 2, except for 2.6)

Week 5  (16th Dec.)   3 lectures, 1 tutorial

Universal machines and undecidability. (Ch. 3)
Propositional logic. The complexity of satisfiability and validity. (Sec. 4.1 and 4.2)

Week 8  (20th Jan.)   3 lectures, 1 tutorial

Complexity classes. The Hierarchy theorem. (Sec. 7.1 and 7.2)
Reductions and completeness. (Sec. 8.1 and 8.2)

Written exam on all courses within the Foundations modules

Details about the Examination

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

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.

For example, if the total number of points is 100, then there will be exercises as follows:

These exercises will be combined into the two tracks.