DIMACS TR: 96-40

Sparse Hard Sets for P

Authors: Dieter van Melkebeek, Mitsunori Ogihara


Sparse hard sets for complexity classes has been a central topic for two decades. The area is motivated by the desire to clarify relationships between completeness/hardness and density of languages and studies the existence of sparse complete/hard sets for various complexity classes under various reducibilities. Very recently, we have seen remarkable progress in this area for low-level complexity classes. In particular, the Hartmanis' sparseness conjectures for P and NL have been resolved. This article overviews the history of sparse hard set problems and exposes some of the recent results.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-40.ps.gz
DIMACS Home Page