** 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.

1

** 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.

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.

* 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.

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

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.

* 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 .

* 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.