Course pages 2011–12

# Topics in Logic and Complexity

**Principal lecturer:** Prof Anuj Dawar**Taken by:** MPhil ACS, Part III**Code:** L15**Hours:** 16**Prerequisites:** Undergraduate courses in complexity theory, computation theory and first-order logic

## Aims

This module aims to provide an introduction to topics in complexity theory beyond that covered in the undergraduate course and a grounding in research that connects this with methods from logic. The topics covered in the last four lectures will focus on current research and may vary from year to year.

## Syllabus

- Complexity theory—a review of the major complexity classes (space, time, nondeterministic, etc.) and their interrelationships. [3 lectures]
- First-order and second-order logic: their expressive power and computational complexity. [3 lectures]
- Lower bounds on expressive power: the use of games and locality. [3 lectures]
- Fixed-point logics and descriptive complexity. [3 lectures]
- A selection of topics from the following [4 lectures]:
- finite-variable logics;
- complexity of constraint satisfaction problems;
- random structures;
- parameterized complexity;
- complexity of logical theories;
- logic and circuit complexity.
- logics of polynomial time computation.

## Objectives

On completion of this module, students should:

- be familiar with the basic relationship between the expressive power of logic and computational complexity;
- be able to formulate simple game-based inexpressibility arguments;
- be able to identify current research issues relating logic to complexity.

## Coursework and practical work

None.

## Assessment

The lecture syllabus will be assessed by a take-home test, set and marked by the principal lecturer.

The final module mark will be expressed as a percentage.

## Recommended reading

Arora, S. & Barak, B. (2009). *Computational complexity*.
Cambridge University Press.

Gradel. E. *et al*. (2007). *Finite model theory and its
applications*. Springer.

Libkin, L. (2004). *Elements of finite model theory*. Springer.

Immerman, N. (1999). *Descriptive complexity*. Springer.

Ebbinghaus, H-D. & Flum, J. (1999). *Finite model theory*. Springer.