Characterization of reduction classes modulo oracle conditions (Q3763590)

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 4020479
Language Label Description Also known as
default for all languages
No label defined
    English
    Characterization of reduction classes modulo oracle conditions
    scientific article; zbMATH DE number 4020479

      Statements

      Characterizations of reduction classes modulo oracle conditions (English)
      0 references
      Characterization of reduction classes modulo oracle conditions (English)
      0 references
      0 references
      0 references
      1984
      0 references
      complexity classes of formal languages
      0 references
      nondeterministic reducibilities
      0 references
      polynomial time Turing reducibility
      0 references
      oracle conditions
      0 references
      reduction classes
      0 references
      polyomial space
      0 references
      It is known that nondeterministic polynomial time truth-table reducibility is exactly the same as nondeterministic polynomial time Turing reducibility. Here we study the standard nondeterministic reducibilities (conjunctive, bounded truth-table, bounded positive truth- table, and many-one) and show that each is a restriction of nondeterministic polynomial time Turing reducibility corresponding to acceptance modulo a set of ``oracle conditions''. Then we show that the reduction classes of these reducibilities are classes of formal languages and as such have language theoretic characterization theorems. The same program is carried out for polyomial space.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references