**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; Circuit models
- Oct 25 Circuit models; Karp-Lipton theorem
- Oct 30 Randomized computation
- Nov 01 Upper bounds for BPP
- Nov 06 (No Lecture)
- Nov 08 (No Lecture)
- Nov 13 Counting complexity
- Nov 15 Approximate counting
- Nov 20 Unique Satisfiability; Interactive proofs
- Nov 22 Graph isomorphism
- Nov 27 Interactive protocol for the permanent
- Nov 29 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

Solution 1Problem set 2 (credit): 4pm, Friday, 23rd November

Solution 2

Here are some supplementary exercises for your own practise.

- Past exam papers can be found through this link.
- 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

- Even older 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: