NP-Hardness of Learning Programs and Partial MCSP
NP-Hardness of Learning Programs and Partial MCSP
复制标题
学习计划的 NP 难度和部分 MCSP
DOI：
10.1109/focs54457.2022.00095
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Shuichi Hirahara
中科院分区：
文献类型：
--
作者：
Shuichi Hirahara;Nobutaka Shimizu;Shuichi Hirahara
在计算学习理论中，一个长期存在的问题是证明学习有效程序的NP-困难性，其设置介于正确学习和不正确学习之间。Ko（COLT'90，SICOMP'91）明确提出了这个开放性问题，并通过证明不存在学习程序NP-困难的相对化证明来证明其困难性。在本文中，我们克服了Ko的相对化障碍，证明了学习程序在随机多项式时间多1约简下的NP-困难性。我们的结果是可证明的非相对化，并且有点接近不正确学习的参数范围：我们观察到，轻微地提高我们的不可近似性因子足以排除启发式，即，显示平均情况下和最坏情况下的NP复杂性之间的等价性。我们还取得了进展的另一个长期悬而未决的问题，显示NP-硬度的最小电路尺寸问题（MCSP）。我们证明了NP-困难的部分函数变体的MCSP以及其他元计算问题，如问题MKTP* 和MINKT* 的计算时间有界的Kolmogorov复杂性的一个给定的部分字符串，随机多项式时间减少。我们的证明是算法信息（a.k. a. Kolmogorov复杂度）理论。我们利用黑盒伪随机发生器的建设，如Nisan-Wigderson发电机，作为一个一次性的加密方案安全对程序的“不知道”的随机函数。我们的主要技术贡献是量化的“知识”的程序，使用条件柯尔莫哥洛夫复杂性，并表明，没有小程序可以知道许多随机函数。
A long-standing open question in computational learning theory is to prove NP-hardness of learning efficient programs, the setting of which is in between proper learning and improper learning. Ko (COLT’90, SICOMP’91) explicitly raised this open question and demonstrated its difficulty by proving that there exists no relativizing proof of NP-hardness of learning programs. In this paper, we overcome Ko’s relativization barrier and prove NP-hardness of learning programs under randomized polynomial-time many-one reductions. Our result is provably non-relativizing, and comes somewhat close to the parameter range of improper learning: We observe that mildly improving our inapproximability factor is sufficient to exclude Heuristica, i.e., show the equivalence between average-case and worst-case complexities of N P. We also make progress on another long-standing open question of showing NP-hardness of the Minimum Circuit Size Problem (MCSP). We prove NP-hardness of the partial function variant of MCSP as well as other meta-computational problems, such as the problems MKTP*and MINKT*of computing the time-bounded Kolmogorov complexity of a given partial string, under randomized polynomial-time reductions. Our proofs are algorithmic information (a.k. a. Kolmogorov complexity) theoretic. We utilize black-box pseudorandom generator constructions, such as the Nisan-Wigderson generator, as a one-time encryption scheme secure against a program which “does not know” a random function. Our key technical contribution is to quantify the “knowledge” of a program by using conditional Kolmogorov complexity and show that no small program can know many random functions.
登录
查看更多内容
关于 NP 问题的最坏情况到平均情况的减少
DOI：
10.1109/sfcs.2003.1238205
发表时间：
2003
期刊：
44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.
影响因子：
--
作者：
Andrej Bogdanov;L. Trevisan
通讯作者：
L. Trevisan
给定真值表时最小化析取范式公式和 AC0 电路
DOI：
10.1137/060664537
发表时间：
2008
期刊：
SIAM J. Comput.
影响因子：
--
作者：
Eric Allender;L. Hellerstein;Paul McCabe;T. Pitassi;M. Saks
通讯作者：
M. Saks
伪随机发生器、典型正确的去随机化和电路下界
影响因子：
1.4
作者：
Jeff Kinne;D. Melkebeek;Ronen Shaltiel
通讯作者：
Ronen Shaltiel
从上到下接近 MCSP：条件变体和 AC^0[p] 的硬度
DOI：
10.4230/lipics.itcs.2020.34
发表时间：
2020
期刊：
2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
Rahul Ilango
通讯作者：
Rahul Ilango
相对启发式中的最坏情况学习
DOI：
--
发表时间：
2022
期刊：
影响因子：
--
作者：
Matsumoto Norifumi;Nakagawa Masaya;Ueda Masahito;Shuichi Hirahara and Mikito Nanashima
通讯作者：
Shuichi Hirahara and Mikito Nanashima