The Hardest Explicit Construction
The Hardest Explicit Construction
复制标题
DOI：
10.1109/focs52979.2021.00051
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Oliver Korten
中科院分区：
文献类型：
--
作者：
Oliver Korten
我们研究了明确的结构问题的复杂性，在该问题中，我们在该物体的大小中产生了某些伪和多项式的特定对象。是与概率方法遵循的对象的显式结构相关的自然复杂性类别，通过将各种此类构造问题放在然后，我们证明，当搜索问题之间的降低时，je视贝克[10]的结果表明，在NP-Oracle降低下，构建了APEPP的真实表说明香农关于硬布尔功能存在的经典证据实际上是普遍的概率存在论点：德兰统治他的证明意味着通用有问题的方法作为推论。我们证明了直接的多项式时间缩短了硬真相表的明确构造。
We investigate the complexity of explicit construction problems, where the goal is to produce a particular object possessing some pseudorandom property in time polynomial in the size of that object. We give overwhelming evidence that APEPP, defined originally by Kleinberg et al. [12], is the natural complexity class associated with explicit constructions of objects whose existence follows from the probabilistic method, by placing a variety of such construction problems in this class. We then demonstrate that a result of Jeřábek [10] on provability in Bounded Arithmetic, when reinterpreted as a reduction between search problems, shows that constructing a truth table of high circuit complexity is complete for APEPP under NP-oracle reductions. This illustrates that Shannon's classical proof of the existence of hard boolean functions is in fact a universal probabilistic existence argument: deran-domizing his proof implies a generic derandomization of the probabilistic method. As a corollary, we prove that EXPNP contains a language of mildly-exponential circuit complexity if and only if it contains a language of nearly maximum circuit complexity. Finally, for several of the problems shown to lie in APEPP, we demonstrate direct polynomial time reductions to the explicit construction of hard truth tables.