Valiant-Vazirani theorem
From Wikipedia, the free encyclopedia
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.
Contents |
[edit] Proof of the Theorem
[edit] 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.
[edit] 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.
[edit] 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 φ0,φ1,...,φ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 2k ≤ a ≤ 2k+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 x0,x1,...,xa-1. Let's also define a random variable Χi ∈ {0,1}, 0 ≤ i ≤ a-1. Let Χi=1 denote an event when xi is a unique element of S hashed to a fixed string 0. Then,
Prob[ |ƒ-1(0)∩S| = 1 ] =
Prob[ (Χ0 = 1) ∨ (Χ1 = 1) ∨ ... ∨ (Χa-1 = 1) ] =
Prob[ Χ0 = 1 ] + Prob[ Χ1 = 1 ] + ... + Prob[ Χa-1 = 1 ], since uniqueness of xi 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[ Χ0 = 1 ] + Prob[ Χ1 = 1 ] + ... + Prob[ Χa-1 = 1 ] =
Prob[ ƒ(x0 = 0) ∧ (∀i≠0 : ƒ(xi)≠0) ] + Prob[ ƒ(x1 = 0) ∧ (∀i≠1 : ƒ(xi)≠0) ] + ... + Prob[ ƒ(xa-1 = 0) ∧ (∀i≠a-1 : ƒ(xi)≠0) ] =
a * Prob[ ƒ(x0 = 0) ∧ (∀i≠0 : ƒ(xi)≠0) ]=
a * Prob[ ƒ(x0 = 0) ] * Prob[ (∀i≠0 : ƒ(xi)≠0) | ƒ(x0 = 0) ] (by conditional probability rule).
By the properties of the universal hash function
Prob[ ƒ(x0 = 0) ]=1/(2k+2)
Prob[ (∀i≠0 : ƒ(xi)≠0) | ƒ(x0 = 0) ] = (1 - Prob[ (∃i≠0 : ƒ(xi)=0) | ƒ(x0 = 0) ]).
Note, that Prob[ (∃i≠0 : ƒ(xi)=0) | ƒ(x0 = 0) ] ≤ ∑i Prob[ ƒ(xi)=0 | ƒ(x0 = 0) ] = a/(2k+2) ≤ 1/2, since a < 2k+1.
This implies that (1 - Prob[ (∃i≠0 : ƒ(xi)=0) | ƒ(x0 = 0) ]) ≥ 1/2
Putting everything together we obtain:
Prob[ |ƒ-1(0)∩S| = 1 ] = a * Prob[ ƒ(x0 = 0) ] * Prob[ (∀i≠0 : ƒ(xi)≠0) | ƒ(x0 = 0) ] ≥ a*1/(2k+2)*1/2 ≥ 2k*1/(2k+2)*1/2 ≥ 1/8. Q.E.D.
Now, given a formula φ(x) on n variables x0,x1,...,xn 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 ƒ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 ƒ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)∧Ψi(x).
If there are no satisfying assignments to original formula φ(x), then ∀x φ(x) = 0 and ∀i, φi(x) = φ(x)∧Ψi(x) = 0. However, if φ(x) can be satisfied, the probability that at least one of φi(x) has a unique satisfying assignment is ≥ 1/8. To illustrate that assume S to be the set of all satisfying assignments to φ(x), i.e. S = {x ∈ {0,1}n : φ(x) = 1} and the size of S is a, such that 1 ≤ a ≤ 2n. Then, for some k, such that 0 ≤ k ≤ n, 2k ≤ a ≤ 2k+2. Then, by the lemma proven above, the probability that a unique element x' ∈ S is mapped to a fixed string 0 by function ƒk is greater or equal to 1/8. In other words, the probability that x' is a unique satisfying assignment to Ψk(x) is ≥ 1/8. Note also that since x' ∈ 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 ≥ 1/8.
Therefore, by reduction described above, we can reduce a general instance of SAT to UNIQUE-SAT probabilistically. Since by assumption UNIQUE-SAT ∈ 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 ⊆ RP, and since we know that RP ⊆ NP, then NP=RP. Q.E.D.
