On random reductions from sparse sets to tally sets

DOI10.1016/0020-0190(93)90102-FzbMath0780.68044MaRDI QIDQ685530

Uwe Schoening

Publication date: 31 January 1994

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

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)

Related Items (3)

On the power of generalized Mod-classes ⋮ Monotonous and randomized reductions to sparse sets ⋮ Sparse sets and collapse of complexity classes

Cites Work

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

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