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