On size vs. efficiency for programs admitting speed-ups

DOI10.2307/2271512MaRDI QIDQ5674405zbMATH OpenOpenAlexFDO

Authors

Publication date 1971

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2307/2271512

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20) Analysis of algorithms and problem complexity (68Q25)

Cites work

• A Machine-Independent Theory of the Complexity of Recursive Functions
• On the size of machines

Cited in

(7)

• Uncontrollable computational growth in theoretical physics
• Complexity of algorithms and computations
• On recursive bounds for the exceptional values in speed-up
• Easy Constructions in Complexity Theory: Gap and Speed-Up Theorems
• Effective category and measure in abstract complexity theory
• Computational speed-up by effective operators
• Effective category and measure in abstract complexity theory

This page was built for publication: On size vs. efficiency for programs admitting speed-ups

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