On the possibilities and limitations of pseudodeterministic algorithms
On the possibilities and limitations of pseudodeterministic algorithms
复制标题
论伪确定性算法的可能性和局限性
DOI：
10.1145/2422436.2422453
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
D. Ron
中科院分区：
文献类型：
--
作者：
Oded Goldreich;S. Goldwasser;D. Ron
我们研究了伪确定性算法的可能性和局限性，算法是Gat和Goldwasser（2011）提出的一个概念。这些是解决搜索问题的概率算法，使得在每个输入上，它们以高概率输出相同的解，这可以被认为是规范解。我们考虑的标准设置（概率）多项式时间算法和设置（概率）次线性时间算法。我们的一些结果将在下面列出。在标准设置中，我们证明了伪确定性算法比确定性算法更强大的当且仅当\cP\neq\BPP，但比一般的概率算法弱。在次线性时间设置，我们表明，如果搜索问题有一个伪确定性算法的查询复杂度q，那么这个问题可以解决确定性O（q4）查询。这是指总搜索问题。相比之下，对于几个自然的承诺搜索问题，我们提出了伪确定性算法，比他们的确定性同行更有效。
We study the possibilities and limitations of pseudodeterministic algorithms, algorithms, a notion put forward by Gat and Goldwasser (2011). These are probabilistic algorithms that solve search problems such that on each input, with high probability, they output the same solution, which may be thought of as a canonical solution. We consider both the standard setting of (probabilistic) polynomial-time algorithms and the setting of (probabilistic) sublinear-time algorithms. Some of our results are outlined next. In the standard setting, we show that pseudodeterministic algorithms are more powerful than deterministic algorithms if and only if \cP\neq\BPP, but are weaker than general probabilistic algorithms. In the sublinear-time setting, we show that if a search problem has a pseudodeterministic algorithm of query complexity q, then this problem can be solved deterministically making O(q4) queries. This refers to total search problems. In contrast, for several natural promise search problems, we present pseudodeterministic algorithms that are much more efficient than their deterministic counterparts.