A Moment of Perfect Clarity II: Consequences of Sparse Sets Hard for NP with Respect to Weak Reductions
<|reference_start|>A Moment of Perfect Clarity II: Consequences of Sparse Sets Hard for NP with Respect to Weak Reductions: 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.<|reference_end|>
@article{glasser2000a,
    title={A Moment of Perfect Clarity II: Consequences of Sparse Sets Hard for NP
  with Respect to Weak Reductions},
    author={Christian Glasser and Lane A. Hemaspaandra},
    journal={arXiv preprint arXiv:cs/0011019},
    year={2000},
    number={URCS-TR-2000-738},
    archivePrefix={arXiv},
    eprint={cs/0011019},
    primaryClass={cs.CC cs.DS}
}