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)

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

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)