Valiant–Vazirani theorem

The Valiant–Vazirani theorem is a theorem in computational complexity theory. It was proven by Leslie Valiant and Vijay Vazirani in their paper titled NP is as easy as detecting unique solutions published in 1986.^[1] The theorem states that if there is a polynomial time algorithm for Unambiguous-SAT, then NP = RP. The proof is based on the Mulmuley–Vazirani–Vazirani isolation lemma, which was subsequently used for a number of important applications in theoretical computer science.

The Valiant–Vazirani theorem implies that the Boolean satisfiability problem, which is NP-complete, remains a computationally hard problem even if the input instances are promised to have at most one satisfying assignment.

Proof outline

Unambiguous-SAT is the promise problem of deciding whether a given Boolean formula that has at most one satisfying assignment is unsatisfiable or has exactly one satisfying assignment. In the first case, an algorithm for Unambiguous-SAT should reject, and in the second it should accept the formula. If the formula has more than one satisfying assignment, then there is no condition on the behavior of the algorithm. The promise problem Unambiguous-SAT can be decided by a nondeterministic Turing machine that has at most one accepting computation path. In this sense, this promise problem belongs to the complexity class UP (which is usually only defined for languages).

The proof of the Valiant–Vazirani theorem consists of a probabilistic reduction from SAT to SAT such that, with probability at least $\Omega(1/n)$, the output formula has at most one satisfying assignment, and thus satisfies the promise of the Unambiguous-SAT problem. More precisely, the reduction is a randomized polynomial-time algorithm that maps a Boolean formula $F(x_1,\dots,x_n)$ with $n$ variables $x_1,\dots,x_n$ to a Boolean formula $F'(x_1,\dots,x_n)$ such that

• every satisfying assignment of $F'$ also satisfies $F$, and
• if $F$ is satisfiable, then, with probability at least $\Omega(1/n)$, $F'$ has a unique satisfying assignment $(a_1,\dots,a_n)$.

By running the reduction a polynomial number $t$ of times, each time with fresh independent random bits, we get formulas $F'_1,\dots,F'_t$. Choosing $t=O(n)$, we get that the probability that at least one formula $F'_i$ is uniquely satisfiable is at least $1/2$ if $F$ is satisfiable. This gives a Turing reduction from SAT to Unambiguous-SAT since an assumed algorithm for Unambiguous-SAT can be invoked on the $F'_i$. Then the random self-reducibility of SAT can be used to compute a satisfying assignment, should it exist. Overall, this proves that NP = RP if Unambiguous-SAT can be solved in RP.

The idea of the reduction is to intersect the solution space of the formula $F$ with $k$ random affine hyperplanes over $\text{GF}(2)^n$, where $k\in\{1,\dots,n\}$ is chosen uniformly at random. An alternative proof is based on the isolation lemma by Mulmuley, Vazirani, and Vazirani. They consider a more general setting, and applied to the setting here this gives an isolation probability of only $\Omega(1/n^8)$.

References

1. Valiant, L.; Vazirani, V. (1986). "NP is as easy as detecting unique solutions" (PDF). Theoretical Computer Science. 47: 85–93. doi:10.1016/0304-3975(86)90135-0.