P-selectivity: Intersections and indices
From MaRDI portal
Publication:673115
DOI10.1016/0304-3975(94)00290-YzbMATH Open0873.68065MaRDI QIDQ673115FDOQ673115
Lane A. Hemaspaandra, Zhigen Jiang
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Complexity classes without machines: on complete languages for UP
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Polynomial-Time Membership Comparable Sets
- Semirecursive Sets and Positive Reducibility
- On self-reducibility and weak P-selectivity
- Computing Solutions Uniquely Collapses the Polynomial Hierarchy
- Reductions on NP and p-selective sets
- Separating complexity classes with tally oracles
- Defying upward and downward separation
- The use of lists in the study of undecidable problems in automata theory
- On Circuit-Size Complexity and the Low Hierarchy in NP
- BANISHING ROBUST TURING COMPLETENESS
- Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
Cited In (9)
- Title not available (Why is that?)
- Title not available (Why is that?)
- NP-hard sets are superterse unless NP is small
- Closure and nonclosure properties of the classes of compressible and rankable sets
- Query-monotonic Turing reductions
- Boolean operations, joins, and the extended low hierarchy
- Title not available (Why is that?)
- Reducibility classes of P-selective sets
- Optimal advice
Recommendations
This page was built for publication: P-selectivity: Intersections and indices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q673115)
