CS254 Lecture 8 – Approximate Counting

Counting Problems

Today we describe counting problems and the class that they define, and we show that every counting problem can be approximately solved in randomized polynomial given access to an oracle.

CS254 Lecture 7 – Valiant-Vazirani

Today we prove the Valiant-Vazirani theorem.

Theorem 1 (Valiant-Vazirani) Suppose there is a polynomial time algorithm that on input a CNF formula having exactly one satisfying assignment finds that assignment. (We make no assumption on the behaviour of the algorithm on other inputs.) Then .

CS245 Lecture 6 – Karp-Lipton

In this lecture we prove the Karp-Lipton theorem that if all NP problems have polynomial size circuits then the polynomial hierarchy collapses. A nice application is a theorem of Kannan, showing that, for every , there are languages in requiring circuits of size . The next result we wish to prove is that all approximate combinatorial counting problem can be solved within the polynomial hierarchy. Before introducing counting problems and the hashing techniques that will yield this result, we prove the Valiant-Vazirani theorem that solving SAT on instances with exactly one satisfying assignment is as hard as solving SAT in general.

CS254 Lecture 5 – The Polynomial Hierarchy

Last revised 4/29/2010

In this lecture, we first continue to talk about polynomial hierarchy. Then we prove the Gács-Sipser-Lautemann theorem that BPP is contained in the second level of the hierarchy.

CS254 Lecture 4 – The Polynomial Hierarchy

Today we show how to reduce the error probability of probabilistic algorithms, prove Adleman’s theorem that polynomial time probabilistic algorithms can be simulated by polynomial size circuits, and we give the definition of the polynomial hierarchy

CS254 Lecture 3 – Boolean Circuits

In this lecture we introduce the computational model of boolean circuits and prove that polynomial size circuits can simulate all polynomial time computations. We also begin to talk about randomized algorithms.

CS254 Lecture 2 – P and NP

Last revised 4/29/2010

In this lecture we define , we state the versus problem, we prove that its formulation for search problems is equivalent to its formulation for decision problems, and we prove the time hierarchy theorem, which remains essentially the only known theorem which allows to show that certain problems are not in .

CS254 Lecture 1 – Introduction

Last revised 4/29/2010

This course assumes CS154, or an equivalent course on automata, computability and computational complexity, as a prerequisite. We will assume that the reader is familiar with the notions of algorithm, running time, and of polynomial time reduction, as well as with basic notions of discrete math and probability. We will occasionally refer to Turing machines.

In this lecture we give an (incomplete) overview of the field of Computational Complexity and of the topics covered by this course.