Computational Complexity

INFR11102 - 2019 Autumn

---

General Information

• Instructor : Heng Guo

• Lectures:
  Tuesday 11:10-12:00: Room 2.3, Lister Center (Week 1,2,4)
                                    Room G.8, 1 George Square (Week 3,5)
                                    Room 1.2, Lister Center (Week 6-11)
  Thursday 11:10-12:00: Room 2.1, Lister Center

• Tutorial: Friday 11:10-12:00: G.203 Teaching Room 2 - Doorway 3, Medical School (Week 2,4,6,8,10)

• Course catalogue entry

• 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.

Description

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.

Schedule / Lecture Notes

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 17 Introduction
• Sep 19 Turing machines and undecidability
• Sep 24 Hierarchy theorems
• Sep 26 Hierarchy theorems; Robust complexity classes
• Oct 01 Non-determinism
• Oct 03 Savitchʼs Theorem
• Oct 08 More on NL; NP-completeness
• Oct 10 More on NP-completeness
• Oct 15 More on NP-completeness; Ladnerʼs theorem
• Oct 17 NP-intermediate candidates
• Oct 22 Polynomial hierarchy
• Oct 24 Circuit models
• Oct 29 More on circuit models; Randomized computation
• Oct 31 Randomized computation
• Nov 05 Upper bounds for BPP
• Nov 07 Counting complexity
• Nov 12 (no lecture)
• Nov 14 Approximate counting
• Nov 19 Unique Satisfiability; Interactive proofs
• Nov 21 Graph isomorphism
• Nov 26 Interactive protocol for the permanent
• Nov 28 (flex)

Problem Sets

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

---

Some Learning Resources

• 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

---

Guidelines

Please read the following guidelines regarding coursework:

• Academic Conduct Policy: Students are expected to adhere to the academic conduct policy of the University; this policy can be found in full here.
• Late Coursework Policy: Please see here for the late coursework policy of the School of Informatics.