Robust algorithms: a different approach to oracles
type: Item
instance of: scholarly article
title: Robust algorithms: a different approach to oracles
zbMATH Open document ID: 0574.68041
DOI: 10.1016/0304-3975(85)90158-6
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
review text: See the review of the preliminary version [Lect. Notes Comput. Sci. 172, 448-453 (1984; Zbl 0554.68034)].
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W99
zbMATH DE Number: 3917712
zbMATH Keywords: oracle Turing machine
zbMATH Keywords: polynomial-time algorithm
author: Uwe Schöning
MaRDI profile type: Publication
full work available at URL: 0304-3975(85)90158-6
OpenAlex ID: W1988529552
cites work: Q3691059
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: Quantitative Relativizations of Complexity Classes
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: Q5592246
cites work: The Power of Dominance Relations in Branch-and-Bound Algorithms
cites work: Q4142699
cites work: Q3957950
cites work: BPP and the polynomial hierarchy
cites work: A note on sparse oracles for NP
cites work: On Restricting the Size of Oracles Compared with Restricting Access to Oracles
cites work: “Helping”: several formalizations
cites work: Q3662618
cites work: Relative complexity of checking and evaluating
Recommended article: Q3217606
Recommended article: Q4967176
Recommended article: Robust algorithms for restricted domains
Recommended article: A note on the nonexistence of oracle-polynomial algorithms for robust combinatorial optimization
Recommended article: Robust algorithms for the stable set problem
Recommended article: On helping by robust oracle machines
Recommended article: Robustness analysis for stochastic approximation algorithms
Recommended article: Q5066958
description: scientific article; zbMATH DE number 3917712