Is Valiant-Vazirani's isolation probabilityimprovable?
Is Valiant-Vazirani's isolation probabilityimprovable?
复制标题
Valiant-Vazirani 的孤立概率是否可以提高？
DOI：
10.1007/s00037-013-0059-7
复制
发表时间：
2013
影响因子：
1.4
通讯作者：
Osamu Watanabe
中科院分区：
文献类型：
--
作者：
Holger Dell;Valentine Kabanets,Dieter van Melkebeek;Osamu Watanabe
Valiant 和 Vazirani 的隔离引理（Theor Comput Sci 47:85–93, 1986）提供了一个有效的过程，用于隔离给定可满足电路的令人满意的分配：给定布尔电路Conn输入变量，该过程在相同的输入变量上输出一个新的电路C'，使得（i）C'的每个令人满意的分配也满足C'并且（ii）如果C是可满足的，那么C'恰好有一项令人满意的任务。特别是，如果 C 不可满足，则 (i) 意味着 C' 不可满足。 Valiant-Vazirani 过程是随机的，当 C 可满足时，它会产生一个唯一可满足的电路 C'，概率为 Ω(1/n)。是否可能有一个有效的确定性证人隔离过程？或者，至少，是否有可能将随机过程的成功概率提高到一个大常数？我们证明存在非均匀随机多项式时间证人隔离程序，当且仅当NPP/poly 时，其成功概率大于2/3。我们对证人隔离的其他变体建立了类似的结果，例如删除了可满足电路中除奇数个满足分配之外的所有分配的减少。我们还考虑了证人隔离的黑盒设置，该设置概括了 Valiant-Vazirani 隔离引理的设置，并给出了自然类随机证人隔离程序的成功概率的上限 O(1/n)。
The Isolation Lemma of Valiant and Vazirani (Theor Comput Sci 47:85–93, 1986) provides an efficient procedure forisolatinga satisfying assignment of a given satisfiable circuit: Given a Boolean circuitConninput variables, the procedure outputs a new circuitC′ on the sameninput variables such that (i) every satisfying assignment ofC′ also satisfiesCand (ii) ifCis satisfiable, thenC′ has exactly one satisfying assignment. In particular, ifCis unsatisfiable, then (i) implies thatC′ is unsatisfiable. The Valiant–Vazirani procedure israndomized, and whenCis satisfiable, it produces a uniquely satisfiable circuitC′ with probability Ω(1/n).Is it possible to have an efficientdeterministicwitness-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/3if and only ifNPP/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 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 ofO(1/n) on the success probability for a natural class of randomized witness-isolating procedures.