Complexity Theory - Winter Term 2005/06

Introduction

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.

Consultations

During the Open House

References

Recommended text:

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

Other useful texts:

• Michael Sipser. Introduction to the Theory of Computation, PWS, 1997
• Michael R. Garey and David S. Johnson. Computers and Intractability, W. H. Freeman, 1979

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)

• Graph reachability
• Maximum flow and matching
• Travelling Salesman problem

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)

• TM basics
• TM as algorithms
• TM with multiple strings
• Lineas speedup
• Space bounds
• Nondeterministic machines

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)

• Universal TM
• Halting problem
• More undecidability
• Boolean logic
• Boolean expressions
• Satisfiability and validity (except for Horn clauses)

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)

• Complexity classes
• Hierarchy theorem
• Reductions
• Completeness (Cook's theorem)

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:

• 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.

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

• 50 points for Logic
• 50 points for Science of Computational Logic
• 25 points for Complexity theory
• 25 points for Computer Algebra

These exercises will be combined into the two tracks.