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

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

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

(9)

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

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)