scientific article; zbMATH DE number 3883614
[For the entire collection see Zbl 0543.00014.] The paper introduces the new concept of an oracle Turing machine being helped by an appropriate oracle set. The crucial requirement is that the oracle machine is robust, i.e. always computes the same set (or function) independent of the particular oracle. The oracle only serves to possibly speed up the computation time. The main result of this paper is that the class of sets that can be computed by deterministic polynomial- time algorithms when being helped by an appropriate oracle is exactly NP\(\cap co\)-NP. The full version will appear in a special issue of Theoretical Computer Science, 1985.
- Robust algorithms: a different approach to oracles
- On helping by robust oracle machines
- On helping by parity-like languages
- scientific article; zbMATH DE number 4172379 (Why is no real title available?)
- scientific article; zbMATH DE number 4064489 (Why is no real title available?)
- On the correctness of orphan management algorithms
- Robust algorithms for restricted domains
- scientific article; zbMATH DE number 7075880 (Why is no real title available?)
- Robust machines accept easy sets
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3217606)