- Authors: D. van Melkebeek and M. Ogihara.
- Reference: In: D.-Z. Du and K.-I Ko (eds.),
Advances in Languages, Algorithms, and Complexity,
ISBN 0-7923-4396-4, p. 191-208.
Kluwer Academic Publishers, 1997.
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.
