Name
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 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 argue that the answer is likely `No'. More precisely, 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. 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 satisfiable circuit. We also consider a black box 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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s00037-013-0059-7 | Computational Complexity |
Keywords | Field | DocType |
Isolation Lemma, unique satisfiability, parity satisfiability, derandomization, 68Q15, 68Q17 | Discrete mathematics,Boolean circuit,Combinatorics,Lemma (mathematics),Mathematics | Conference |
Volume | Issue | ISSN |
22 | 2 | 1420-8954 |
Citations | PageRank | References |
3 | 0.43 | 15 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Holger Dell | 1 | 220 | 16.74 |
| Valentine Kabanets | 2 | 562 | 35.38 |
| Dieter van Melkebeek | 3 | 487 | 32.80 |
| Osamu Watanabe | 4 | 6 | 1.30 |