The Global Power of Additional Queries toP-Random Oracles

DOI10.1137/S0097539700366711zbMath0997.03039MaRDI QIDQ2784467

Wolfgang Merkle

Publication date: 23 April 2002

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

random setsresource bounded measurequery complexityrandom oraclesbounded truth-table reducibilityresource-bounded reducibilitieseffective measureeffective reducibilitiesseparation of reducibilities

Mathematics Subject Classification ID

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)

Related Items

Some connections between bounded query classes and non-uniform complexity.