NONDETERMINISTICALLY SELECTIVE SETS

DOI10.1142/S0129054195000214MaRDI QIDQ4867411zbMATH OpenFDO

Authors Lane A. Hemaspaandra, Albrecht Hoene, Ashish V. Naik, Ogihara, Mitsunori, Alan L. Selman, Thomas Thierauf, Jie Wang

Publication date 13 August 1996

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054195000214

zbMATH Keywords

NP-selective sets

Mathematics Subject Classification ID

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

Recommendations

• On sets bounded truth-table reducible to P-selective sets
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• Adaptive versus nonadaptive queries to NP and P-selective sets
• p-selective self-reducible sets: a new characterization of P

Cited in

(14)

• On simple and creative sets in NP
• On the reducibility of sets inside NP to sets with low information content
• Competing provers yield improved Karp-Lipton collapse results
• p-Selective sets and reducing search to decision vs. self-reducibility
• Adaptive versus nonadaptive queries to NP and P-selective sets
• NP-hard sets are superterse unless NP is small
• scientific article; zbMATH DE number 4014026 (Why is no real title available?)
• scientific article; zbMATH DE number 1543037 (Why is no real title available?)
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• ADVICE FOR SEMIFEASIBLE SETS AND THE COMPLEXITY-THEORETIC COST(LESSNESS) OF ALGEBRAIC PROPERTIES
• Theory of semi-feasible algorithms
• The shrinking property for NP and coNP
• Nondeterministic functions and the existence of optimal proof systems
• The Boolean hierarchy of NP-partitions

This page was built for publication: NONDETERMINISTICALLY SELECTIVE SETS

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