Valiant-Vazirani theorem

The Valiant-Vazirani Theorem was proven by Leslie Valiant and Vijay Vazirani in their paper titled "NP is as easy as detecting unique solutions" published in 1986. The theorem states that if there is a polynomial time algorithm for UNIQUE-SAT, then NP=RP. Formally:

UNIQUE-SAT ∈ P → NP=RP

The theorem implies that even if the number of satisfying assignments is very small, SAT (which is an NP-complete problem) still remains a hard problem.

Proof of the Theorem

UNIQUE-SAT

UNIQUE-SAT is a promise problem that decides whether a given Boolean formula is unsatisfiable or has exactly one satisfying assignment. In the first case a UNIQUE-SAT algorithm would reject, and in the second it would accept the formula. If the formula has more than one satisfying assignment then the behavior of the UNIQUE-SAT algorithm does not matter.

Proof Outline

The proof of Valiant-Vazirani Theorem creates a probabilistic reduction from SAT to a limited number of instances of UNIQUE-SAT. By this reduction, if the original formula was unsatisfiable, none of UNIQUE-SAT problems are satisfiable. And if the original formula is satisfiable, then with probability ≥ 1/8, at least one of the UNIQUE-SAT instances has a unique satisfying assignment. Note that this probabilistic reduction introduces some error; however, the proof shows that the error is single-sided and completely avoids false-positives. The reduction relies also on universal hash functions to map the original SAT formula to multiple UNIQUE-SAT instances. By choosing different sizes of the hash set the authors create one instance of UNIQUE-SAT to have a solution with probability ≥1/8, if the original problem was satisfiable.

Proof

Assume there is a polynomial time solution to UNIQUE-SAT. It is possible to reduce SAT to UNIQUE-SAT probabilistically, or, more precisely, there is a randomized polynomial time algorithm that maps a formula "φ" on "n" variables to "n+1" formulas "φ₀","φ₁",...,"φ_n", such that:

1. If "φ" is unsatisfiable, then none of "φ_i" are satisfiable.
2. If "φ" is satisfiable, then with probability ≥ 1/8, at least one of the "φ_i" has a unique satisfying assignment.

In other words, if the initial formula "φ" is not in SAT, then the algorithm makes no mistake and creates "n+1" unsatisfiable formulas. However, there exists an assignment of variables that satisfies "φ", then with probability of mistake ≤ 7/8 the algorithm makes at least one formula "φ_i" that is an instance of UNIQUE-SAT.

Note that the algorithm defined above has a false-positive probability = 0, and false-negative probability ≤ 7/8. Although by the definition of RP the probability of a false-negative must be ≤ 1/2, this algorithm is still in RP, since the error can be lowered by re-running the algorithm a fixed number of times.

Lemma: Let "S" ⊆ {0,1}^"n" of size "a", such that 2^"k" ≤ "a" ≤ 2^"k"+1, and let ƒ be a universal hash function from {0,1}^"n" to {0,1}^"k+2". Then

Prob [ |ƒ^-1(0)∩S| = 1 ] ≥ 1/8.

I.e. given a set "S" of "a" strings of zeros and ones of length "n" and a universal hash function mapping them to strings of length "k+2", the probability that a unique element of "S" is hashed to a fixed string 0 is ≥ 1/8.

To prove this let's label elements in "S" by "x₀","x₁",...,"x_a-1". Let's also define a random variable "Χ_i" ∈ {0,1}, 0 ≤ "i" ≤ "a"-1. Let "Χ_i"=1 denote an event when "x_i" is a unique element of "S" hashed to a fixed string 0. Then,
Prob [ |ƒ^-1(0)∩S| = 1 ] =
Prob [ ("Χ₀" = 1) ∨ ("Χ₁" = 1) ∨ ... ∨ ("Χ_a-1" = 1) ] =
Prob [ "Χ₀" = 1 ] + Prob [ "Χ₁" = 1 ] + ... + Prob [ "Χ_a-1" = 1 ] , since uniqueness of "x_i" implies that such events are disjoint. Now, by properties of the universal hash functions we can simplify this equation and calculate its probability as follows:
Prob [ "Χ₀" = 1 ] + Prob [ "Χ₁" = 1 ] + ... + Prob [ "Χ_a-1" = 1 ] =
Prob [ ƒ("x₀" = 0) ∧ (∀"i"≠0 : ƒ("x_i")≠0) ] + Prob [ ƒ("x₁" = 0) ∧ (∀"i"≠1 : ƒ("x_i")≠0) ] + ... + Prob [ ƒ("x_a-1" = 0) ∧ (∀"i"≠a-1 : ƒ("x_i")≠0) ] =
"a" * Prob [ ƒ("x₀" = 0) ∧ (∀"i"≠0 : ƒ("x_i")≠0) ] =
"a" * Prob [ ƒ("x₀" = 0) ] * Prob [ (∀"i"≠0 : ƒ("x_i")≠0) | ƒ("x₀" = 0) ] (by conditional probability rule).

