Lecture 24 - Cutting planes and course conclusion
We describe the cutting planes proof system: we show that it p-simulates resolution, and that it refutes Pigeonhole principle efficiently.
Homework
- Section 19.1, 19.2 [Jukna]
This is the journal of the computational complexity course. You can find the content of each lecture and any additional resource.
We describe the cutting planes proof system: we show that it p-simulates resolution, and that it refutes Pigeonhole principle efficiently.
Homework
We describe the Pigeonhole Principle, which is hard for resolution. Pigeonhole principle proof complexity in tree-like resolution is \(2^{\Theta(n \log n)}\), and we briefly describe the upper bound.
We can easily show that \(2^{\Omega(n)}\) is required for tree-like resolution using the Prover-Delayer game, but we can show formally that this game cannot give a tight lower bound.
We show instead that the proof complexity in resolution is \(2^{\Theta(n)}\) and we give both the upper and the lower bound.
Homework
We describe the Ordering Principle formula, which is hard for tree-like resolution but has a resolution refutation of polynomial size.
We present a Prover-Delayer game on CNFs that provides a good framework to give lower bounds to tree-like resolution refutations. We use it to prove that Tree-Like Resolution cannot prove the ordering principle efficiently, while standard resolution has short proofs of it. We show both statements.
Homework
We introduce the topic of Proof Complexity. We introduce proofs of unsatisfiability for CNF formulas. In particular we discuss Decision Trees and Resoluton. We prove that tree-like Resolution efficiently p-simulates Decision trees, andd we show a lower bound for Tree-Like Resolution via a Prover-Delayer game.
Homework
We conclude the discussion of deterministic communication complexity, showing
We introduce randomized protocols with public and private coins, and we discuss a Minimax theorem for them. We will use some material from the book of Rao and Yehudayoff.
Homework
We continue the discussion of communication complexity, and the fundamental interpretation of the protocol as partition of a matrix into monochromatic combinatorial rectangles. We see some applications of communication complexity to lower bounds, and we discuss few methods of lower bounding \(C(f)\).
We will use some material from the book of Rao and Yehudayoff.
Homework
Many of these exercises have hints for solutions in the book, and moreover we will see together some of the solutions in class, in particular 13.3, 13.16, 13.19
We concluded with the relations between various complexity measures for boolean functions.
We introduce the model of communication complexity, in particular the deterministic one. We give some examples of applications, and then we describe some techniques to prove lower bounds in this model.
Homework
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. Then we connect the decision tree complexity to sensitivity, block sensitivity and degree, three parameters of boolean functions. We briefly see how these measures are useful to study parallel computation.
Homework
We discuss the Certificate complexity and its connection with Decision tree complexity.
Homework
Please fill the OPIS form for this course
The students will present proofs of NP-completeness for various problems. Each presentation should introduce the problem and explain why it is NP-complete, showing a reduction.
Please fill the OPIS form for this course
We discuss a simple and yet fundamental model of computation: decision trees. We define the most important complexity measure over it (worst depth depth).
Homework
We conclude the discussion about interactive proofs. We will prove:
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.
Homework
The lecture is going to be cancelled because the lecturer is sick
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
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.
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).
Homework
Additional resource: wikipedia page on Game Complexity
We continue with randomized computation. We give another example of randomized algorithm (findind the median) which is simpler than the corresponding deterministic version.
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.
Requirements:
Homework
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, and ZPP.
We discuss the amplification of confidence of the algorithm by repetition.
Requirements:
Homework
We further discuss the complexity class P/poly, define both as the class of languages with polynomial size circuits. We show that P/poly contains non-computable languages.
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
We conclude the proof that 3-SAT is NP-complete, we see easily that there are many others NP-complete like Independent Set, or Clique, or Vertex cover.
We discuss and define class coNP, and its relation with NP.
We discuss the difference between Decision, Search and Optimization.
Homework
We prove Theorem 2.9 to give a canonical (even if not interesting) NP-complete problem.
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
We see a different definition of NP via non-deterministic Turing Machines, and we prove the equivalence with the previous definition.
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 and that 3-SAT reduces to INDSET.
We introduce (without proof for now) the Cook-Levin theorem which claims that SAT (or even 3-SAT) is an NP-complete problems.
Homework
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.
We discuss 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. We see different ways to define NP: via (1) a verifier (2) a non-deterministic Turing Machine. To do (2) we define NTIME.
Homework
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
Universality
Uncomputability
Homework
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:
Homework: