Computational Complexity:  2024-2025

Overview

This course is an introduction to the theory of computational complexity and standard complexity classes. One of the most important insights to have emerged from Theoretical Computer Science is that computational problems can be classified according to how difficult they are to solve. This classification has shown that many computational problems are impossible to solve, and many more are impractical to solve in a reasonable amount of time. To classify problems in this way, one needs a rigorous model of computation, and a means of comparing problems of different kinds. This course introduces these ideas, and shows how they can be used.

Learning outcomes

The course is designed to enable students to:

1. Classify decision problems into appropriate complexity classes, including P, NP, PSPACE and complexity classes based on randomised machine models and use this information effectively.
2. State precisely what it means to reduce one problem to another, and construct reductions for simple examples.
3. Classify optimisation problems into appropriate approximation complexity classes and use this information effectively.
4. Use the concept of interactive proofs in the analysis of optimisation problems.

Prerequisites

The course begins with a brief review/reminder of Turing machines and decision problems; but students should know about models of computation and undecidability. Students should also be familiar with the notion of polynomial-time computation (and its significance) and "big-O" notation.

Synopsis

1. [1 lecture] Introduction. Easy and hard problems. Algorithms and complexity.
2. [1 lecture] Turing machines, reductions, and diagonalisation
3. [1 lecture] The Halting Problem and Undecidable Languages. Counting and diagonalisation. Tape reduction. Universal Turing machine. Undecidability of halting. Reductions. Rice's theorem.
4. [1 lecture] Deterministic Complexity Classes. DTIME[t]. Linear Speed-up Theorem. PTime. Polynomial reducibility. Polytime algorithms: 2-satisfiability, 2-colourability.
5. [4 lectures] NP and NP-completeness. Non-deterministic Turing machines. NTIME[t]. NP. Polynomial time verification. NP-completeness. Cook-Levin Theorem. Polynomial transformations: 3-satisfiability, clique, colourability, Hamilton cycle, partition problems. Pseudo-polynomial time. Strong NP-completeness. Knapsack. NP-hardness.
6. [4 lectures] Space complexity and hierarchy theorems. DSPACE[s]. Linear Space Compression Theorem. PSPACE, NPSPACE. PSPACE = NPSPACE. PSPACE-completeness. Quantified Boolean Formula problem is PSPACE-complete. L, NL and NL-completeness. NL=coNL. Hierarchy theorems.
7. [2 lectures] Optimization and approximation. Combinatorial optimisation problems. Relative error. Bin-packing problem. Polynomial and fully polynomial approximation schemes. Vertex cover, travelling salesman problem, minimum partition.
8. [2 lectures] Randomized Complexity. The classes BPP, RP, ZPP. Interactive proof systems: IP = PSPACE.

Syllabus

Turing machines, decision problems and search problems, time and space complexity, polynomial time algorithms, NP and NP-completeness, standard time and space complexity classes, oracles and the polynomial hierarchy, randomised algorithms and complexity classes based on randomised machine models, interactive proofs and their relation to approximation.

Reading list

Primary Text

• M Sipser. Introduction to the Theory of Computation, (First edition - PWS Publishing Company, January 1997, or second edition - Thomson Course Technology, 2005).

Supplementary List

• Arora, Barak. Computational Complexity. Cambridge University Press, 2009.
• I Wegener. Complexity Theory, Springer,  2005.
• C H Papadimitriou. Computational Complexity, Addison-Wesley, 1994.
• M R Garey and D S Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979.
• T H Cormen, S Clifford, C E Leiserson and R L Rivest. Introduction to Algorithms, MIT Press, Second edition, 2001.
• Oded Goldreich. Computational Complexity, Cambridge University press.
• Vijay V. Vazirani. Approximation Algorithms, Springer, Second edition, 2003.

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.