Relative to a random oracle, NP is not small

DOI10.1006/jcss.1996.0065zbMath0859.68033OpenAlexW2059025729MaRDI QIDQ1816731

Steven M. Kautz, Peter Bro Miltersen

Publication date: 31 March 1997

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1996.0065

zbMATH Keywords

resource-bounded measuretime-bounded Turing machine

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

An excursion to the Kolmogorov random strings ⋮ The size of SPP ⋮ Inseparability and strong hypotheses for disjoint NP pairs ⋮ Relativized worlds with an infinite hierarchy

This page was built for publication: Relative to a random oracle, NP is not small