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

DOI10.1007/3-540-60246-1_124zbMATH Open1193.03071OpenAlexW1906736031MaRDI QIDQ3569010FDOQ3569010

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

Recommendations

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

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)

Cited In (8)

• 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
• Title not available (Why is that?)
• On random oracle separations
• The global power of additional queries to \(p\)-random oracles

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)