Course pages 2020–21 (these pages are still being updated)

# Complexity Theory

**Principal lecturer:** Prof Anuj Dawar**Taken by:** Part IB CST 50%, Part IB CST 75%**Past exam questions**

No. of lectures: 12

Suggested hours of supervisions: 3

Prerequisite courses: Algorithms, Computation Theory

## Aims

The aim of the course is to introduce the theory of computational complexity. The course will explain measures of the complexity of problems and of algorithms, based on time and space used on abstract models. Important complexity classes will be defined, and the notion of completeness established through a thorough study of NP-completeness. Applications to cryptography will be considered.

## Lectures

**Algorithms and problems.**Complexity of algorithms and of problems. Lower and upper bounds. Examples: sorting and travelling salesman.**Time and space.**Models of computation and measures of complexity. Time and space complexity on a Turing machine. Decidability and complexity.**Time complexity.**Time complexity classes. Polynomial time problems and algorithms. Problems on numbers, graphs and formulas.**Non-determinism.**Non-deterministic machines. The complexity class NP and its various characterizations. Non-deterministic algorithms for satisfiability and other problems in NP.**NP-completeness.**Reductions and completeness. NP-completeness of satisfiability.**More NP-complete problems.**Graph-theoretic problems. Independent set, clique and 3-colourability.**More NP-complete problems.**Sets, numbers and scheduling. Matching, set covering and knapsack.**coNP.**Validity of boolean formulae and its completeness. NP ∩ coNP. Primality and factorisation.**Cryptographic complexity.**One-way functions. The class UP.**Space complexity.**Deterministic and non-deterministic space complexity classes. The reachability method. Savitch’s theorem.**Hierarchy.**The time and space hierarchy theorems and complete problems.**Descriptive complexity.**Logics capturing complexity classes. Fagin’s theorem.

## Objectives

At the end of the course students should

- be able to analyse practical problems and classify them according to their complexity;
- be familiar with the phenomenon of NP-completeness, and be able to identify problems that are NP-complete;
- be aware of a variety of complexity classes and their interrelationships;
- understand the role of complexity analysis in cryptography.

## Recommended reading

* Papadimitriou, Ch.H. (1994). *Computational complexity*. Addison-Wesley.

Goldreich, O. (2010). *P, NP, and NP-Completeness: the basics of
computational complexity*. Cambridge University Press.
Sipser, M. (1997). *Introduction to the theory of computation*. PWS.