A Relativization Perspective on Meta-Complexity
A Relativization Perspective on Meta-Complexity
复制标题
DOI：
10.4230/lipics.stacs.2022.54
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Hanlin Ren;R. Santhanam
中科院分区：
文献类型：
--
作者：
Hanlin Ren;R. Santhanam
元复杂性研究有关复杂性理论的计算问题的复杂性，例如最小电路尺寸问题（MCSP）及其变体。我们表明，相对化障碍适用于元复杂性中的许多重要的开放问题。我们给出相对化世界，其中： 1. MCSP 可以在确定性多项式时间内求解，但 MCSP 的搜索版本不能在确定性多项式时间内求解，甚至不能近似求解。相比之下，Carmosino、Impagliazzo、Kabanets、Kolokolova [CCC’16] 给出了 MCSP 的随机近似搜索到决策简化，并带有相对化证明。 2. 在最坏情况和平均情况设置下，MCSP[2 n/ 2 ] 和 MCSP[2 n/ 4 ] 的复杂度是不同的。因此，MCSP 的复杂度对于尺寸函数的选择并不“稳健”。 3. 对于任何 ϵ > 0，Levin 的时间限制 Kolmogorov 复杂度 Kt( x ) 可以近似为多项式时间中的一个因子 (2 + ϵ )。 4. 自然证明不存在，辅助输入单向函数也不存在。相比之下，Santhanam [ITCS’20] 给出了一个相对化证明，即自然证明的不存在意味着在关于最佳命中集的猜想下存在单向函数。 5. DistNP 不会通过一系列“稳健”约简来约简为 GapMINKT。这为解决平原问题[FOCS’20]带来了技术障碍。
Meta-complexity studies the complexity of computational problems about complexity theory, such as the Minimum Circuit Size Problem (MCSP) and its variants. We show that a relativization barrier applies to many important open questions in meta-complexity. We give relativized worlds where: 1. MCSP can be solved in deterministic polynomial time, but the search version of MCSP cannot be solved in deterministic polynomial time, even approximately. In contrast, Carmosino, Impagliazzo, Kabanets, Kolokolova [CCC’16] gave a randomized approximate search-to-decision reduction for MCSP with a relativizing proof. 2. The complexities of MCSP[2 n/ 2 ] and MCSP[2 n/ 4 ] are different, in both worst-case and average-case settings. Thus the complexity of MCSP is not “robust” to the choice of the size function. 3. Levin’s time-bounded Kolmogorov complexity Kt( x ) can be approximated to a factor (2 + ϵ ) in polynomial time, for any ϵ > 0. 4. Natural proofs do not exist, and neither do auxiliary-input one-way functions. In contrast, Santhanam [ITCS’20] gave a relativizing proof that the non-existence of natural proofs implies the existence of one-way functions under a conjecture about optimal hitting sets. 5. DistNP does not reduce to GapMINKT by a family of “robust” reductions. This presents a technical barrier for solving a question of Hirahara [FOCS’20].