Computational Complexity: 20082009
Lecturer 

Degrees 
Schedule B2 — Computer Science Schedule B2 — Mathematics and Computer Science 
Term 
Michaelmas Term 2008 (16 lectures) 
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:
 State precisely what it means for a problem to be computable, and show that some problems are not computable.
 State precisely what it means to reduce one problem to another, and construct reductions for simple examples.
 Classify problems into appropriate complexity classes, including P, NP and PSPACE, and use this information effectively.
Synopsis
 [2 lectures] Turing machine and elements of computability. Models of computation. Multitape deterministic Turing machines. Decision problems.
 [3 lectures] Polynomial time. DTIME[t]. Linear Speedup Theorem. P. Polynomial reducibility. Polytime algorithms: 2satisfiability, 2colourability.
 [5 lectures] NP and NPcompleteness. Nondeterministic Turing machines. NTIME[t]. NP. Polynomial time verification. NPcompleteness. CookLevin Theorem. Polynomial transformations: 3satisfiability, clique, colourability, Hamilton cycle, partition problems. Pseudopolynomial time. Strong NPcompleteness. Knapsack. NPhardness.
 [2 lectures] Space complexity. DSPACE[s]. Linear Space Compression Theorem. PSPACE, NPSPACE. PSPACE = NPSPACE. PSPACEcompleteness. Quantified Boolean Formula problem is PSPACEcomplete. L, NL and NLcompleteness. NL=coNL.
 [2 lectures] Optimization and approximation. Combinatorial optimisation problems. Relative error. Binpacking problem. Polynomial and fully polynomial approximation schemes. Vertex cover, travelling salesman problem, minimum partition.
 [2 lectures] Other topics. Randomized Complexity. The classes BPP, RP, ZPP. Interactive proof systems: IP = PSPACE.
Syllabus
Turing machines, computability, decision problems, undecidability, time complexity, polynomial time algorithms, NP and NPcompleteness, standard time and space complexity classes, optimization problems and approximation algorithms.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).
 I Wegener, Complexity Theory, Springer, 2005.
 C H Papadimitriou, Computational Complexity, AddisonWesley, 1994.
 S Arora and B Barak, Computational Complexity: A Modern Approach, preliminary version available online at princeton
 M R Garey and D S Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness, 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.