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

Syllabus

• Introduction to Complexity Theory. Decidability and complexity; lower and upper bounds; the Church-Turing hypothesis.
• Time complexity. Time complexity classes; polynomial time computation and the class P.
• Non-determinism. Non-deterministic machines; the class NP; the problem 3SAT.
• NP-completeness. Reductions and completeness; the Cook-Levin theorem; graph-theoretic problems.
• More NP-complete problems. 3-colourability; scheduling, matching, set covering, and knapsack. 
• coNP. Complement classes. NP ∩ coNP; primality and factorisation.
• Cryptography. One-way functions; the class UP.
• Space complexity. Space complexity classes; Savitch’s theorem.
• Hierarchy theorems. Time and space hierarchy theorems.
• Randomised algorithms. The class BPP; derandomisation; error-correcting codes, communication complexity.
• Quantum Complexity. The classes BQP and QMA.
• Interactive Proofs. IP=PSPACE; Zero Knowledge Proofs; Probabilistically Checkable Proofs (PCPs). 
   

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

• A Survey of P vs. NP by Scott Aaronson.
• Computational Complexity: A Modern Approach by Arora and Barak
• Computational Complexity: A Conceptual Perspective by Oded Goldreich
• Mathematics and Computation by Avi Wigderson