Valiant-Vazirani Theorem
Consider the following promise problem: Given a boolean formula that has at most one satisfying assignment, decide whether it is unsatisfiable or it has exactly one satisfying assignment. The Valiant-Vazirani theorem says that, if this problem is solvable in polynomial time, then NP = RP. The idea is that SAT (an NP-complete language) has a probabilistic reduction to this problem.
Let SAT be the set of satisfiable boolean formulas. Let USAT be the set of boolean formulas each with a unique satisfying assignment.
Theorem. (Valiant-Vazirani Theorem)
There is a probabilistic algorithm (mapping a formula to another formula) running in polynomial time such that, for any input formula \(\phi\) on \(n\) variables, the algorithm outputs \(\psi\), and
- if \(\phi\) is in SAT, then with probability at least \(\frac{1}{8n}\) we have \(\psi\) is in USAT;
- if \(\phi\) is not in SAT, then \(\psi\) is not in SAT
The proof of this theorem uses the following lemma on pairwise independent hash functions.
Lemma.
Let \({\cal H}_{n,k}\) be a family of pairwise independent hash functions from $\{0,1\}^n \to \{0,1\}^k$. Let \(S\) be a subset of \(\{0,1\}^n\) of size between \(2^{k-2}\) and \(2^{k-1}\). Then, with probability at least 1/8, there is a unique \(x\in S\) such that \(h(x)=0\) for a random \(h\in {\cal H}_{n,k}\).
Proof.
Let \(p = 1/2^k\). By pairwise independency,
- for any \(x\), the probability that \(h(x) = 0\) is \(p\);
- for any \(x\neq y\), the probability that \(h(x) = 0\) and \(h(y) = 0\) is \(p^2\)
By the inclusion-exclusion principle, the probability that at least one element in \(S\) is mapped to 0 is at least
\[
\sum_{x\in S} {\bf Pr}[h(x) = 0] – \sum_{x \neq y \in S} {\bf Pr}[h(x) = h(y) = 0] = |S| p – {|S| \choose 2} p^2.
\]
By the union bound, the probability that at least two elements in \(S\) are mapped to 0 is at most
\[
\sum_{x \neq y \in S} {\bf Pr}[h(x) = h(y) = 0] = {|S| \choose 2} p^2.
\]
Then the probability that exactly one element is mapped to 0 is at least
\[
|S| p – 2 {|S| \choose 2} p^2 \geq |S| p – |S|^2 p^2 \geq \frac{1}{8}.
\]
Note that \(1/4 \leq |S| p \leq 1/2\).
█
Proof of Valiant-Vazirani Theorem.
Given a formula \(\phi\) with \(n\) variables, randomly choose \(k\) in $\{1,\ldots, n\}$ and a hash function \(h\) in \({\cal H}_{n,k+1}\). Consider that
\[
\varphi(x) \wedge [h(x) = 0].
\]
There exists constructions of hash functions such that \(h(x) = 0\) can be verified via a boolean formula. Thus we can express the above as a boolean formula (encode the hash function \(h\) into the formula).
If \(\phi\) is unsatisfiable, then the above formula is always false. If \(\phi\) is satisfiable, let \(S\) be the set of its satisfying assignments; then with probability \(1/n\), we have \(2^{k-1} \leq |S| \leq 2^{k}\), and with probability \(1/8\), there is a unique \(x\) in \(S\) such that \(h(x) = 0\).
█