On Pseudodeterministic Approximation Algorithms
On Pseudodeterministic Approximation Algorithms
复制标题
关于伪确定性逼近算法
DOI：
10.4230/lipics.mfcs.2018.61
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
N. V. Vinodchandran
中科院分区：
文献类型：
--
作者：
P. Dixon;A. Pavan;N. V. Vinodchandran
我们研究了伪确定性近似算法的概念。函数f的随机化近似算法A是伪确定性的，如果对于每个输入x都存在唯一的值v，使得A(X)以高概率输出v，并且v是f(X)的良好近似。我们证明了为NP成员计数问题设计一个伪确定性的Stockmeyer近似算法将产生一个新的回路下界：如果存在这样的逼近算法，则对于任意k，在复杂类ZPP^{NP}_{TT}中有一种语言不具有n^k-大小的回路。虽然我们不知道如何为NP成员计数问题设计这样的算法，但我们证明了一个一般性的结果：任何计数问题的随机化近似算法都可以转化为具有恒定影响随机比特的近似算法。也就是说，对于这些影响位的大多数设置，近似算法将是伪确定性的。
We investigate the notion of pseudodeterminstic approximation algorithms. A randomized approximation algorithm A for a function f is pseudodeterministic if for every input x there is a unique value v so that A(x) outputs v with high probability, and v is a good approximation of f(x). We show that designing a pseudodeterministic version of Stockmeyer's well known approximation algorithm for the NP-membership counting problem will yield a new circuit lower bound: if such an approximation algorithm exists, then for every k, there is a language in the complexity class ZPP^{NP}_{tt} that does not have n^k-size circuits. While we do not know how to design such an algorithm for the NP-membership counting problem, we show a general result that any randomized approximation algorithm for a counting problem can be transformed to an approximation algorithm that has a constant number of influential random bits. That is, for most settings of these influential bits, the approximation algorithm will be pseudodeterministic.