A Moment of Perfect Clarity II: Consequences of Sparse Sets Hard for NP with Respect to Weak Reductions
classification
💻 cs.CC
cs.DS
keywords
reductionshardsetssparseadvancesclarityclasscollapses
read the original abstract
This paper discusses advances, due to the work of Cai, Naik, and Sivakumar and Glasser, in the complexity class collapses that follow if NP has sparse hard sets under reductions weaker than (full) truth-table reductions.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.