We continue with the student presentations.

Student presentations

We describe the Pigeonhole principle and the Ordering Principle formula. The former is hard for resolution (and we show this), and the latter is hard for tree-like resolution but has a resolution refutation of polynomial size.

Homework

• Section 18.4-18.6 [Jukna]

Then we introduce the topic of Proof Complexity, and the problem of showing unsatisfiability of CNF formulas.

We discuss proofs of unsatisfiability via Decision Trees and Resoluton. We prove that tree-like Resolution efficiently p-simulates Decision trees.

Homework

• Section 15.1 [Arora, Barak]
• Section 18.1-18.2 [Jukna]

We continue the discussion of communication complexity, giving lower bound methods.

• fooling set method: equality, disjointness, greater than
• large monochromatic rectangles: equality, inner product
• rank methods: equality, disjointness

We see some applications of communication complexity to lower bounds, for example exercises 13.16, 13.17 and 13.19. We discuss nonndeterministic communication complexity (can be lower bounded by fooling sets and not tiling) size of covers.

We will use some material from the book of Rao and Yehudayoff. (solution to Exercise 13.5)

• Theorem 1.7: balancing deterministic protocols
• Theorem 1.18: Exercise 13.10

Homework

• Section 13.2.1, 13.2.2, 13.2.3
• Theorem 1.7, 1.18 [Rao, Yehudayoff]
• Exercises 13.10, 13.16, 13.17, 13.19

We introduce the model of communication complexity, in particular the deterministic one. We discuss the connection with monochromatic rectangles and tiling.

We will use some material from the book of Rao and Yehudayoff.

• Theorem 1.9: \(C(f) = O({(\log \chi(f))}^2)\) (solution to Exercise 13.5)

Homework

• Section 13.1, 13.2.1, 13.2.2, 13.2.3
• Theorem 1.9 [Rao, Yehudayoff]

Homework

• Exercises 13.1, 13.2, 13.5, 13.9

We continue the discussion about interactive proofs. We will discuss:

• GI is probably non NP-complete
• coNP \(\subseteq\) IP
• TQBF \(\in\) IP

Homework

• Section 8.2.4, Section 8.3, Section 8.4

We study the power of interaction: 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
• 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]\)
• IP, AM, MA classes

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 a PSPACE complete problem TQBF and its relation with two-players competitive games. See exercise 4.10.

We also define logspace reductions and we discuss the NL-completeness of Reachability (see Claim 4.4). Observe that 3-SAT is NP-complete with respect of logspace reductions. See exercise 4.6.

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
• 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]\)

Homework

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

Additional resource: wikipedia page on Game Complexity

We concluded the proof of Theorem 3.7

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.

Recall:

• \(L \subseteq NL \subseteq P \subseteq NP \subseteq PH \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?

Homework

• Chapter 4
• Exercises 4.1, 4.2, 4.3, 4.4, 4.5, 4.7, 4.8

We prove some real lower bounds on general Turing machines, using the Time Hierarchy Theorems. This implies P is different from EXP.

We state Ladner's Theorem. Then we discuss the topic of machines with Oracle and the limits of diagonalization. We proved Theorem 3.1, sketched the proof of Theorem 3.2, stated Theorem 3.3 and prove Theorem 3.7: there exist oracles such that P equal to NP and P different to NP hold respectively relative to those oracle.

Homework

• Sections 3.1, 3.2, 3.3, 3.4
• Exercises 5.1, 5.10, 5.12, 6.5, 6.6 (see Karp-Lipton theorem)

Please fill the OPIS form for this course

• instruction: download here.
• OPIS code: C4TB1ISA

We go on defining the polynomial hierarchy. In particulal we see that the quantifiers definition and the oracle definitions are equivalent. We discuss the definition (a finite number of alternations) and the absence of a complete problem. We look at

• Theorem 7.15 (Sipser-Gács) \(BPP \subseteq \Sigma_2^p \cap \Pi_2^p\)
• 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.

Please fill the OPIS form for this course

• instruction: download here.
• OPIS code: C4TB1ISA

Homework

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

We finish the description of the randomized algorithms for polynomial identity testing and bipartite matching. We define the class BPP, which allows two-sided error. We discuss the reduction of the error via repetition, using Chernoff bound. We show that problems in BPP have small boolean circuits.

We briefly discuss derandomization, and claim that very strong pseudo random generators imply P=BPP,

We defined the polynomial hierarchy.

Requirements:

• Appendix A.2

Homework

• Sections 7.1, 7.4, Theorem 7.14
• Same as last lecture.

We define the classes RP, coRP, ZPP and we discuss the amplification of confidence of the algorithm by repetition. We give another randomized algorithms: polynomial identity testing and bipartite matching.

Requirements:

• Appendix A.2

Homework

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

Few more discussions about uniformity. We discuss some unconditional lower bounds for circuits. We show that there are hard 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\).

