Effective category and measure in abstract complexity theory

DOI10.1016/0304-3975(95)00066-6zbMath0872.03027OpenAlexW2073296504WikidataQ57001764 ScholiaQ57001764MaRDI QIDQ672752

Marius Zimand, Cristian S. Calude

Publication date: 28 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(95)00066-6

zbMATH Keywords

complexity classes of recursive predicatescompression theoremeffective version of Baire category theoremoperator gap theoremoperator speed-up theorem

Mathematics Subject Classification ID

Constructive and recursive analysis (03F60) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Theory of numerations, effectively presented structures (03D45)

Related Items (1)

Quantitative aspects of speed-up and gap phenomena

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the topological size of p-m-complete degrees
• If not empty, NP-P is topologically large
• A note on A.E. h-complex functions
• Relativized topological size of sets of partial recursive functions
• Almost everywhere high nonuniform complexity
• Theories of computational complexity
• Families of recursive predicates of measure zero
• On recursive bounds for the exceptional values in speed-up
• Almost every set in exponential time is P-bi-immune
• Is independence an exception?
• Characterization of realizable space complexities
• Process complexity and effective random tests
• Category and Measure in Complexity Classes
• Topological Size of Sets of Partial Recursive Functions
• Easy Constructions in Complexity Theory: Gap and Speed-Up Theorems
• RECURSIVE BAIRE CLASSIFICATION AND SPEEDABLE FUNCTIONS
• Classes of computable functions defined by bounds on computation
• A Machine-Independent Theory of the Complexity of Recursive Functions
• On the size of machines
• An Overview of the Theory of Computational Complexity
• The Operator Gap
• Computational speed-up by effective operators
• On size vs. efficiency for programs admitting speed-ups
• Computational Complexity and the Existence of Complexity Gaps

This page was built for publication: Effective category and measure in abstract complexity theory