A note on sparse oracles for NP

DOI10.1016/0022-0000(82)90050-2zbMath0486.68033OpenAlexW2040387487MaRDI QIDQ1164997

Timothy J. Long

Publication date: 1982

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

Full work available at URL: https://doi.org/10.1016/0022-0000(82)90050-2

zbMATH Keywords

polynomial-time hierarchysparse complete sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hierarchies of computability and definability (03D55)

Related Items

\(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\), On polynomial-time truth-table reducibility of intractable sets to P-selective sets, \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP], New developments in structural complexity theory, Complete sets and closeness to complexity classes, On small generators, Robust algorithms: a different approach to oracles, Kolmogorov characterizations of complexity classes

Cites Work

• Unnamed Item
• Unnamed Item
• A comparison of polynomial time reducibilities
• The polynomial-time hierarchy
• A Note on Sparse Complete Sets
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• The complexity of theorem-proving procedures