scientific article; zbMATH DE number 3883614

From MaRDI portal
Publication:3217606





[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.











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)