On random reductions from sparse sets to tally sets

DOI10.1016/0020-0190(93)90102-FMaRDI QIDQ685530zbMATH OpenFDO

Authors Uwe Schöning

Publication date 31 January 1994

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(93)90102-F

zbMATH Keywords

completenessmany-one reductionNPrandom reductionsparse settally set

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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.

Recommendations

• SPARSE Reduces Conjunctively to TALLY
• scientific article; zbMATH DE number 1318517
• CONJUNCTIVE AND DISJUNCTIVE REDUCIBILITIES TO SPARSE AND TALLY SETS REVISITED
• scientific article; zbMATH DE number 4079403
• On the existence of hard sparse sets under weak reductions

Cites work

• A natural encoding scheme proved probabilistic polynomial complete
• Computation times of NP sets of different densities
• On sparse sets in NP-P
• SPARSE Reduces Conjunctively to TALLY
• Tally languages and complexity classes
• The Lattice Point Covering Theorem for Rectangles

Cited in

(5)

• Sparse sets and collapse of complexity classes
• scientific article; zbMATH DE number 4079403 (Why is no real title available?)
• Monotonous and randomized reductions to sparse sets
• SPARSE Reduces Conjunctively to TALLY
• On the power of generalized Mod-classes

This page was built for publication: On random reductions from sparse sets to tally sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685530)