Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

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

#### Is the Valiant-Vazirani Isolation Lemma Improvable?

Revision #2
Authors: Holger Dell, Valentine Kabanets, Osamu Watanabe, Dieter van Melkebeek
Accepted on: 31st December 2012 01:56
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
Keywords:

Abstract:

The Valiant{Vazirani Isolation Lemma [TCS, vol. 47, pp. 85{93, 1986] provides an ecient
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 ecient 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
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