Revision #2 Authors: Holger Dell, Valentine Kabanets, Osamu Watanabe, Dieter van Melkebeek

Accepted on: 31st December 2012 01:56

Downloads: 1312

Keywords:

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

Revision #1 Authors: Holger Dell, Valentine Kabanets, Osamu Watanabe, Dieter van Melkebeek

Accepted on: 24th June 2012 01:20

Downloads: 903

Keywords:

The Valiant{Vazirani Isolation Lemma [TCS, vol. 47, pp. 85{93, 1986] provides an ecient

procedure for isolating a satisfying assignment of a given satisable 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 satises C, and (ii) if C is satisable,

then C0 has exactly one satisfying assignment. In particular, if C is unsatisable, then (i) implies

that C0 is unsatisable. The Valiant{Vazirani procedure is randomized, and when C is satisable

it produces a uniquely satisable 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 satisable 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.

TR11-151 Authors: Valentine Kabanets, Osamu Watanabe

Publication: 9th November 2011 20:02

Downloads: 1931

Keywords:

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.