Separations by random oracles and ``almost classes for generalized reducibilities

DOI10.1007/3-540-60246-1_124MaRDI QIDQ3569010zbMATH OpenOpenAlexFDO

Authors Wolfgang Merkle, Y. Wang

Publication date 17 June 2010

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

Full work available at URL https://doi.org/10.1007/3-540-60246-1_124

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Algorithmic randomness and dimension (03D32) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Abstract and axiomatic computability and recursion theory (03D75)

Recommendations

• Separations by random oracles and ``almost classes for generalized reducibilities
• scientific article; zbMATH DE number 1670881
• The global power of additional queries to \(p\)-random oracles
• On Languages Reducible to Algorithmically Random Languages
• scientific article; zbMATH DE number 3995648

Cited in

(8)

• The global power of additional queries to \(p\)-random oracles
• Polynomial clone reducibility
• Separations by random oracles and ``almost classes for generalized reducibilities
• Weak randomness, genericity and Boolean decision trees
• Exact Pairs for Abstract Bounded Reducibilities
• Maximal pairs of computably enumerable sets in the computably Lipschitz degrees
• scientific article; zbMATH DE number 3995648 (Why is no real title available?)
• On random oracle separations

This page was built for publication: Separations by random oracles and ``almost classes for generalized reducibilities

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