Relations between diagonalization, proof systems, and complexity gaps
DOI10.1016/0304-3975(79)90047-1zbMath0398.68013MaRDI QIDQ1254105
Publication date: 1979
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/6561
Gap Theorem; Complexity Classes; Diagonal Processes over Time Bounded Computations; Existence of Sharp Time Bounds; One-Tape Turing Machines; Proof Systems; Tape Bound Computations
68Q25: Analysis of algorithms and problem complexity
68Q65: Abstract data types; algebraic specification
03D15: Complexity of computation (including implicit computational complexity)
03D20: Recursive functions and relations, subrecursive hierarchies
03D60: Computability and recursion theory on ordinals, admissible sets, etc.
Related Items
Cites Work
- Optimization Among Provably Equivalent Programs
- Theory of Provable Recursive Functions
- Two-Tape Simulation of Multitape Turing Machines
- Computational Complexity of One-Tape Turing Machine Computations
- An Overview of the Theory of Computational Complexity
- Computational Complexity and the Existence of Complexity Gaps