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.
DIMACS Home Page