**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 of this course can be found in the Arora-Barak book.

Lecture notes are uploaded in due course. Older 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
- Mar 01 (University closed due to heavy snow)
- Mar 06 Randomized computation (cont.)
- Mar 08 Upper bounds for BPP
- Mar 13 Counting complexity
- Mar 15 Isolation lemma
- Mar 20 Unique satisfiability
- Mar 22 Inteactive proof systems
- Mar 27 Graph isomorphism
- Mar 29 LFKN protocol for the permanent
- Apr 03 Exponential time hypothesis
- Apr 05 (no class)

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

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

Solution 2

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