Topics in Logic and Complexity

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 assessment will be based on an essay completed during the term, and a take-home test taken after the course, weighted as follows:

• Essay: 30%
• Test: 70%

Recommended reading

Arora, S. and 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. and Flum, J. (1999). Finite model theory. Springer.

Further Information

Due to COVID-19, the method of teaching for this module will be adjusted to cater for physical distancing and students who are working remotely. We will confirm precisely how the module will be taught closer to the start of term.