In the second part of the class we will introduce the use of randomization in computation. We present some examples of randomized processes and computations that seem to be more efficient (either in theory or in practice) than deterministic ones. We define the classes RP, coRP.

We discuss the amplification of confidence of the algorithm by repetition.

• finding the median
• Randomized primality test

Requirements:

• Appendix A.2

Homework

• Section 6.1, 6.2, 6.3, 6.5, 6.6, 7.1, 7.2 (no 7.2.4), 7.3
• Exercises 7.1, 7.4, 7.6, 7.10
• Theorem 1.29 on Jukna's book

We see easily that there are many others NP-complete, reducing to Independent Set, Clique, Vertex cover. We discussed approximation of the maximum number of satisfiable clauses in a 3-CNF.

We discuss the difference between Decision, Search and Optimization (and we give examples of TFNP problem (Hash collision and PPAD).

We have shown Theorem 2.22.

We show that P/poly contains non-computable languages, and we discuss the notion of uniformity and of a Turing machine with advice.

Please read section 2.7 of the book.

Homework

• Prove that in a 3-CNF where all clauses have three distinct variables, it is always possible to satisfy at least 7/8 fracion of the clauses.
• Reduction of SAT to directed Hamiltonian Path.
• Sections 2.4, 2.5, 2.7, 6.1, 6.3
• Exercises 2.14, 2.21, 2.23, 2.24, 2.25, 2.26, 2.27, 2.29, 2.30, 2.31, 2.34.

We introduce boolean circuits, and we discuss Circuit-SAT. We prove that Circuit-SAT reduces to 3-SAT. We start the proof of Cook-Levin Theorem, using a variant of Theorem 6.6 instead of Lemma 2.11.

We defined the class coNP, EXP, NEXP and P/poly

Homework

• Sections 2.6, 6.1
• Exercises 2.15, 2.16, 2.17, 2.18, 6.1
• Prove that any boolean circuit of size \(S\) on \(n\)-variables can be converted to the DeMorgan format, so that the new circuit has size at most \(2 S\).
• Prove that any function \(f:\{0,1\}^n \longrightarrow \{0,1\}\) can be computed by a CNF of size \(O(n 2^n)\).
• Prove that any function \(f:\{0,1\}^n \longrightarrow \{0,1\}\) can be computed by a boolean circuit of size \(O(2^n)\).
• Check exercise 6.1 to see that the previous upper bound can be improved.

We see a different definition of NP via non-deterministic Turing Machines, and we prove the equivalence with previous definitions.

We introduce the class NP, the class of decision problems that have short certificates/witness of the yes instances. This class models what we usually think as puzzles. There is one or more solutions that are easy to verify but maybe hard to find. Indeed for many decision problems in NP we do not know how to decide them efficiently. This is the question "P vs NP".

We see nevertheless that NP is inside EXP.

Using the notion of polynomial reduction (or Karp reduction) we discuss NP-hardness and NP-completeness: we identify problems that are as hard (or more) than any other problem in NP. We show that SAT reduces to 3-SAT.

We prove Theorem 2.9 to give a canonical (even if not interesting) NP-complete problem. Then we introduce (without proof for now) the Cook-Levin theorem which claims that SAT (or even 3-SAT) is NP-complete.

Homework

• Sections 2.1, 2.2, 2.3 (without section 2.3.4)
• Exercises 2.1, 2.2, 2.4, 2.6, 2.7, 2.8, 2.9, 2.10, 2.11

We recap the definition of Turing machines and discuss basic properties. We see an example on how to check a palindrome binary string in linear time. Then we discuss basic results on uncomputability.

Robustness of definitions

• number of tapes
• random access memory (think about Exercise 1.9)
• size of the alphabet
• obliviousness
• variants on tape structure

Universality

• Encoding a machine as a string
• Universal Turing machine: statement of Theorem 1.9
• Machines with timer

Uncomputability

• Function UC
• Halting problem
• Gödel Theorem (proof idea)

We define DTIME. We introduce the class P of polynomially decidable languages and we discuss pro and cons on using P as notion of efficiency.

Homework

• Sections 1.1, 1.2, 1.3, 1.4, 1.5, 1.6
• Exercises 1.2, 1.3, 1.5, 1.8, 1.14

Introduction of the course, and of the topic of computationa 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.

Homework:

• read Introduction and Chapter 0 of textbook [AB]