On Effective Procedures for Speeding Up Algorithms

DOI10.1145/321637.321648MaRDI QIDQ5625127zbMATH OpenOpenAlexFDO

Authors Manuel Blum

Publication date 1971

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/321637.321648

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Recursive functions and relations, subrecursive hierarchies (03D20)

Cited in

(22)

• Uncontrollable computational growth in theoretical physics
• Complexity classes of provable recursive functions
• Complexity of algorithms and computations
• Two notions of correctness and their relation to testing
• The complexity of the word problems for commutative semigroups and polynomial ideals
• Characterization of realizable space complexities
• On low for speed oracles
• Intensional Kleene and Rice theorems for abstract program semantics
• THE FASTEST AND SHORTEST ALGORITHM FOR ALL WELL-DEFINED PROBLEMS
• On low for speed oracles
• Classifying the computational complexity of problems
• Easy Constructions in Complexity Theory: Gap and Speed-Up Theorems
• On complexity properties of recursively enumerable sets
• Relativization of the Theory of Computational Complexity
• General random sequences and learnable sequences
• Computational complexity, speedable and levelable sets
• Implicit measurements of dynamic complexity properties and splittings of speedable sets
• Computational speed-up by effective operators
• On the polynomial IO-complexity
• A Rice's theorem for abstract semantics
• Speed-up theorems in type-2 computations using oracle Turing machines
• Toward an abstract theory of data compression

This page was built for publication: On Effective Procedures for Speeding Up Algorithms

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