Sparse Sets in : Relativizations

DOI10.1137/0214008MaRDI QIDQ3691647zbMATH OpenOpenAlexFDO

Authors Stuart A. Kurtz

Publication date 1985

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

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

zbMATH Keywords

diagonalizationforcingoracle

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• On sparse oracles separating feasible complexity classes
• scientific article; zbMATH DE number 3978383
• On Restricting the Size of Oracles Compared with Restricting Access to Oracles
• Relativizing relativized computations
• scientific article; zbMATH DE number 500314

Cited in

(19)

• Reductions among polynomial isomorphism types
• On sparse oracles separating feasible complexity classes
• A note on sparse sets and the polynomial-time hierarchy
• Easy sets and hard certificate schemes
• There are no sparse NP\(_{w}\)-hard sets
• Limitations of the upward separation technique
• scientific article; zbMATH DE number 3926243 (Why is no real title available?)
• On Restricting the Size of Oracles Compared with Restricting Access to Oracles
• scientific article; zbMATH DE number 3978383 (Why is no real title available?)
• scientific article; zbMATH DE number 4080915 (Why is no real title available?)
• Towards the Actual Relationship Between NP and Exponential Time
• scientific article; zbMATH DE number 1072529 (Why is no real title available?)
• scientific article; zbMATH DE number 1107624 (Why is no real title available?)
• scientific article; zbMATH DE number 1834655 (Why is no real title available?)
• NP-Creative sets: A new class of creative sets in NP
• NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN
• Oracle-dependent properties of the lattice of NP sets
• Downward translations of equality
• On the complexity of test case generation for NP-hard problems

This page was built for publication: Sparse Sets in : Relativizations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3691647)