A note on P-selective sets and closeness
From MaRDI portal
Publication:673619
DOI10.1016/0020-0190(95)00038-EzbMath0875.68420MaRDI QIDQ673619
Publication date: 28 February 1997
Published in: Information Processing Letters (Search for Journal in Brave)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A low and a high hierarchy within NP
- On self-reducibility and weak P-selectivity
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- On sparse sets in NP-P
- The polynomial-time hierarchy
- On symmetric differences of NP-hard sets with weakly P-selective sets
- Upward separation for FewP and related classes
- A Note on Sparse Complete Sets
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- Bounded Query Classes
- Sparse Sets, Lowness and Highness
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Lower bounds for the low hierarchy
- Complete sets and closeness to complexity classes
- Tally languages and complexity classes
- A refinement of the low and high hierarchies
- Semirecursive Sets and Positive Reducibility
