Reductions to Sets of Low Information Content
A. Ogiwara, U. Schöning, R. Silvestri and T. Thierauf
University of Rochester TR 417.
Monat/Jahr: April 1992
Appeared in Recent Developments in Complexity Theory , Cambridge University Press, 1993
Abstract:
This paper is concerned with three basic questions about sparse sets: (1) With respect to what types of reductions might NP have hard or complete sparse sets? (2) 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? (3) 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.
Kontaktadresse:
koebler@informatik.hu-berlin.de,
thierauf@informatik.uni-ulm.de