On classes of computable functions

DOI10.1145/800169.805421MaRDI QIDQ5402505zbMATH OpenOpenAlexFDO

Authors Sanat K. Basu

Publication date 14 March 2014

Published in Proceedings of the first annual ACM symposium on Theory of computing - STOC '69 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/800169.805421

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20)

Recommendations

• Classes of computable functions defined by bounds on computation
• Completeness problems in classes of computable named functions
• On Closed Classes of Primitive Recursive Functions, II
• scientific article; zbMATH DE number 4112573
• scientific article; zbMATH DE number 922628

Cited in

(15)

• Abstract complexity theory and the \(\Delta_{2}^{0}\) degrees
• Bases for \(\mathrm{AC}^{0}\) and other complexity classes
• scientific article; zbMATH DE number 4112573 (Why is no real title available?)
• The Veblen functions for computability theorists
• scientific article; zbMATH DE number 4068864 (Why is no real title available?)
• Classes of computable functions defined by bounds on computation
• scientific article; zbMATH DE number 4094815 (Why is no real title available?)
• scientific article; zbMATH DE number 2061073 (Why is no real title available?)
• Classifying the Provably Total Functions of PA
• Completeness problems in classes of computable named functions
• Functions computable with limited access to NP
• scientific article; zbMATH DE number 4033742 (Why is no real title available?)
• On Computational Constructions in Function Spaces
• Some characterizations of functions computable in on-line arithmetic
• An operator embedding theorem for complexity classes of recursive functions

This page was built for publication: On classes of computable functions

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