On random reductions from sparse sets to tally sets (Q685530): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Tally languages and complexity classes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: SPARSE Reduces Conjunctively to TALLY / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On sparse sets in NP-P / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computation times of NP sets of different densities / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Lattice Point Covering Theorem for Rectangles / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A natural encoding scheme proved probabilistic polynomial complete / rank | |||
Normal rank |
Latest revision as of 10:34, 22 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On random reductions from sparse sets to tally sets |
scientific article |
Statements
On random reductions from sparse sets to tally sets (English)
0 references
31 January 1994
0 references
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.
0 references
random reduction
0 references
completeness
0 references
sparse set
0 references
tally set
0 references
NP
0 references
many-one reduction
0 references