Separations by random oracles and “Almost” classes for generalized reducibilities

DOI10.1007/3-540-60246-1_124zbMath1193.03071OpenAlexW1906736031MaRDI QIDQ3569010

Yongge Wang, Wolfgang Merkle

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 information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30) Algorithmic randomness and dimension (03D32) Abstract and axiomatic computability and recursion theory (03D75)

Related Items (1)

Exact Pairs for Abstract Bounded Reducibilities

This page was built for publication: Separations by random oracles and “Almost” classes for generalized reducibilities