Robust algorithms: a different approach to oracles

DOI10.1016/0304-3975(85)90158-6zbMath0574.68041OpenAlexW1988529552MaRDI QIDQ1063417

Uwe Schoening

Publication date: 1985

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

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

zbMATH Keywords

polynomial-time algorithmoracle Turing machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Related Items

Revisiting a result of Ko, On helping by parity-like languages, On helping by robust oracle machines, Query-monotonic Turing reductions, Unambiguous computations and locally definable acceptance types, Promise problems and access to unambiguous computation, A note on the self-witnessing property of computational problems, The Helping Hierarchy, Robust machines accept easy sets, Fault-tolerance and complexity (Extended abstract), Constructive complexity, On quasilinear-time complexity theory, Helping by unambiguous computation and probabilistic computation, On being incoherent without being very hard, Classes of bounded nondeterminism, Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly

Cites Work

• BPP and the polynomial hierarchy
• A note on sparse oracles for NP
• Relative complexity of checking and evaluating
• On Restricting the Size of Oracles Compared with Restricting Access to Oracles
• Quantitative Relativizations of Complexity Classes
• “Helping”: several formalizations
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• The Power of Dominance Relations in Branch-and-Bound Algorithms
• Computational Complexity of Probabilistic Turing Machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item