On the random oracle hypothesis

DOI10.1016/S0019-9958(83)80023-0zbMath0549.68038MaRDI QIDQ3341897

Stuart A. Kurtz

Publication date: 1983

Published in: Information and Control (Search for Journal in Brave)

zbMATH Keywords

counterexamplesrandom oracle hypothesis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (11)

On bounded query machines ⋮ Bounded truth table does not reduce the one-query tautologies to a random oracle ⋮ Borel complexity and Ramsey largeness of sets of oracles separating complexity classes ⋮ On the cutting edge of relativization: The resource bounded injury method ⋮ Strong self-reducibility precludes strong immunity ⋮ On random oracle separations ⋮ The relativized relationship between probabilistically checkable debate systems, IP and PSPACE ⋮ Circuit size relative to pseudorandom oracles ⋮ The generic oracle hypothesis is false ⋮ Degrees of Dowd-type generic oracles ⋮ Towards the Actual Relationship Between NP and Exponential Time

This page was built for publication: On the random oracle hypothesis