Relations between diagonalization, proof systems, and complexity gaps

DOI10.1016/0304-3975(79)90047-1zbMath0398.68013OpenAlexW2036722394MaRDI QIDQ1254105

Juris Hartmanis

Publication date: 1979

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1813/6561

zbMATH Keywords

Gap TheoremComplexity ClassesDiagonal Processes over Time Bounded ComputationsExistence of Sharp Time BoundsOne-Tape Turing MachinesProof SystemsTape Bound Computations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract data types; algebraic specification (68Q65) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items (2)

THE FASTEST AND SHORTEST ALGORITHM FOR ALL WELL-DEFINED PROBLEMS ⋮ Consistency and Optimality

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

This page was built for publication: Relations between diagonalization, proof systems, and complexity gaps