Complexity Theory

Lecture fall 2014

Instructor Dominique Unruh <<surname> at ut dot ee>
Teaching assistant
Prastudy Fauzi <<givenname> at ut dot ee>
Lecture Period September 9, 2014 - December 16, 2014
Lectures Tuesdays, 10:15-11:45, room 403 (Unruh; may sometimes be switched with practice)
Practice sessions
Tuesdays, 12:15-13:45, room 122 (Unruh)
Course Material Blackboard photos (of practice), and exam study guide.
Language English
Mailing list
Exam January 8, 2015, 14:00-17:00, room 403
Contact Dominique Unruh <<surname> at ut dot ee>


Topics covered

2014-09-09 (lecture)Intro: what is complexity theory for. Oh-notation. Languages/decision problems. Turing machines.
2014-09-09 (practice)Turing machine for palindrome testing. Turing machine for simulating a normal computer. (Yauhen)
2014-09-16 (lecture)Church-Turing thesis. Universal TM. Uncomputable functions. Halting problem. The classes DTIME, P, NP. Strong Church-Turing thesis.
2014-09-16 (practice)Time-hierarchy theorem. (Janno)
2014-09-23 (lecture)Karp reductions. NP-hard. NP-complete. Satisfiability. CNF-formulas. Cook-Levin theorem (with proof).
2014-09-23 (practice)INDSET is NP-hard. SAT reduces to INDSET. (Yauhen)
2014-09-30 (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)
2014-09-30 (practice)Oracle Turing machines. SAT^L is NP^L complete. (Ivo)
2014-10-07 (lecture)Baker-Gill-Solovay (BKS) theorem (Sec. 3.4). Randomized algorithms intro (Chap. 7 intro & Sec. 7.2.2).
2014-10-07 (practice)Polynomial identity testing (Sec. 7.2.3). (Vootele)
2014-10-14 (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.
2014-10-14 (practice)BPL (bounded-error probabilistic log-space, Sec. 7.7) is in P. (Yauhen)
2014-10-21 (lecture)Space complexity (Chap 4). Classes L and PSPACE (Sec. 4.2). TQBF is PSPACE-complete (Sec. 4.3). PSPACE and two-player games (Sec. 4.3).
2014-10-21 (practice)Palindrom in L. Hex in PSPACE. (Mayuresh)
2014-10-28 (lecture)Polynomial-hierarchy. Classes Σip, Πip, PH. Relation of PH to P, NP, PSPACE. (Sec. 5-5.2 and 5.5)
2014-10-28 (practice)If Σip=Πip, PH collapses (Thm 5.4(1)). (Yauhen)
2014-11-04 (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). NP not in P/poly unless PH collapse (Karp-Lipton, Sec. 6.4). Nonuniform hierarchy theorem (Sec. 6.6). P-uniform circuits = P (Sec. 6.2).
2014-11-04 (practice)BPP in P/poly (Sec. 7.5.1). (Ivo).
2014-11-11 (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] (Sec. 8.2.1). IP[k] in AM[k+2] (Goldwasser-Sipser, Sec. 8.2.1).
2014-11-11 (practice)IP with deterministic verifier (dIP) = NP (Sec. 8.1.1). IP in PSPACE (Ex. 8.1(b)). (Yauhen)
2014-11-18 (lecture)If graph-iso is NP-complete, PH collapses. IP=PSPACE (w/o proof). Quantum computing (intro). Formalization of quantum mechanics.
2014-11-18 (practice)Evaluating quantum circuits.
2014-11-25 (lecture)Formalization of quantum mechanics (ctd.). Simon's algorithm. Class BQP. BPP in BQP. BQP notin BPP relative to oracle.
2014-11-25 (practice)...
2014-12-02 (lecture)Cryptography (Chap 9). The need for P!= NP (Lemma 9.2). One way functions imply CPA secure encryption.
2014-12-02 (practice)Breaking the Merkle-Hellman knapsack-based cryptosystem.
2014-12-09 (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.
2014-12-09 (practice)What hardness of approximation does NP in PCP(poly,1) imply. (No definite conclusion reached.)
2014-12-16 (lecture)QUADEQ. Walsh-Hadamard codes. PCP-proof system for QUADEQ. NP in PCP(poly,1).
2014-12-16 (practice)QUADEQ is NP-complete.


Your current amount of points in the homework can be accessed here.
Out / due
2014-09-162014-09-25Homework 1Solution 1
2014-09-262014-10-03Homework 2Solution 2
2014-10-012014-10-09Homework 3Solution 3
2014-10-092014-10-16Homework 4Solution 4
2014-10-162014-10-23Homework 5Solution 5
2014-10-302014-11-06Homework 6Solution 6
2014-11-062014-11-13Homework 7Solution 7
2014-11-132014-11-20Homework 8Solution 8
2014-11-202014-11-27Homework 9Solution 9


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