On symmetric differences of NP-hard sets with weakly P-selective sets
From MaRDI portal
Publication:1314375
DOI10.1016/0304-3975(93)90292-2zbMath0805.68042MaRDI QIDQ1314375
Publication date: 26 January 1995
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(93)90292-2
03D15: Complexity of computation (including implicit computational complexity)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Cites Work
- Unnamed Item
- On self-reducibility and weak P-selectivity
- Some observations on NP real numbers and P-selective sets
- Reductions on NP and p-selective sets
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- A Note on Sparse Complete Sets
- On polynomial-time truth-table reducibility of intractable sets to P-selective sets
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- On Sets Truth-Table Reducible to Sparse Sets
- On lower bounds of the closeness between complexity classes
- Semirecursive Sets and Positive Reducibility