Additional queries to random and pseudorandom oracles (Q4038699)

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 177821
Language Label Description Also known as
default for all languages
No label defined
    English
    Additional queries to random and pseudorandom oracles
    scientific article; zbMATH DE number 177821

      Statements

      0 references
      0 references
      0 references
      18 May 1993
      0 references
      oracle set
      0 references
      additional query property
      0 references
      pspace-random
      0 references
      Additional queries to random and pseudorandom oracles (English)
      0 references
      [For the entire collection see Zbl 0758.00017.] An oracle set \(S\) is said to have the additional query property if the ability to make more queries about membership in \(S\) enlarges the class of languages reducible to \(S\). This paper first announces that with probability one a randomly selected oracle set has the additional query property. Furthermore, it is also announced that if \(x\) is pspace-random then \(x\) has the additional query property relative to \(f\) for any \(f\) in \(P\).
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references