# Complexity Theory

Lecture fall 2016

 Instructor Dominique Unruh < at ut dot ee> Teaching assistant Prastudy Fauzi < 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 ut-complexity@googlegroups.com Exam TBA Contact Dominique Unruh < at ut dot ee>

## News

• None currently

## 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 (Sec. 8.1.3). And in AM (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]

## Homework

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

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