Reductions to sets of low information content. (English) Zbl 0794.68058

Arvind, V.; Han, Y.; Hemachandra, L.; Köbler, J.; Lozano, A.; Mundhenk, M.; Ogiwara, M.; Schöning, U.; Silvestri, R.; Thierauf, T.

Ambos-Spies, Klaus (ed.) et al., Complexity theory. Current research. Proceedings of the workshop on structure and complexity held at the Dagstuhl International Conference and Research Center, Wadern, Germany, February 2-8, 1992. Cambridge: Cambridge University Press. 1-45 (1993).

The paper is concerned with two basic questions about sparse sets, and a related question about sets of low instance complexity:
Question 1: With respect to what types of reductions might NP have hard or complete sparse sets?
Question 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\)?
Question 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.
For the entire collection see [Zbl 0782.00046].

Reviewer: L.Hemachandra (Rochester)

MSC:

68Q15	Complexity classes (hierarchies, relations among complexity classes, etc.)
03D15	Complexity of computation (including implicit computational complexity)

Keywords:

computational complexity; low information; sparse sets; low instance complexity