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 .