No label defined (Q3217606)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3883614
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3883614

      Statements

      1984
      0 references
      oracle Turing machine
      0 references
      polynomial-time algorithms
      0 references
      0 references
      [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.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references