On random reductions from sparse sets to tally sets (Q685530)

A set \(S\subseteq\{0,1\}^*\) is called \textit{sparse} if for each natural \(n\) it contains only a polynomial number of words of length \(n\). A set \(T\subseteq \{1\}^*\) is called tally. It is shown that every sparse set \(S\) can be many-one reduced to an appropriate tally set \(T\) by a polynomial-time, randomized reduction. The proof is based on the Chinese remainder theorem. As a consequence of the main result it is proven that there exists a tally set in NP which is complete for all sparse sets in NP under polynomial randomized many-one reduction. This is a partial answer to an open problem posed by Hartmanis and Yesha in 1984.