New version page

Stanford CS 254 - The Valiant-Vazirani Theorem

Pages: 3
Documents in this Course

This preview shows page 1 out of 3 pages.

View Full Document

End of preview. Want to read all 3 pages?

View Full Document
Unformatted text preview:

The Valiant-Vazirani TheoremStanford University — CS254: Computational Complexity Handout 7Luca Trevisan April 14, 2010Today we prove the Valiant-Vazirani theorem.Theorem 1 (Valiant-Vazirani) Suppose there is a polynomial time algorithm thaton input a CNF formula having exactly one satisfying assignment finds that assign-ment. (We make no assumption on the behaviour of the algorithm on other inputs.)Then NP = RP.1 The Valiant-Vazirani TheoremAs discussed in the last lecture, our approach is the following: given a satisfiableformula φ and a number k such that φ has roughly 2ksatisfying assignments, we picka random hash function h : {0, 1}n→ {0, 1}k+2from a family of pairwise independenthash functions, and we construct a formula ψ(x) which is equivalent to φ(x)∧(h(x) =0). With constant probability, ψ has precisely one satisfying assignment, and so wecan 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 k between 0 and n (wheren is the number of variables in φ), and run the above procedure for each k. Whenthe correct value of k is chosen, we have a constant probability of finding a satisfyingassignment for φ.Once we have a randomized algorithm that, given a satisfiable formula, finds a sat-isfying assignment with constant probability, we have an RP algorithm for 3SAT:run the assignment-finding algorithm, accept if it finds a satisfying assignment andreject otherwise. The existence of an RP algorithm for 3SAT implies that NP ⊆ RPbecause RP is closed under many-to-one reductions, and so RP = NP because wehave RP ⊆ NP by definition.The main calculation that we need to perform is to show that if we have a set of sizeroughly 2k, and we hash its elements pairwise independently to {0, 1}k+2, then thereis a constant probability that exactly one element is hashed to (0, . . . , 0).Lemma 2 Let T ⊆ {0, 1}nbe a set such that 2k≤ |T | < 2k+1and let H be a familyof pairwise independent hash functions of the form h : {0, 1}n→ {0, 1}k+2. Then ifwe pick h at random from H, there is a constant probability that there is a uniqueelement x ∈ T such that h(x) = 0. Precisely,Ph∈H[|{x ∈ T : h(x) = 0}| = 1] ≥181Proof: Let us fix an element x ∈ T . We want to compute the probability that x isthe unique element of T mapped into 0 by h. Clearly,Ph[h(x) = 0∧∀y ∈ T −{x}.h(y) 6= 0] =Ph[h(x) = 0]·Ph[∀y ∈ T −{x}.h(y) 6= 0|h(x) = 0]and we know thatPh[h(x) = 0] =12k+2The difficult part is to estimate the other probability. First, we writePh[∀y ∈ T − {x}.h(y) 6= 0|h(x) = 0] = 1 −Ph[∃y ∈ T − {x}.h(y) = 0|h(x) = 0]And then observe thatPh[∃y ∈ T − {x}.h(y) = 0|h(x) = 0]≤Xy∈|T |−{x}Ph[h(y) = 0|h(x) = 0]=Xy∈|T |−{x}Ph[h(y) = 0]=|T | − 12k+2≤12Notice how we used the fact that the value of h(y) is independent of the value of h(x)when x 6= y.Putting everything together, we havePh[∀y ∈ T − {x}.h(y) 6= 0|h(x) = 0] ≥12and soPh[h(x) = 0 ∧ ∀y ∈ T − {x}.h(y) 6= 0] ≥12k+3To conclude the argument, we observe that the probability that there is a uniqueelement of T mapped into 0 is given by the sum over x ∈ T of the probability that xis the unique element mapped into 0 (all this events are disjoint, so the probabilityof their union is the sum of the probabilities). The probability of a unique elementmapped into 0 is then at least |T |/2k+3> 1/8. 2Lemma 3 There is a probabilistic polynomial time algorithm that on input a CNFformula φ and an integer k outputs a formula ψ such that• If φ is unsatisfiable then ψ is unsatisfiable.• If φ has at least 2kand less than 2k+1satifying assignments, then there is aprobability at least 1/8 then the formula ψ has exactly one satisfying assignment.Proof: Say that φ is a formula over n variables. The algorithm picks at randomvectors a1, . . . , ak+2∈ {0, 1}nand bits b1, . . . , bk+2and produces a formula ψ that isequivalent to the expression φ(x) ∧(a1·x+b1= 0)∧. . . ∧ (ak+2·x+bk+2= 0). Indeed,there is no compact CNF expression to compute a ·x if a has a lot of ones, but we canproceed as follows: for each i we add auxiliary variables yi1, . . . , yinand then write aCNF condition equivalent to (yi1= x1∧ai)∧· · ·∧(yin= yin−1⊕(xn∧ai[n]⊕bi))). Thenψ is the AND of the clauses in φ plus all the above expressions for i = 1, 2, . . . , k + 2.By construction, the number of satisfying assignments of ψ is equal to the number ofsatisfying assignments x of φ such that ha1,...,ak+2,b1,...,bk+2(x) = 0. If φ is unsatisfiable,then, for every possible choice of the ai, ψ is also unsatisfiable.If φ has between 2kand 2k+1assignments, then Lemma 2 implies that with probabilityat least 1/8 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 The-orem, 3SAT has an RP algorithm.On input a formula φ, we construct formulae ψ0, . . . , ψnby using the algorithm ofLemma 3 with parameters k = 0, . . . , n. We submit all formulae ψ0, . . . , ψnto thealgorithm in the assumption of the Theorem, and accept if the algorithm can find asatisfying assignment for at least one of the formulae. If φ is unsatisfiable, then allthe formulae are always unsatisfiable, and so the algorithm has a probability zero ofaccepting. If φ is satisfiable, then for some k it has between 2kand 2k+1satisfyingassignments, and there is a probability at least 1/8 that ψkhas exactly one satisfyingassignment and that the algorithm accepts. If we repeat the above procedure t times,and accept if at least one iteration accepts, then if φ is unsatisfiable we still haveprobability zero of accepting, otherwise we have probability at least 1 − (7/8)tofaccepting, which is more than 1/2 already for t = 6.

View Full Document Unlocking...