Lecturer: Dr. Axel Großmann,
See the official Course Summary page for more details.
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
Christos H. Papadimitriou. Computational Complexity, Addison Wesley, 1994
Please note this arrangement is tentative. Along with each topic, there is a reference to the relevant chapters or sections of the main text.
Languages for specificaton and the need for formalism. Algorithms, polynomials and polynomial time algorithms. (Ch. 1)
Turing machines as formalised algorithm. Complexity classes. Space complexity and nondeterminism (Ch. 2, except for 2.6)
Universal machines and undecidability. (Ch. 3)
Propositional logic. The complexity of satisfiability and validity. (Sec. 4.1 and 4.2)
Complexity classes. The Hierarchy theorem. (Sec. 7.1 and 7.2)
Reductions and completeness. (Sec. 8.1 and 8.2)
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.