scientific article; zbMATH DE number 922628

MaRDI QIDQ4893148zbMATH OpenFDO

Authors Lars Kristiansen

Publication date 26 June 1997

zbMATH Keywords

computational complexityelementary reducibilityhonest functionssubrecursive degreessubrecursive jump operatorsubrecursive reducibility

Mathematics Subject Classification ID

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

Recommendations

• The complexity of information set decoding
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
• The complexity of quantitative information flow in recursive programs
• scientific article; zbMATH DE number 3922389
• Kolmogorov complexity and computably enumerable sets
• Probabilistic setting of information-based complexity
• On the Combinatorial Representation of Information
• A survey of information-based complexity

Cited in

(8)

• A jump operator on honest subrecursive degrees
• Computable irrational numbers with representations of surprising complexity
• On computational complexity and honest polynomial degrees
• Streamlined subrecursive degree theory
• Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension
• Honest elementary degrees and degrees of relative provability without the cupping property
• On classes of computable functions
• Weak jumps in the elementary degrees and jump inversion theorems

This page was built for publication:

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