By the properties of the universal hash function
Prob [ ƒ("x₀" = 0) ] =1/(2^"k"+2)

Prob [ (∀"i"≠0 : ƒ("x_i")≠0) | ƒ("x₀" = 0) ] = (1 - Prob [ (∃"i"≠0 : ƒ("x_i")=0) | ƒ("x₀" = 0) ] ).

Note, that Prob [ (&exist;"i"&ne;0 : &fnof;("x_i")=0) | &fnof;("x₀" = 0) ] &le; &sum;_"i" Prob [ &fnof;("x_i")=0 | &fnof;("x₀" = 0) ] = "a"/(2^"k"+2) &le; 1/2, since "a" < 2^"k"+1.
This implies that (1 - Prob [ (&exist;"i"&ne;0 : &fnof;("x_i")=0) | &fnof;("x₀" = 0) ] ) &ge; 1/2

Putting everything together we obtain:
Prob [ |&fnof;^-1(0)&cap;S| = 1 ] = "a" * Prob [ &fnof;("x₀" = 0) ] * Prob [ (&forall;"i"&ne;0 : &fnof;("x_i")&ne;0) | &fnof;("x₀" = 0) ] &ge; "a"*1/(2^"k"+2)*1/2 &ge; 2^"k"*1/(2^"k"+2)*1/2 &ge; 1/8. Q.E.D.

Now, given a formula "φ"("x") on "n" variables "x₀","x₁",...,"x_n" a reduction to UNIQUE-SAT can be constructed as follows:

For "i" = 0, 1, .., "n" define "m" = "i" + 2 and randomly choose a universal hash function &fnof;_"i" from {0,1}^"n" to {0,1}^"m". Then we can construct a boolean formula "Ψ_i"("x") to represent an instance when an input string "x" maps to a fixed string 0 in set {0,1}^"m". In other words, "Ψ_i"("x") encodes &fnof;_"i"("x")=0. Note that the formula for "Ψ"_"i"("x") is polynomial in terms of "n" and "m", thus it is polynomial in terms of "n". Now create "φ_i"("x")="φ"("x")&and;"Ψ"_"i"("x").

If there are no satisfying assignments to original formula "φ"("x"), then &forall;"x" "φ"("x") = 0 and &forall;"i", "φ_i"("x") = "φ"("x")&and;"Ψ"_"i"("x") = 0. However, if "φ"("x") can be satisfied, the probability that at least one of "φ_i"("x") has a unique satisfying assignment is &ge; 1/8. To illustrate that assume "S" to be the set of all satisfying assignments to "φ("x")", i.e. "S" = {"x" &isin; {0,1}^"n" : "φ"("x") = 1} and the size of "S" is "a", such that 1 &le; "a" &le; 2^"n". Then, for some "k", such that 0 &le; "k" &le; "n", 2^"k" &le; "a" &le; 2^"k"+2. Then, by the lemma proven above, the probability that a unique element "x' " &isin; "S" is mapped to a fixed string 0 by function &fnof;_"k" is greater or equal to 1/8. In other words, the probability that "x' " is a unique satisfying assignment to "Ψ_k"("x") is &ge; 1/8. Note also that since "x' " &isin; "S", "φ"("x' ")=1, therefore, the probability that "x' " is a unique satisfying assignment to "φ_k"("x") is greater or equal to 1/8. Thus the probability that at least one of "φ_i"("x") that were created has a unique satisfying assignment is &ge; 1/8.

Therefore, by reduction described above, we can reduce a general instance of SAT to UNIQUE-SAT probabilistically. Since by assumption UNIQUE-SAT &isin; P, then there exists an algorithm in RP that can solve SAT by using reduction first and then solving UNIQUE-SAT in polynomial time. Since SAT is NP-complete, then NP &sube; RP, and since we know that RP &sube; NP, then NP=RP. Q.E.D.

References

* [http://portal.acm.org/citation.cfm?id=22108 L. G. Valiant, V. V. Vazirani, "NP is as easy as detecting unique solutions"]
* [http://people.deas.harvard.edu/~valiant/ Leslie G. Valiant homepage]
* [http://www.cc.gatech.edu/fac/Vijay.Vazirani/ Vijay V. Vazirani homepage]