Monotonous and Randomized Reductions to Sparse Sets
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.
Ps-File: Monotonous and Randomized Reductions to Sparse Sets