# 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$$.