[Computational Complexity] Favorite Theorems: Unique Witnesses
This is the August edition of Favorite Theorems.
Perhaps you could easily find a satisfying assignment of a Boolean formula when only one solution exists, somehow using the uniqueness to cleverly guide your search. Valiant and Vazirani show that any such procedure would give a randomized algorithm for general satisfiability and put the class NP in RP.
NP is as easy as detecting unique solutions, Leslie Valiant and Vijay Vazirani, STOC 1985, TCS 1986.
Valiant and Vazirani show there is some efficient randomized algorithm f mapping Boolean formula to Boolean formula such that for all formula φ,
- f(φ) will always have the same set of variables of φ and every satisfying assignment of f(φ) is a satisfying assignment of φ. In particular if φ is not satisfiable then f(φ) is never satisfiable.
- If φ is satisfiable then Pr(f(φ) has exactly one satisfying assignment) ≥ 1/(4n), where n is the number of variables of φ.
Valiant and Vazirani's proof takes random half-spaces of the solution set and argues that with some reasonable probability repeating this process will yield a single solution. The techniques are quite general and one can get similar results for nearly every known NP problem.
Mulmuley, Vazirani and Vazirani prove an "isolating lemma" which one can use to give an alternate proof of a similar theorem by putting random weights on edges and with some reasonable probability there is a unique maximum weight clique. Mulmuley et. al. use the isolating lemma to give a simple randomized parallel algorithm for maximum matching.
Besides the immediate hardness of finding unique solutions, Valiant-Vazirani has had impact in complexity in many ways. Just a couple:
- One can use Valiant-Vazirani to find a satisfying assignment of a formula using non-adaptive queries to SAT.
- Valiant-Vazirani gives the base case of Toda's theorem.
- Similar ideas show how to create a low-degree polynomial that correctly computes the OR function at most inputs (which one can extend to AC0 by recursion).
Posted by Lance to Computational Complexity at 9/01/2006 09:43:00 AM