P-selectivity: Intersections and indices
From MaRDI portal
Publication:673115
DOI10.1016/0304-3975(94)00290-YzbMath0873.68065MaRDI QIDQ673115
Zhigen Jiang, Hemaspaandra, Lane A.
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items
NP-hard sets are superterse unless NP is small, Query-monotonic Turing reductions, Optimal advice, Closure and nonclosure properties of the classes of compressible and rankable sets, Boolean operations, joins, and the extended low hierarchy
Cites Work
- Unnamed Item
- Unnamed Item
- On self-reducibility and weak P-selectivity
- Complexity classes without machines: on complete languages for UP
- 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
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- BANISHING ROBUST TURING COMPLETENESS
- Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
- Polynomial-Time Membership Comparable Sets
- Computing Solutions Uniquely Collapses the Polynomial Hierarchy
- Semirecursive Sets and Positive Reducibility
