On random reductions from sparse sets to tally sets. (English) Zbl 0780.68044

A set \(S\subseteq\{0,1\}^*\) is called 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.


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


[1] Adleman, L.; Manders, K., Reductions that lie, Proc. 20th Ann. IEEE Conf. on Foundations of Computer Science, 397-410 (1979)
[2] Book, R. V., Tally languages and complexity classes, Inform. and Control, 26, 186-193 (1974) · Zbl 0287.68029
[3] Buhrman, H.; Longpré, L.; Spaan, E., Sparse reduces conjunctively to tally, (Tech. Rept. NU-CCS-92-8 (1992), North-eastern University, College of Computer Science) · Zbl 0830.68042
[4] Chang, R.; Kadin, J.; Rohatgi, P., Connections between the complexity of unique satisfiability and the threshold behavior of randomized reductions, Proc. 6th Ann. IEEE Conf. on Structure in Complexity Theory, 255-266 (1991)
[5] Hartmanis, J., On sparse sets in NP-P, Inform. Process. Lett., 16, 55-60 (1983) · Zbl 0501.68014
[6] Hartmanis, J.; Yesha, Y., Computation times of NP sets of different densities, Theoret. Comput. Sci., 34, 17-32 (1984) · Zbl 0985.68515
[7] Niven, I.; Zuckerman, H. S., An Introduction to the Theory of Numbers (1960), Wiley: Wiley New York · Zbl 0186.36601
[8] Saluja, S., Relativized limitations of the left set technique and closure classes of sparse sets, Tech. Rept. Dept. of Computer Science (1992), Tata Institute of Fundamental Research: Tata Institute of Fundamental Research Bombay, India
[9] Vazirani, U.; Vazirani, V., A natural encoding scheme proved probabilistic polynomial complete, Theoret. Comput. Sci., 24, 291-300 (1983) · Zbl 0525.68025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.