Additional queries to random and pseudorandom oracles

DOI10.1007/BFB0032039MaRDI QIDQ4038699zbMATH OpenFDO

Authors Ronald V. Book, Jack H. Lutz, Shouwen Tang

Publication date 18 May 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0032039

zbMATH Keywords

additional query propertyoracle setpspace-random

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

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

Recommendations

• The global power of additional queries to p-random oracles
• The global power of additional queries to p-random oracles
• scientific article; zbMATH DE number 512800
• scientific article; zbMATH DE number 4049050
• The global power of additional queries to random oracles

Cited in

(4)

• The global power of additional queries to p-random oracles
• Random Oracles and Auxiliary Input
• scientific article; zbMATH DE number 512800 (Why is no real title available?)
• Augmented random oracles

This page was built for publication: Additional queries to random and pseudorandom oracles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4038699)