Relativization of the Theory of Computational Complexity

DOI10.2307/1997644zbMath0353.68059OpenAlexW4247851087MaRDI QIDQ4124321

Michael J. Fischer, Albert R. Meyer, Nancy A. Lynch

Publication date: 1976

Full work available at URL: https://doi.org/10.2307/1997644

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Recursive functions and relations, subrecursive hierarchies (03D20) Turing machines and related notions (03D10) Hierarchies of computability and definability (03D55)

Related Items (8)

Results on memory-limited U-shaped learning ⋮ A note on the best-case complexity ⋮ Some results on relativized deterministic and nondeterministic time hierarchies ⋮ On being incoherent without being very hard ⋮ A comparison of polynomial time reducibilities ⋮ Complete sets and the polynomial-time hierarchy ⋮ Log space machines with multiple oracle tapes ⋮ On some natural complete operators

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Augmented loop languages and classes of computable functions
• On a Subrecursive Hierarchy and Primitive Recursive Degrees
• Gödel numberings of partial recursive functions
• Classes of Predictably Computable Functions
• Helping and the meet of pairs of honest subrecursive classes
• Honest bounds for complexity classes of recursive functions
• “Helping”: several formalizations
• Classes of computable functions defined by bounds on computation
• Degrees of Unsolvability. (AM-55)
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Uniformly introreducible sets
• Hierarchies of Primitive Recursive Functions
• On Effective Procedures for Speeding Up Algorithms
• An Overview of the Theory of Computational Complexity
• The Operator Gap
• A Classification of the Recursive Functions
• Computational speed-up by effective operators
• Computational Complexity and the Existence of Complexity Gaps
• Recursive Properties of Abstract Complexity Classes

This page was built for publication: Relativization of the Theory of Computational Complexity