Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
复制标题
Ker-I Ko 与资源有限 Kolmogorov 复杂性研究
DOI：
10.1007/978-3-030-41672-0_2
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Allender, Eric
中科院分区：
文献类型：
--
作者：
Allender, Eric
Ker-I Ko是最早认识到资源受限Kolmogorov复杂性作为更好地理解复杂性类结构的工具的重要性的人之一。在这个简短的非正式回忆中，我回顾了20世纪80年代初的环境，这引起了对资源受限的Kolmogorov复杂性的兴趣，然后我讨论了一些最近的工作，这些工作进一步阐明了Ko在20世纪80年代和90年代努力解决的与Kolmogorov复杂性相关的问题。我包括一个详细的讨论柯的工作的问题，它是否很难确定的时间有界的柯尔莫哥洛夫复杂性的一个给定的字符串。这个问题与最小电路尺寸问题（）密切相关，最小电路尺寸问题是计算复杂性理论中几项当代研究的核心。
Ker-I Ko was among the first people to recognize the importance of resource-bounded Kolmogorov complexity as a tool for better understanding the structure of complexity classes. In this brief informal reminiscence, I review the milieu of the early 1980’s that caused an up-welling of interest in resource-bounded Kolmogorov complexity, and then I discuss some more recent work that sheds additional light on the questions related to Kolmogorov complexity that Ko grappled with in the 1980’s and 1990’s.In particular, I include a detailed discussion of Ko’s work on the question of whether it is-hard to determine the time-bounded Kolmogorov complexity of a given string. This problem is closely connected with the Minimum Circuit Size Problem (), which is central to several contemporary investigations in computational complexity theory.
登录
查看更多内容
从上到下接近 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：
--
发表时间：
1990
期刊：
International Symposium on Mathematical Foundations of Computer Science
影响因子：
--
作者：
Ricard Gavaldà;L. Torenvliet;O. Watanabe;J. Balcázar
通讯作者：
J. Balcázar
DOI：
--
发表时间：
1992
期刊：
Currents in Research
影响因子：
--
作者：
V. Arvind;Yenjo Han;L. Hemaspaandra;J. Köbler;A. Lozano;M. Mundhenk;Mitsunori Ogihara;U. Schöning;R. Silvestri;T. Thierauf
通讯作者：
T. Thierauf
计算复杂性理论中资源有限的柯尔莫哥洛夫复杂性的普遍影响
DOI：
10.1016/j.jcss.2010.06.004
发表时间：
2009
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Eric Allender;M. Koucký;Detlef Ronneburger;Sambuddha Roy
通讯作者：
Sambuddha Roy
DOI：
10.1007/978-3-030-11298-1
发表时间：
2019
期刊：
--
影响因子：
--
作者：
Ming Li;P. Vitányi
通讯作者：
Ming Li;P. Vitányi