Relations between diagonalization, proof systems, and complexity gaps
Relations between diagonalization, proof systems, and complexity gaps
复制标题
DOI：
10.1145/800105.803412
复制
发表时间：
1977-05
期刊：
影响因子：
--
通讯作者：
J. Hartmanis
中科院分区：
文献类型：
--
作者：
J. Hartmanis
在本文中，我们研究对角过程的时间有界计算的一个磁带图灵机对角化只在这些机器上，存在正式的证明，他们在给定的时间范围内运作。这取代了传统的“时钟”的资源有界的对角化的形式证明的运行时间，并建立了密切的关系证明系统的属性和存在的尖锐的时间界的一个磁带图灵机复杂性类。此外，这些对角化的方法表明，差距定理的资源有界的计算不成立的复杂性类，只接受图灵机，它可以正式证明，他们在所需的时间范围内运行的语言。
In this paper we study diagonal processes over time-bounded computations of one-tape Turing machines by diagonalizing only over those machines for which there exist formal proofs that they operate in the given time bound. This replaces the traditional “clock” in resource bounded diagonalization by formal proofs about running times and establishes close relations between properties of proof systems and existence of sharp time bounds for one-tape Turing machine complexity classes. Furthermore, these diagonalization methods show that the Gap Theorem for resource bounded computations does not hold for complexity classes consisting only of languages accepted by Turing machines for which it can be formally proven that they run in the required time bound.