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 .
1. The Valiant-Vazirani Theorem
As discussed in the last lecture, our approach is the following: given a satisfiable formula and a number such that has roughly satisfying assignments, we pick a random hash function from a family of pairwise independent hash functions, and we construct a formula which is equivalent to . With constant probability, has precisely one satisfying assignment, and so we can pass it to our hypothetical algorithm, which finds a satisfying assignment for and hence a satisfying assignment for .
If we are only given , we can try all possible values of between and (where is the number of variables in ), and run the above procedure for each . When the correct value of is chosen, we have a constant probability of finding a satisfying assignment for .
Once we have a randomized algorithm that, given a satisfiable formula, finds a satisfying assignment with constant probability, we have an algorithm for 3SAT: run the assignment-finding algorithm, accept if it finds a satisfying assignment and reject otherwise. The existence of an algorithm for 3SAT implies that because is closed under many-to-one reductions, and so because we have by definition.
The main calculation that we need to perform is to show that if we have a set of size roughly , and we hash its elements pairwise independently to , then there is a constant probability that exactly one element is hashed to .
Lemma 2 Let be a set such that and let be a family of pairwise independent hash functions of the form . Then if we pick at random from , there is a constant probability that there is a unique element such that . Precisely,
Proof: Let us fix an element . We want to compute the probability that is the unique element of mapped into by . Clearly,
and we know that
The difficult part is to estimate the other probability. First, we write
And then observe that
Notice how we used the fact that the value of is independent of the value of when .
Putting everything together, we have
To conclude the argument, we observe that the probability that there is a unique element of mapped into is given by the sum over of the probability that is the unique element mapped into (all this events are disjoint, so the probability of their union is the sum of the probabilities). The probability of a unique element mapped into is then at least .
- If is unsatisfiable then is unsatisfiable.
- If has at least and less than satifying assignments, then there is a probability at least then the formula has exactly one satisfying assignment.
Proof: Say that is a formula over variables. The algorithm picks at random vectors and bits and produces a formula that is equivalent to the expression . Indeed, there is no compact CNF expression to compute if has a lot of ones, but we can proceed as follows: for each we add auxiliary variables and then write a CNF condition equivalent to . Then is the AND of the clauses in plus all the above expressions for .
By construction, the number of satisfying assignments of is equal to the number of satisfying assignments of such that . If is unsatisfiable, then, for every possible choice of the , is also unsatisfiable.
If has between and assignments, then Lemma 2 implies that with probability at least there is exactly one satisfying assignment for .
We can now prove the Valiant-Vazirani theorem.
Proof: (Of Theorem 1) It is enough to show that, under the assumption of the Theorem, 3SAT has an algorithm.
On input a formula , we construct formulae by using the algorithm of Lemma 3 with parameters . We submit all formulae to the algorithm in the assumption of the Theorem, and accept if the algorithm can find a satisfying assignment for at least one of the formulae. If is unsatisfiable, then all the formulae are always unsatisfiable, and so the algorithm has a probability zero of accepting. If is satisfiable, then for some it has between and satisfying assignments, and there is a probability at least that has exactly one satisfying assignment and that the algorithm accepts. If we repeat the above procedure times, and accept if at least one iteration accepts, then if is unsatisfiable we still have probability zero of accepting, otherwise we have probability at least of accepting, which is more than 1/2 already for .