Is the Valiant-Vazirani Isolation Lemma Improvable?
Valentine Kabanets, Osamu Watanabe · Electronic colloquium on computational complexity · 2011
AbstractThe Valiant-Vazirani Isolation Lemma [TCS, vol. 47, pp. 85{93, 1986] provides an ecientprocedure for isolating a satisfying assignment of a given satis able circuit: given a Booleancircuit C on ninput variables, the procedure outputs a new circuit C 0 on the same ninputvariables with the property that the set of satisfying assignments for C 0 is a subset of thosefor C, and moreover, if C is satis able then C 0 has exactly one satisfying assignment. TheValiant-Vazirani procedure is randomized, and it produces a uniquely satis able circuit C 0 withprobability (1=n).Is it possible to have an ecient deterministic witness-isolating procedure? Or, at least, is itpossible to improve the success probability of a randomized procedure to (1)? We argue thatthe answer is likely ‘No’. More precisely, we prove that1. a non-uniform deterministic polynomial-time witness-isolating procedure exists if and onlyif NP P=poly, and2. if there is a randomized polynomial-time witness-isolating procedure with success proba-bility bigger than 2=3, then coNP NP=poly.Thus, an improved witness-isolating procedure would imply the collapse of the Polynomial-TimeHierarchy. Finally, we consider a black-box setting of witness isolation (generalizing the settingof the Valiant-Vazirani Isolation Lemma), and give the upper bound O(1=n) on the successprobability for a natural class of randomized witness-isolating procedures.