Complexity classes of provable recursive functions

DOI10.1016/0022-0000(79)90037-0MaRDI QIDQ1134153zbMATH OpenOpenAlexFDO

Authors 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)

Cites work

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

Cited in

(1)

• Independence results in computer science?

This page was built for publication: Complexity classes of provable recursive functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1134153)