We show the connections between certificate and decision tree complexity, then we continue the discussion of decision tree complexity considering randomized trees. We see how they relate with standard trees and how to lower bound them, via min-max theorem.

Homework

• Sections 12.3, 12.4.1
• Exercises 12.1, 12.2, 12.3 (ignore \(s(f)\) and \(bs(f)\)), 12.5, 12.6, 12.7

We discuss a simple and yet fundamental model of computation: decision trees. We define the most important complexity measure over it (worst case depth) and see how it is connected to size. We also study certificate complexity and it's connection with decision tree complexity.

Homework

• Sections 12.1, 12.2, Definition 12.13
• Exercises 12.1, 12.2, 12.3 (ignore \(s(f)\) and \(bs(f)\)), 12.5, 12.6, 12.7

Please fill the OPIS form for this course

• instruction: download here.
• OPIS code: H0W6430W

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

• Graph Non Isomorphism is in AM (no proof)
• GI is probably non NP-complete
• coNP \(\subseteq\) IP
• TQBF \(\in\) IP

Homework

• Section 8.2.4, Section 8.3, Section 8.4
• Exercise 8.3 (variant: show that AM is in PH)

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\).
• 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 and its relation with two-players competitive games. We give the proof of Savitch's Theorem (Theorem 4.14). Savitch's theorem immediately leaves us wondering if the squaring the space is necessary to get rid of non-determinism. We discuss NL complexity class, and the theory of NL-completeness which revolves around logspace reductions. We show Theorem 4.18 and Theorem 4.20.

Homework

• Sections 4.2, 4.3
• Exercises 4.3, 4.4, 4.5, 4.7, 4.8, 4.9, 4.11

We introduce the study 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. We introduce the complexity classes related to space, and the class PSPACE.

Homework

• Sections 4.1 (no 4.1.3)
• Exercises 4.1, 4.2, 4.10

Additional resource: wikipedia page on Game Complexity

We continue with randomized computation. We give other examples of randomized algorithm (polynomial identity testing, findind the median).

We define zero-error class ZPP, and then 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, and that BPP is in the polynomial hierarchy.

Requirements:

• Appendix A.2

Homework

• Sections 7.4, Theorem 7.14 and 7.15
• Same as last lecture.

We recap last lecture, plus Theorem 6.19 and Exercises 6.5 and 6.6.

We 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

• Sections 7.1, 7.2 (no 7.2.4), 7.3
• Exercises 7.1, 7.4, 7.5, 7.6, 7.10

Please fill the OPIS form for this course

• instruction: download here.
• OPIS code: H0W6430W

We prove some real lower bounds on general Turing machines, using the Time Hierarchy Theorems. 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 Theorem 3.7. We discuss

Homework

• Sections 3.1, 3.2, 3.3, 3.4, 5.1, 5.2, 5.5
• 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: H0W6430W

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\).

Homework

• Section 6.5
• Theorem 1.29 on Jukna's book

We discuss and define class coNP, and its relation with NP. We also discuss the difference between Decision, Search and Optimization.

We further discuss the complexity class P/poly, define either as the class of languages with polynomial size circuits, or as the class with polynomial running time and polynomial advice. We show that P/poly contains non-computable languages.

Homework

• Section 6.1, 6.2, 6.3

We see easily that there are many others NP-complete, reducing to Independent Set, Clique, Vertex cover or Hamiltonian-Path. Homework

• Sections 2.4, 2.5, 2.6, 2.7
• 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.

Homework

• Sections 2.4, 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
• Machine 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 loer 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]