Is Valiant-Vazirani's isolation probability improvable?
Holger Dell, Valentine Kabanets , Dieter van Melkebeek, and Osamu Watanabe
Abstract
The Isolation Lemma of Valiant and Vazirani (1986) provides an efficient procedure for isolating a satisfying assignment of a given satisfiable circuit: Given a Boolean circuit C on n input variables, the procedure outputs a new circuit C' on the same n input variables such that (i) every satisfying assignment of C' also satisfies C, and (ii) if C is satisfiable, then C' has exactly one satisfying assignment. In particular, if C is unsatisfiable, then (i) implies that C' is unsatisfiable. The Valiant-Vazirani procedure is randomized, and when C is satisfiable it produces a uniquely satisfiable circuit C' with probability Ω(1/n).
Is it possible to have an efficient deterministic witness-isolating procedure? Or, at least, is it possible to improve the success probability of a randomized procedure to a large constant? We prove that there exists a non-uniform randomized polynomial-time witness-isolating procedure with success probability bigger than 2/3 if and only if NP has polynomial-size circuits. We establish similar results for other variants of witness isolation, such as reductions that remove all but an odd number of satisfying assignments of a satisfiable circuit.
We also consider a blackbox setting of witness isolation that generalizes the setting of the Valiant-Vazirani Isolation Lemma, and give an upper bound of O(1/n) on the success probability for a natural class of randomized witness-isolating procedures.
Versions
- journal version in Computational Complexity (special CCC'12 issue), 22(2):345-383, 2013.
- extended abstract in Proceedings of the Twenty-Seventh Annual IEEE Conference on Computational Complexity (CCC'12), pages 10-20, 2012.
- early version ECCC-TR11-151.