V.Arvind, Y. Han, L. Hemachandra, J. Köbler, A. Lozano, M. Mundhenk,
A. Ogiwara, U. Schöning, R. Silvestri, and T. Thierauf
Abstract:
This paper is concerned with three basic questions about sparse sets:
- With respect to what types of reductions might NP have hard or
complete sparse sets?
- If a set A reduces to a sparse set, does it
follow that A is reducible to some sparse set that is ``simple''
relative to A?
- With respect to what types of reductions might NP
have hard or complete sets of low instance complexity, and, relatedly,
what is the structure of the class of sets with low instance
complexity?
With respect to the first and third questions, intuitively
one would expect that even with respect to flexible reductions NP is
unlikely to have complete sets whose information content is low. With
respect to the second question, one might intuitively feel that the
structure imposed on a set by the fact that it reduces to a sparse set
makes it plausible that we can indeed find a simple sparse set that
can masquerade as the original sparse set. These two intuitions are
in many ways certified by the current literature, and by the results
of this paper.
Not all proofs are included in the journal version of the paper.
Here
you find the full version which is University of Rochester TR 417, 1992.