Abstract
Vikraman Arvind, Johannes Köbler and Martin Mundhenk
Abstract:
An oracle machine is called monotonous, if after a
negative answer the machine does not ask further queries
to the oracle. For example, one-query truth-table,
conjunctive, and Hausdorff reducibilities are
monotonous. We study the consequences of the existence
of sparse hard sets for different complexity classes
under monotonous and randomized reductions. We prove
trade-offs between the randomized time complexity of
NP sets that reduce to a set B via such reductions
and the density of B as well as the number of queries
made by the monotonous reduction. As a consequence,
bounded Turing hard sets for NP are not co-rp
reducible to a sparse set unless RP=NP. We also
prove similar results under the apparently weaker
assumption that some solution of the promise problem
(1SAT,SAT) reduces via the mentioned reductions to
a sparse set.