On random reductions from sparse sets to tally sets
type: Item
instance of: scholarly article
title: On random reductions from sparse sets to tally sets
zbMATH Open document ID: 0780.68044
DOI: 10.1016/0020-0190(93)90102-F
published in: Information Processing Letters
publication date: 1994-01-31T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 417425
zbMATH Keywords: random reduction
zbMATH Keywords: completeness
zbMATH Keywords: sparse set
zbMATH Keywords: tally set
zbMATH Keywords: NP
zbMATH Keywords: many-one reduction
author: Uwe Schöning
reviewed by: K. V. Shvachko
MaRDI profile type: Publication
cites work: Tally languages and complexity classes
cites work: SPARSE Reduces Conjunctively to TALLY
cites work: On sparse sets in NP-P
cites work: Computation times of NP sets of different densities
cites work: The Lattice Point Covering Theorem for Rectangles
cites work: A natural encoding scheme proved probabilistic polynomial complete
description: scientific article; zbMATH DE number 417425