On Restricting the Size of Oracles Compared with Restricting Access to Oracles

DOI10.1137/0214043zbMath0583.68025OpenAlexW4238001574MaRDI QIDQ3706504

Timothy J. Long

Publication date: 1985

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

Full work available at URL: https://doi.org/10.1137/0214043

zbMATH Keywords

sparse setspolynomial-time hierarchytally setslanguage classesnondeterministic oracle programsnondeterministic polynomial-time oracle machinesrestricted relativization of NP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (12)

On reductions of NP sets to sparse sets ⋮ On bounded query machines ⋮ Positive relativizations for log space computability ⋮ On polynomial-time truth-table reducibility of intractable sets to P-selective sets ⋮ Restricted relativizations of probabilistic polynomial time ⋮ Reducibilities on tally and sparse sets ⋮ A positive relativization of polynomial time versus polylog space ⋮ A note on sparse sets and the polynomial-time hierarchy ⋮ Sets with small generalized Kolmogorov complexity ⋮ Tally NP sets and easy census functions. ⋮ Bounded queries, approximations, and the Boolean hierarchy ⋮ Robust algorithms: a different approach to oracles

This page was built for publication: On Restricting the Size of Oracles Compared with Restricting Access to Oracles