Abstract
Vikraman Arvind, Johannes Köbler and Martin Mundhenk
Abstract:
In this paper we study the consequences of the existence of sparse
hard sets for different complexity classes under certain types of
deterministic, randomized and nondeterministic reductions. We show
that if an NP-complete set is bounded-truth-table reducible to a
set that conjunctively reduces to a sparse set then P=NP.
Relatedly, we show that if an NP-complete set is
bounded-truth-table reducible to a set that co-rp reduces to some set
that conjunctively reduces to a sparse set then RP=NP. We also
prove similar results under the (apparently) weaker assumption that
some solution of the promise problem (ONESAT,SAT) reduces via the
mentioned reductions to a sparse set.
Finally we consider
nondeterministic polynomial time many-one reductions to sparse and
co-sparse sets. We prove that if a coNP-complete set reduces via a
nondeterministic polynomial time many-one reduction to a co-sparse set
then PH = Theta^p_2. On the other hand, we show that
nondeterministic polynomial time many-one reductions to sparse sets
are as powerful as nondeterministic Turing reductions to sparse sets.