Martin Mundhenk:
Hausdorff Reduktionen zu Mengen mit geringem Informationsgehalt
(Hausdorff reductions to sets of low information content)
(PhD Dissertation'93)
Reductions of $\NP$-complete sets to sparse sets
play an important role in structural complexity theory.
Since the conjecture of Berman and Hartmanis (1977)
that an $\NP$-complete set cannot be sparse,
much effort has been spent in research in this topic.
Mahaney (1982) proved that sparse $\NP$-hard sets
under polynomial-time many-one reducibility cannot exist unless $\P=\NP$.
This result was followed by many others deriving
under the same hypothesis non-existence of
sparse $\NP$-hard sets for more general types of
reducibilities.
This lead to the independent results of Ogiwara and Watanabe (1991)
for bounded truth-table reducibility and Arvind et al. (1992)
for the case of conjunctive reducibility.
This thesis compares structural properties of sets
in the Polynomial Hierarchy with sets which reduce
to sparse sets via different types of reducibility.
At first the structure of classes defined by
reducibilities to sparse sets is considered.
The Hausdorff reducibility (Wagner 1980) is for the first time
considered in this context.
Properties of this reducibility
are then used to show that the existence of
sparse $\NP$-hard sets under the composition of
bounded Hausdorff
-- which is the same as bounded truth-table in this case --
and conjunctive reducibility implies $\P=\NP$,
generalizing the known results in this area.
Weakening from bounded to unbounded Hausdorff
reducibility a collaps of the Polynomial Hierarchy
to $\P^{\NP}$ is derived. It is shown that this collaps also follows
from the existence of sparse $\NP$-hard sets under
disjunctive reducibility.
All the above mentioned reduction classes to sparse sets
are also placed in the $\EL^{p,\theta}_3$-level of the
Extended Low-Hierarchy.
The results can be interpreted intuitively in a way that
the information content of sets reducible to
sparse sets is very low compared with sets
in the Polynomial Hierarchy.
Surprisingly, it also turns out that
sets of high information density
(defined similar to the ``high sets'' of Book and Lutz 1992)
being the natural counterpart of sets of low information
content have not more use as oracles.
It is shown that
sets in ESPACE
can be reduced (under the above reducibility types)
to sets of high information density
if and only if they are reducible to sparse sets.
Back to my homepage