Quantitative aspects of speed-up and gap phenomena

DOI10.1017/S0960129510000174zbMath1226.03050OpenAlexW2082093671MaRDI QIDQ3060186

Thorsten Kräling, Ambos-Spies, Klaus

Publication date: 1 December 2010

Published in: Mathematical Structures in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0960129510000174

zbMATH Keywords

gap theoremstructural complexity theorycomputable operatoreffective measureeffective Baire categorynon-speedable problemsspeedable problems

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Theory of numerations, effectively presented structures (03D45)

Related Items (1)

Comparing nontriviality for E and EXP

Cites Work

• Unnamed Item
• Effective category and measure in abstract complexity theory
• Almost everywhere high nonuniform complexity
• Almost every set in exponential time is P-bi-immune
• Process complexity and effective random tests
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Computational speed-up by effective operators
• Computational Complexity and the Existence of Complexity Gaps

This page was built for publication: Quantitative aspects of speed-up and gap phenomena