Pseudodeterminism: promises and lowerbounds
Pseudodeterminism: promises and lowerbounds
复制标题
伪决定论：承诺和下限
DOI：
10.1145/3519935.3520043
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Vinodchandran, N. V.
中科院分区：
文献类型：
--
作者：
Dixon, Peter;Pavan, A.;Woude, Jason Vander;Vinodchandran, N. V.
概率算法A是伪确定性的，如果在每个输入上，存在以高概率输出的规范值。如果该算法以高概率输出k个标准值之一，则称为ak-伪确定性算法。在伪确定性的研究中，接受概率估计问题（APEP）是一个中心的计算问题，它是一个布尔电路的接受概率的加法近似。这个问题允许一个2-伪确定性算法。最近，有人指出，这个问题的一个伪确定性算法将意味着任何多值函数，承认ak-伪确定性算法为常数k（包括近似算法）也承认一个伪确定性算法（狄克逊，Pavan，Vinodchandran;ITCS 2021）。首先，作为我们的主要概念性贡献，我们建立了一个伪确定性算法APEP的存在从根本上关系到概率承诺类和相应的标准复杂性类之间的差距。特别是，我们证明了以下等价性：APEP有一个伪确定性的近似算法，当且仅当每个承诺问题在PromiseBPP有一个解决方案在BPP。这种等价性的概念解释是2-伪决定论和伪决定论之间的算法差距等价于PromiseBPP和BPP之间的差距。基于这种连接，我们表明，设计伪确定性算法的APEP导致复杂性理论中的一些公开问题的解决方案，包括新的布尔电路下界。这种等价性也解释了多重伪决定论是如何与SearchBPP中的问题联系在一起的。特别是，我们表明，如果APEP有一个pseudodetically算法，那么每个问题，承认ak（n）-pseudodetically算法（对于任何polynomialk）是在SearchBPP和承认一个pseudodetically算法。出于这种联系，我们还探讨了它的连接到概率搜索问题，并建立APEP是完整的搜索问题的某些概念的上下文中pseudodeterministy.Our的第二个贡献是建立查询复杂度的下界多pseudodeterministically计算。证明了对任意k ≥ 1，存在一个问题，其（k+1）-伪确定性查询复杂度在统一查询模型中为O（1），而在更一般的非适应查询模型中为Ω（n）.这部分工作的一个关键贡献是利用Sperner引理建立查询复杂度下限。
A probabilistic algorithmAispseudodeterministicif, on every input, there exists a canonical value that is output with high probability. If the algorithm outputs one ofkcanonical values with high probability, then it is called ak-pseudodeterministic algorithm. In the study of pseudodeterminism, the Acceptance Probability Estimation Problem (APEP), which is to additively approximate the acceptance probability of a Boolean circuit, is emerging as a central computational problem. This problem admits a 2-pseudodeterministic algorithm. Recently, it was shown that a pseudodeterministic algorithm for this problem would imply that any multi-valued function that admits ak-pseudodeterministic algorithm for a constantk(including approximation algorithms) also admits a pseudodeterministic algorithm (Dixon, Pavan, Vinodchandran;ITCS 2021).The contribution of the present work is two-fold. First, as our main conceptual contribution, we establish that the existence of a pseudodeterministic algorithm for APEP is fundamentally related to the gap between probabilistic promise classes and the corresponding standard complexity classes. In particular, we show the following equivalence:APEP has a pseudodeterministic approximation algorithm if and only if every promise problem in PromiseBPP has a solution in BPP. A conceptual interpretation of this equivalence is that the algorithmic gap between 2-pseudodeterminism and pseudodeterminism is equivalent to the gap between PromiseBPP and BPP. Based on this connection, we show that designing pseudodeterministic algorithms for APEP leads to the solution of some open problems in complexity theory, including new Boolean circuit lower bounds. This equivalence also explains how multi-pseudodeterminism is connected to problems in SearchBPP. In particular, we show that if APEP has a pseudodeterministic algorithm, then every problem that admits ak(n)-pseudodeterministic algorithm (for any polynomialk) is in SearchBPP and admits a pseudodeterministic algorithm. Motivated by this connection, we also explore its connection to probabilistic search problems and establish that APEP is complete for certain notions of search problems in the context of pseudodeterminism.Our second contribution is establishing query complexity lower bounds for multi-pseudodeterministic computations. We prove that for everyk≥ 1, there exists a problem whose (k+1)-pseudodeterministic query complexity, in the uniform query model, isO(1) but has ak-pseudodeterministic query complexity of Ω(n), even in the more general nonadaptive query model. A key contribution of this part of the work is the utilization of Sperner’s lemma in establishing query complexity lower bounds.
登录
查看更多内容
具有小电路的 NP 的新崩溃后果
DOI：
--
发表时间：
1995
期刊：
SIAM journal on computing (Print)
影响因子：
--
作者：
J. Köbler;O. Watanabe
通讯作者：
O. Watanabe
三次斯佩纳引理作为广义互补旋转的应用
DOI：
--
发表时间：
1977
期刊：
Journal of Combinatorial Theory
影响因子：
--
作者：
L. Wolsey
通讯作者：
L. Wolsey
对数空间中的再现性和伪决定论
DOI：
10.1137/1.9781611975482.38
发表时间：
2018
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
O. Grossman;Yang P. Liu
通讯作者：
Yang P. Liu
另一个证明 bpp?ph （以及更多）
DOI：
--
发表时间：
1997
期刊：
影响因子：
--
作者：
Oded Goldreich;David Zuckerman
通讯作者：
David Zuckerman
DOI：
10.1145/2422436.2422453
发表时间：
2013
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Oded Goldreich;S. Goldwasser;D. Ron
通讯作者：
D. Ron