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.

improved presentation

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.

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.