Recent Advances Towards Proving P = BPP
Recent Advances Towards Proving P = BPP
复制标题
证明 P = BPP 的最新进展
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
L. Trevisan
中科院分区：
文献类型：
--
作者：
A. Clementi;José D. P. Rolim;L. Trevisan
是否存在太多复杂性类别？仅仅试图理解计算的一个方面，例如随机性的力量，就会导致一系列复杂性类别，例如 ZPP、RP 和 BPP，仅举几例。我们真的需要所有这些课程吗？过去几年中复杂性理论最令人兴奋的发展之一是越来越多的证据表明上述所有类都只是 P 的化名。本期我们的客座专栏概述了这一领域。摘要 最近开发了两种独立的技术，根据可在指数时间内计算的函数的最坏情况电路复杂性，产生 P = BPP 的充分条件。 Andreev、Clementi 和 Rolim 证明了 P = BPP 前提是存在一种具有足够高电路复杂性的稀疏“有效可枚举”语言。Impagliazzo 和 Wigderson 随后改进了该结果，表明 P = BPP 或所有可在 2 O(n) 时间内解决的决策问题都可以通过大小为 2 o(n) 的电路来解决。在本专栏中，我们讨论这些结果及其与先前已知的 P = 充分条件的关系BPP。
Are there too many complexity classes? Merely trying to understand one aspect of computation, such as the power of randomness, leads to a whole range of complexity classes, such as ZPP, RP, and BPP, to name but a few. Do we really need all of these classes? One of the most exciting developments in complexity theory in the past few years is the growing body of evidence that all of the aforementioned classes are merely pseudonyms for P. Our guest column this issue gives an overview of this area. Abstract Two independent techniques have been developed recently that yield suucient conditions for P = BPP in terms of worst-case circuit complexity of functions computable in exponential time. Andreev, Clementi and Rolim proved that P = BPP provided that a sparse \eeciently enumerable" language exists of suuciently high circuit complexity. This result has been subsequently improved by Impagliazzo and Wigderson by showing that either P = BPP or all the decision problems solvable in time 2 O(n) are solvable by circuits of size 2 o(n). In this column we discuss these results and their relation with previously known suucient conditions for P = BPP.