On random reductions from sparse sets to tally sets
FacultiesFakultät für Ingenieurwissenschaften und Informatik
LicenseStandard (Fassung vom 01.10.2008)
We show that every sparse set S can be many-one reduced to an appropriate tally set T by a polynomial-time, randomized reduction (see formal definitions below). Since T is in NP if S is in NP, this result can be used to show that there is a tally set in NP being randomized many-one complete for all sparse sets in NP. This partially answers an open problem posed by Hartmanis and Yesha [Ha].