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

2000/11/16 by Christian Glaßer, Christian Glasser, Glasser, Christian +2
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.1.2 #F.1.3 #FOS: Computer and information sciences #Machine Learning and Algorithms #Optimization and Search Problems #cs.CC #cs.DS

paper · pdf · doi:10.48550/arxiv.cs/0011019

20 pages, 1 table

arxiv created 2000/11/16 · openalex publication_date 2000/11/16 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis

Related

• NP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaney's Theorem, with applications
• P is a proper subset of NP
• NP-Hardness and Inapproximability of Sparse PCA
• A Moment of Perfect Clarity I: The Parallel Census Technique
• Separating the complexity classes NL and NP