On symmetric differences of NP-hard sets with weakly P-selective sets

DOI10.1016/0304-3975(93)90292-2zbMath0805.68042OpenAlexW2093889711MaRDI QIDQ1314375

Bin Fu, Hong-zhou Li

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

zbMATH Keywords

sparse setsNP-hard setsweakly \(p\)-selective

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

A note on P-selective sets and closeness

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