DIMACS TR: 96-40
Sparse Hard Sets for P
Authors: Dieter van Melkebeek, Mitsunori Ogihara
ABSTRACT
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