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

Tuesday 10:00-10:50 Lecture Theatre 1B, Business School, George Square

Thursday 10:00-10:50 Lecture Theatre 1A, Business School, George Square**Assessment:**A written examination contributes 75% of the final grade. The remaining 25% will be based on coursework.

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 we will cover can be found in this book.

Below is a tentative schedule. It is likely to be too ambitious and I will adjust it in due course. I will also upload lecture notes, once they are available. Older lecture notes can be found below.

- Jan 16 Introduction
- Jan 18 Turing machines and undecidability
- Jan 23 Hierarchy theorems
- Jan 25 Robust complexity classes
- Jan 30 Savitchʼs theorem
- Feb 01 NP-completeness
- Feb 06 More on NP-completeness
- Feb 08 Ladnerʼs theorem, self-reducibility
- Feb 13 Polynomial hierarchy
- Feb 15 Circuit model, P/poly
- Feb 20 (No class)
- Feb 22 (No class)
- Feb 27 Karp-Lipton Theorem, Randomized computation, RP and BPP
- Mar 01 BPP in Sigma_2^P
- Mar 06 Approximate counting and unique-SAT
- Mar 08 Interactive proof systems, MA, AM
- Mar 13 LFKN protocal for Permanent
- Mar 15 IP=PSPACE
- Mar 20 Circuit lower bound: Razborov-Smolensky
- Mar 22 More on circuit lower bounds
- Mar 27 Sparsification and ETH
- Mar 29 Fine-grained complexity
- Apr 03 Review / flex
- Apr 05 Review / flex

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, 2nd March
- Problem set 2 (credit): 4pm, Friday, 23rd March

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