Complexity Theory

Lecture fall 2016

Instructor Dominique Unruh <<surname> at ut dot ee>
Teaching assistant
Prastudy Fauzi <<givenname> at ut dot ee>
Lecture Period August 30, 2016 – December 13, 2016
Lectures Tuesdays, 10:15-11:45, Paabel, room 218 (Unruh; may sometimes be switched with practice)
Practice sessions
Tuesdays, 12:15-13:45, Paabel, room 218 (Unruh/Fauzi)
Course Material Blackboard photos (of practice), and exam study guide.
Language English
Mailing list
Exam TBA
Contact Dominique Unruh <<surname> at ut dot ee>


Topics covered

2016-08-30 (lecture)Intro: what is complexity theory for. Oh-notation. Languages/decision problems. Turing machines. Church-Turing thesis. Universal TM. Uncomputable functions. Halting problem. The classes DTIME, P, NP. Strong Church-Turing thesis. (Double lecture)[video]
2016-09-06 (lecture)Karp reductions. NP-hard. NP-complete. Satisfiability. CNF-formulas. Cook-Levin theorem (with proof).[video]
2016-09-06 (practice)Turing machine for palindrome testing. Turing machine for simulating a normal computer (partial). (Tore)
2016-09-13 (practice)INDSET is NP-hard. SAT reduces to INDSET. (Raul-Martin)
2016-09-20 (lecture)coNP and coNP-completeness (Sec. 2.6.1). NP-decision vs. NP-search problems (Sec. 2.5). What if P=NP, what if L NP-hard? (Sec. 2.7.3, 2.7.6). Baker-Gill-Solovay (BKS) theorem (Sec. 3.4).[video]
2016-09-20 (practice)Time-hierarchy theorem. (Adriano)
2016-09-27 (lecture)Randomized algorithms intro (Chap. 7 intro & Sec. 7.2.2). Polynomial identity testing (Sec. 7.2.3).[video]
2016-09-27 (practice)Oracle Turing machines. P^P=P. SAT^L is NP^L complete. (Tore)
2016-10-04 (lecture)Probabilistic TM (Sec. 7.1). Class BPP (Sec. 7.1). Amplification in BPP (Sec. 7.4.1). RP (Sec. 7.3). ZPP (Sec. 7.3). BPP in EXP.[video]
2016-10-04 (practice)BPL (bounded-error probabilistic log-space, Sec. 7.7) is in P.
2016-10-11 (lecture)Space complexity (Chap 4). Classes L and PSPACE (Sec. 4.2). TQBF is PSPACE-complete (Sec. 4.3, proof only for "in PSPACE"). PSPACE and two-player games (Sec. 4.3).[video]
2016-10-11 (practice)Randomized polynomial-time algorithm for perfect matching. Algorithm for ZPP that never errs.
2016-10-18 (lecture)Polynomial-hierarchy. Classes Σip, Πip, PH. Relation of PH to P, NP, PSPACE. (Sec. 5-5.2 and 5.5)[video]
2016-10-18 (practice)TQBF is PSPACE-hard. (Tore)
2016-10-25 (lecture)Boolean circuits (Sec. 6.1). P/poly (Sec. 6.1). UHALT in P/poly (Sec. 6.1.1). P in P/poly (Sec. 6.1.1). Nonuniform hierarchy theorem (Sec. 6.6). P-uniform circuits = P (Sec. 6.2).[video]
2016-10-25 (practice)NP not in P/poly unless PH collapses (Karp-Lipton, Sec. 6.4). (Ashish)
2016-11-01 (lecture)Interactive proofs (Sec. 8.1.2). Classes IP[k], IP (Sec. 8.1.2). Classes MA, AM[k], AM (Sec. 8.2). GNI (graph non-isomorphism) is in IP[2] (Sec. 8.1.3). And in AM[2] (only mentioned, Sec. 8.2.1). IP[k] in AM[k+2] (only mentioned, Goldwasser-Sipser, Sec. 8.2.1).[video]
2016-11-01 (practice)BPP in P/poly (Sec. 7.5.1). (Dominique).
2016-11-08 (lecture)If graph-iso is NP-complete, PH collapses. IP=PSPACE (w/o proof). Quantum computing (intro). Formalization of quantum mechanics (started).[video]
2016-11-08 (practice)Evaluating quantum circuits.
2016-11-17 (lecture)Formalization of quantum mechanics (ctd.). Simon's algorithm. Class BQP. BPP in BQP. BQP notin BPP relative to oracle.[video]
2016-11-17 (practice)CHSH games (classical and quantum strategies)
2016-11-22 (lecture)Cryptography (Chap 9). The need for P!=NP (Lemma 9.2). One-way functions. One-way functions imply encryption.[video]
2016-11-22 (practice)Merkle-Hellman knapsack-based cryptosystem
2016-11-29 (lecture)Class PCP. GNI in PCP(poly,1). W/o proof: "PCP Theorem" NP=PCP(log,1) Constraint satisfaction problems (qCSP). PCP Theorem implies: qCSP hard to approximate.[video]
2016-12-13 (lecture)QUADEQ. Walsh-Hadamard codes. PCP-proof system for QUADEQ. NP in PCP(poly,1).[video]


Your current amount of points in the homework can be accessed here.
2016-08-302016-09-08Homework 1Solution 1
2016-09-062016-09-22Homework 2Solution 2
2016-09-272016-10-04Homework 3Solution 3
2016-10-062016-10-13Homework 4Solution 4
2016-10-122016-10-20Homework 5Solution 5
2016-10-202016-10-27Homework 6Solution 6
2016-10-262016-11-03Homework 7Solution 7
2016-11-022016-11-10Homework 8Solution 8
2016-11-112016-11-17Homework 9Solution 9
2016-11-182016-11-24Homework 10Solution 10
2016-11-262016-12-03Homework 11Solution 11
2016-12-022016-12-13Homework 12Solution 12


Complexity theory (or computational complexity theory) is the study of how hard computational problems are. Could it be that there are fast algorithms, e.g., for finding optimal routes? Or will any search for such algorithms be doomed from the start? What are the principal limitations of computation? Questions like this lie in the core of complexity theory. Complexity theory itself is one of the foundational areas in computer science, and it is hard to understand the theory of computer science without a sound background in complexity theory. Complexity theory is especially important for the cryptographer, as complexity theory shows up in disguise in many cryptographic security proofs.

This course will introduce you to the basics of complexity theory. You will learn the basic terminology and notions in complexity theory and learn to reason like a complexity theorist. Possible topics include (but are not limited to):

The precise choice of subjects may vary, preferences of the audience can be taken into account.



Required book (will be available in the library): "Computational Complexity: A Modern Approach" by Arora and Barak, Cambridge University Press, 2009. A draft of the book is freely available here. The lecture will mostly follow part I of this book.

Complexity Zoo: A very extensive list of complexity classes. A version for "beginners" is