We conclude the proof that IP=PSPACE, in particular TQBF \(\in\) IP, and we start discussing communication complexity.

We will discuss:

• GI is probably non NP-complete
• \(AM \subseteq NP/\mathrm{poly}\)
• \(AM \subseteq\Sigma_3^p\)
• coNP \(\subseteq\) IP

Homework

• Section 8.2.4, Section 8.3

OPIS Please fill the OPIS form for this course

• instruction: download here.
• OPIS code: AJ89P762

We introduce the Interactive Provers and discuss variants instead of asking to an all-powerful prover for a single answer (e.g. a witness), we consider an interactive dialog between the prover and the verifier.

• randomness in interaction is necessary
• interactive proof of Graph non-Isomorphism
• power of provers, IP in PSPACE
• public vs private randomness
• IP, AM, MA classes
• Theorem 8.12 with no proof: \(IP[k] \subseteq AM[k+2]\) for any polynomial \(k(n)\).
• Exercise 8.7 with no proof: \(AM[k+1] \subseteq AM[k]\) for any constant \(k\).
• Theorem 8.13 with no proof: \(GNI \in AM[2]\)
• Error reduction for SOME cases

Homework

• Section 8.1, 8.2 (Up to Theorem 8.13, with no proof)
• Exercises 8.1, 8.2, 8.6, 8.8

We discuss the power of BPP. We briefly discuss derandomization, and claim that very strong pseudo random generators imply P=BPP. We show that problems in BPP have small boolean circuits and that their are contained in the second level of the polynomial hierarchy.

• Theorem 7.14 (Adleman) \(BPP \subseteq P/\mathrm{poly} \)
• Theorem 7.15 (Sipser-Gács) \(BPP \subseteq \Sigma_2^p \cap \Pi_2^p\)

Homework

• Theorem 7.14, 7.15 in [AB]

We introduce randomness in computation with examples are finding the median and primality testing. We define the classes RP, coRP, ZPP and we discuss the amplification of confidence of the algorithm by repetition. We make example of randomized algorithms: polynomial identity testing and bipartite matching.

Then we define the class BPP, which allows two-sided error. We discuss the reduction of the error via repetition, using Chernoff bound.

Requirements:

• Appendix A.2

Homework

• Sections 7.1, 7.2, 7.3, 7.4
• Exercises 7.1, 7.4, 7.5, 7.6, 7.10

Continue the discussion of the polynomial hierarchy, the notion of collapse, and we prove

• Theorem 6.6: (Karp-Lipton) \(NP \subseteq P/\mathrm{poly}\) implies \(PH=\Sigma_2^p\)
• We state the claim that Graph Isomorphism is likely not to be NP-complete.

Homework

• Sections: 5.1, 5.2
• Exercises 5.1, 5.12, 6.5, 6.6

We discuss a PSPACE complete problem TQBF and its relation with two-players competitive games. See exercise 4.10.

We go on defining the polynomial hierarchy. We discuss the definition (a finite number of alternations).

Homework

• Section: 4.2
• Sections: 5.1, 5.2
• Exercises 4.10, 5.1, 5.12

We review the notion of space complexity. This is the study of how much memory is needed to decide a language. A core concept is the configuration graph of a (non)-deterministic computation. A machine accept if and only if the accepting configuration is reachable in that graph. Review Claim 4.4 and space hierarchy theorem. We also review logspace reductions and the theory of NL-completeness of Reachability.

Recall:

• \(L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE \subseteq EXP\)
• L is strictly contained in PSPACE
• Savitch's theorem (Thm 4.14) which implies PSPACE=NPSPACE
• Immerman-Szelepcsényi (Thm 4.20) which implies NL=coNL

Going deeper:

• Alternative definition of NL and comparison with NP
• can you check a sat assignment of 3-CNF with one-directional access to the witness?
• Observe that 3-SAT is NP-complete with respect of logspace reductions.

Homework

• [pdf] Space Complexity (and homework there)

We discuss the concept of non-uniformity: to compute a function we need a circuit class with an infinite description. Is this process always constructive? We analyze this with the language of machines with advices.

We recap of NP-completeness theory: Karp reductions, NP-hardness, in the end we the Cook-Levin theorem, namely that Circuit-SAT is NP-complete, and then Circuit-SAT reduces to 3-SAT.

We show a reduction from search to decision, indeed showing that if P=NP, then searching for a SAT assignment can be done in polynomial time.

We introduce the study of space complexity. And indeed we define what it means for a machine to use sublinear space to read input and write output. We claim the basic fact that logspace function compose.

We also claim that all the constructions for the Cook-Levin theorem can be done in logspace, hence we could easy have a theory of NP-completeness based on logspace reductions.

Homework

• Section 6.1.2, 6.2, 6.3 [AB]
• [pdf] Complexity classes, NP and Cook-Levin (and homework there)

We prove that the number of OR and AND gates in a circuit for Parity on \(n\) bits is exactly \(3n-3\).

We give a brief recap about Turing machine, and we enumerate the properties needed to prove that efficient TMs imply small circuits (Theorem 6.6 in [AB]).

Homework

• Section 6.1, and 6.1.1 specifically [AB]
• Theorem 1.29 [J]
• [pdf] Turing machine recap lecture notes (and homework there)

Introduction of the course, and of the topic of computational complexity. We discussed generically what it means to prove a lower bound, i.e., to show that it is impossible to compute some function within a certain amount of resources.

An impossibility result is a mathematical statement about a computational model. We can focus on powerful computational model and only prove weak and conditional lower bounds, and we can consider concrete and restricted models where we can prove tight one.

We saw the example of two lower bounds:

• Parity on \(n\) variables requires CNF formulas of size \(\Theta(n 2^n)\)
• (Sketch) Equality of two strings of \(n\) bits requires \(n\) bits of communication.

We introduce boolean circuits. We give the general upper bound \(O(2^n)\) for every boolean function, and we clain without proof the Shannon upper bound \(O(2^n/n)\), which is then compared with a matching lower bound for almost all functions.

even though we do not know how they look like. Then we show a hierarchy theorem for circuits. After that we show the minimum number of OR and AND gates in a circuit for Parity on \(n\) bits is exactly \(3n-3\).

Homework:

• read Introduction and Chapter 0 of textbook [AB]
• Section 6.1 [AB]