Complexity Theory

Lecture fall 2014

 Instructor Dominique Unruh < at ut dot ee> Teaching assistant Prastudy Fauzi < 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 ut-complexity@googlegroups.com Exam January 8, 2015, 14:00-17:00, room 403 Contact Dominique Unruh < at ut dot ee>

News

• None currently

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.

Homework

Your current amount of points in the homework can be accessed here.
Out / due
Homework
Solution
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

Description

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

• NP completeness (or: why are some problems inherently hard?)
• Space complexity
• The polynomial hierarchy
• Interactive proofs
• Randomized computation (or: how random numbers speed things up)
• Quantum computation (or: how physics overturns everything)
• The PCP theorem (or: how to check a proof while reading only a little part of it)
• Boolean circuits

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

Requirements

• MTAT.03.003 Algorithms and Data Structures or comparable background
• An interest in the theory of computer science
• An ability for analytical/mathematical thinking