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
18 May 1993
0 references
oracle set
0 references
additional query property
0 references
pspace-random
0 references
0.8230103254318237
0 references
0.8230103254318237
0 references
0.8184819221496582
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