**Instructor : Heng Guo****Lectures:**

Tuesday 11:10-12:00 Room 2.12, Appleton Tower, George Square

Thursday 11:10-12:00 Room F.21, 7 George Square**Assessment:**A written examination contributes 75% of the final grade. The remaining 25% will be based on coursework. The exam will be held in December.

The goal of computational complexity is to classify computational problems according to their intrinsic difficulty or “complexity”. It complements algorithms as we will be aiming to provide “lower bounds” to various problems. Among other things, we will talk about why the P vs. NP problem, one of the seven Millennium Prize Problems, is important, intriguing, and difficult!

Some recommended (but not required) readings:

- Sanjeev Arora and Boaz Barak, “Computational Complexity: A Modern Approach”, Cambridge University Press, 2009.
- Michael Sipser, “Introduction to the Theory of Computation”, PWS, 1997.
- Christos Papadimitriou, “Computational Complexity”, Addison-Wesley, 1994.

In particular, the Arora-Barak book is available online through the library (EASE account required). Most material of this course can be found in the Arora-Barak book.

Lecture notes will be updated in due course. Notes from the last offering can be found below (marked with *). This schedule is subject to adjustments as the course progresses. Even older notes can be found further below.

- Sep 18 Introduction
- Sep 20 Turing machines and undecidability
- Sep 25 Hierarchy theorems
- Sep 27 Hierarchy theorems; Robust complexity classes
- Oct 02 Robust Complexity Classes; Non-determinism
- Oct 04 Savitchʼs Theorem
- Oct 09 More on NL; NP-completeness
- Oct 11 More on NP-completeness
- Oct 16 More on NP-completeness; Ladnerʼs theorem
- Oct 18 NP-intermediate candidates
- Oct 23 Polynomial hierarchy*
- Oct 25 Circuit model*
- Oct 30 Karp-Lipton theorem, Randomized computation*
- Nov 01 Randomized computation (cont.)*
- Nov 06 Upper bounds for BPP*
- Nov 08 Counting complexity*
- Nov 13 Isolation lemma*
- Nov 15 Unique satisfiability*
- Nov 20 Inteactive proof systems*
- Nov 22 Review lecture

There are two problem sets. The first one is for feedback only and the second one for credits. Solutions will appear in due course.

- Problem set 1 (feedback): 4pm, Friday, 26th October

- Old Course Notes
- Lecture Notes Part 1
- Lecture Notes Part 2
- Lecture Notes Part 3
- Lecture Notes Part 4
- Lecture Notes Part 5
- Lecture Notes Part 6
- Lecture Notes Part 7
- Supplementary Note 1: Proof of the Hennie-Stearns theorem
- Supplementary Note 2: Proof of the Immerman-Szelepcsenyi theorem

- Past Examination Papers
- April 1996
- April 1997
- May 1998
- April 1999
- May 2000
- April 2001
- April 2002 (with solutions to Q1, Q2, and Q3)
- April 2003
- April 2004
- May 2005

Please read the following guidelines regarding coursework: