Complexity classes of provable recursive functions

DOI10.1016/0022-0000(79)90037-0zbMath0423.03045OpenAlexW1996469205MaRDI QIDQ1134153

Dan Gordon

Publication date: 1979

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(79)90037-0

zbMATH Keywords

speed-up theoremsecond order arithmeticpartial recursive functions provably recursive in some formal system

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items

Independence results in computer science?

Cites Work

• Abstract computational complexity and cycling computations
• Optimization Among Provably Equivalent Programs
• Theory of Provable Recursive Functions
• A Machine-Independent Theory of the Complexity of Recursive Functions
• On Effective Procedures for Speeding Up Algorithms
• An Overview of the Theory of Computational Complexity