Characterization of realizable space complexities

DOI10.1016/0168-0072(94)00026-YzbMath0826.03019OpenAlexW2091585331MaRDI QIDQ1892934

Albert R. Meyer, Joel I. Seiferas

Publication date: 3 July 1995

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0168-0072(94)00026-y

zbMATH Keywords

specificationpartial functioninherent space complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (4)

Computational complexity of functions ⋮ Effective category and measure in abstract complexity theory ⋮ Effective category and measure in abstract complexity theory ⋮ Amplification of slight probabilistic advantage at absolutely no cost in space

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Halting space-bounded computations
• Relating refined space complexity classes
• Computational complexity of functions
• Gödel numberings of partial recursive functions
• A characterization of complexity sequences
• Easy Constructions in Complexity Theory: Gap and Speed-Up Theorems
• “Helping”: several formalizations
• A Machine-Independent Theory of the Complexity of Recursive Functions
• On Effective Procedures for Speeding Up Algorithms
• The Operator Gap
• Computational speed-up by effective operators
• Computational Complexity and the Existence of Complexity Gaps

This page was built for publication: Characterization of realizable space complexities