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

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 ${\displaystyle \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 ${\displaystyle F(x_{1},\dots ,x_{n})}$ with ${\displaystyle n}$ variables ${\displaystyle x_{1},\dots ,x_{n}}$ to a Boolean formula ${\displaystyle F'(x_{1},\dots ,x_{n})}$ such that

...
Wikipedia