You are currently browsing the tag archive for the ‘CS254 2010’ tag.

Counting Problems

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

Read the rest of this entry »

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 {{\bf NP}={\bf RP}}.

Read the rest of this entry »

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 {k}, there are languages in {\Sigma_2} requiring circuits of size {\Omega(n^k)}. 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.

Read the rest of this entry »

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.

Read the rest of this entry »

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

Read the rest of this entry »

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.

Read the rest of this entry »

Last revised 4/29/2010

In this lecture we define {{\bf NP}}, we state the {{\bf P}} versus {{\bf NP}} 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 {{\bf P}}.

Read the rest of this entry »

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.

Read the rest of this entry »

a

Follow

Get every new post delivered to your Inbox.

Join 281 other followers