Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

On Bounded Truth-Table, Conjunctive, and Randomized Reductions to Sparse Sets

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.

Ps-File: On Bounded Truth-Table, Conjunctive, and Randomized Reductions to Sparse Sets