On size vs. efficiency for programs admitting speed-ups

DOI10.2307/2271512zbMath0258.68023OpenAlexW2121669037MaRDI QIDQ5674405

No author found.

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

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

Related Items (7)

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

Cites Work

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

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