Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR11-151 | 31st December 2012 01:56

Is the Valiant-Vazirani Isolation Lemma Improvable?

RSS-Feed




Revision #2
Authors: Holger Dell, Valentine Kabanets, Osamu Watanabe, Dieter van Melkebeek
Accepted on: 31st December 2012 01:56
Downloads: 1312
Keywords: 


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



Changes to previous version:

improved presentation


Revision #1 to TR11-151 | 24th June 2012 01:20

Is Valiant-Vazirani's Isolation Probability Improvable?





Revision #1
Authors: Holger Dell, Valentine Kabanets, Osamu Watanabe, Dieter van Melkebeek
Accepted on: 24th June 2012 01:20
Downloads: 903
Keywords: 


Abstract:

The Valiant{Vazirani Isolation Lemma [TCS, vol. 47, pp. 85{93, 1986] provides an ecient
procedure for isolating a satisfying assignment of a given satis able circuit: Given a Boolean
circuit C on n input variables, the procedure outputs a new circuit C0 on the same n input
variables such that (i) every satisfying assignment of C0 also satis es C, and (ii) if C is satis able,
then C0 has exactly one satisfying assignment. In particular, if C is unsatis able, then (i) implies
that C0 is unsatis able. The Valiant{Vazirani procedure is randomized, and when C is satis able
it produces a uniquely satis able circuit C0 with probability $\Omega(1/n)$.
Is it possible to have an ecient deterministic witness-isolating procedure? Or, at least, is
it possible to improve the success probability of a randomized procedure to a large constant?
We argue that the answer is likely `No'. More precisely, we prove that there exists a nonuniform
randomized polynomial-time witness-isolating procedure with success probability bigger
than 2/3 if and only if NP \subset P/poly. Thus, an improved witness-isolating procedure would
imply the collapse of the polynomial-time hierarchy. 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 satis able 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.


Paper:

TR11-151 | 9th November 2011 20:00

Is the Valiant-Vazirani Isolation Lemma Improvable?





TR11-151
Authors: Valentine Kabanets, Osamu Watanabe
Publication: 9th November 2011 20:02
Downloads: 1931
Keywords: 


Abstract:

The Valiant-Vazirani Isolation Lemma [TCS, vol. 47, pp. 85--93, 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 with the property that the set of satisfying assignments for $C'$ is a subset of those for $C$, and moreover, if $C$ is satisfiable then $C'$ has exactly one satisfying assignment. The Valiant-Vazirani procedure is randomized, and it produces a uniquely satisfiable circuit $C'$ with probability $\Omega(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 $\Omega(1)$? We argue that the answer is likely `No'. More precisely, we prove that
(1) a non-uniform deterministic polynomial-time witness-isolating procedure exists if and only if $NP\subseteq P/poly,$
(2) if there is a randomized polynomial-time witness-isolating procedure with success probability bigger than $2/3$, then $coNP\subseteq NP/poly.$

Thus, an improved witness-isolating procedure would imply the collapse of the Polynomial-Time Hierarchy. Finally, we consider a black-box setting of witness isolation (generalizing the setting of the Valiant-Vazirani Isolation Lemma), and give the upper bound $O(1/n)$ on the success probability for a natural class of randomized witness-isolating procedures.



ISSN 1433-8092 | Imprint