- Authors: H. Dell, V. Kabanets, D. van Melkebeek, and O. Watanabe.
- Reference: Computational Complexity, 22: 345-383, 2013.
Special issue for selected papers from the
27th IEEE Conference on Computational Complexity.
- Earlier version:
Abstract
The Valiant-Vazirani Isolation Lemma 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
(i) every satisfying assignments 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 also 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 is in P/poly.
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 formula.
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.
