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