Generalized Kolmogorov Complexity in Relativized Separations (Extended Abstract)
Generalized Kolmogorov Complexity in Relativized Separations (Extended Abstract)
复制标题
相对化分离中的广义柯尔莫哥洛夫复杂性（扩展摘要）
DOI：
--
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
J. Balcázar
中科院分区：
文献类型：
--
作者：
Ricard Gavaldà;L. Torenvliet;O. Watanabe;J. Balcázar
我们描述了 Hartmanis 提出的一种技术的几种发展，该技术使用 Kolmogorov 复杂性来证明分离复杂性类别的相对化的存在。这些证明的主要优点是它们清楚地显示了某些类别的预言机的局限性以及这些限制与证明的相关性。这些限制是指定义该类的机器能够处理柯尔莫哥洛夫复杂结构的程度。
We describe several developments of a technique, due to Hartmanis, that uses Kolmogorov complexity to prove the existence of relativizations separating complexity classes. The main advantage of these proofs is that they clearly show the limitations of certain classes of oracle machines and the relevance of these limitations for the proof. Such limitations refer to the extent to which the machines defining the class are able to process Kolmogorov-complex structures.