A Moment of Perfect Clarity II: Consequences of Sparse Sets Hard for NP with Respect to Weak Reductions

Simple item page
dc.creatorGlasser, Christian
dc.creatorHemaspaandra, Lane A.
dc.date2000-11-16
dc.date.accessioned2026-07-07T03:16:43Z
dc.date.available2026-07-07T03:16:43Z
dc.descriptionThis 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.
dc.description20 pages, 1 table
dc.identifierhttps://arxiv.org/abs/cs/0011019
dc.identifierhttp://arxiv.org/abs/cs/0011019
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30458
dc.subjectComputational Complexity
dc.subjectData Structures and Algorithms
dc.subjectF.1.3; F.1.2
dc.titleA Moment of Perfect Clarity II: Consequences of Sparse Sets Hard for NP with Respect to Weak Reductions
dc.typetext

Files

Collections

arXiv