Upper bounds for the complexity of sparse and tally descriptions. (English) Zbl 0840.68041

Summary: We investigate the complexity of computing small descriptions for sets in various reduction classes to sparse sets. For example, we show that if a set \(A\) and its complement conjunctively reduce to some sparse set, then they also are conjunctively reducible to a \(P(A\oplus\text{SAT})\)-printable tally set. As a consequence, the class \(\text{IC}[\log,\text{poly}]\) of sets with low instance complexity is contained in the \(EL^\Sigma_1\)-level of the extended low hierarchy. By refining our techniques, we also show that all word-decreasing self-reducible sets in \(\text{IC}[\log,\text{poly}]\) are in \(\text{NP}\cap \text{co-NP}\) and therefore low for NP. We derive similar results for sets in \(R^p_d(\text{SPARSE})\) and \(R^p_{hd}(R^p_c(\text{SPARSE}))\), as well as in some nondeterministic reduction classes to sparse sets.


68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Full Text: DOI


[1] E. Allender and L. Hemachandra. Lower bounds for the low hierarchy.Journal of the ACM, 39(1):234–250, 1992. · Zbl 0799.68081 · doi:10.1145/147508.147546
[2] V. Arvind, Y. Han, L. Hemachandra, J. Köhler, A. Lozano, M. Mundhenk, M. Ogiwara, U. Schöning, R. Silvestri, and T. Thierauf. Reductions to sets of low information content. InComplexity Theory, Current Research, Cambridge University Press, Cambridge, 1993, pp. 1–45. · Zbl 0794.68058
[3] E. Allender, L. Hemachandra, M Ogiwara, and O. Watanabe. Relating equivalence and reducibility to sparse sets.SIAM Journal on Computing, 21(3):529–539, 1992. · Zbl 0761.68039 · doi:10.1137/0221034
[4] V. Arvind, J. Köbler, and M. Mundhenk. On bounded truth-table, conjunctive, and randomized reductions to sparse sets.Proceedings of the 12th Conference on the Foundations of Software Technology & Theoretical Computer Science, Lecture Notes in Computer Science, Vol. 652, Springer-Verlag, Berlin, 1992, pp. 140–151. · Zbl 0919.03034
[5] V. Arvind, J. Köbler, and M. Mundhenk. Lowness and the complexity of sparse and tally descriptions.Proceedings of the Third International Symposium on Algorithm and Computation, Lecture Notes in Computer Science, Vol. 650, Springer-Verlag, Berlin, 1992, pp. 249–258. · Zbl 0925.68214
[6] V. Arvind, J. Köbler, and M. Mundhenk. Hausdorff reductions to sparse sets and to sets of high information content.Proceedings of the 18th Conference on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 711, Springer-Verlag, Berlin, 1993, pp. 232–241. · Zbl 0925.03184
[7] J. Balcázar. Self-reducibility.Journal of Computer and System Sciences, 41:367–388, 1990. · Zbl 0718.68037 · doi:10.1016/0022-0000(90)90025-G
[8] J. Balcázar and R. Book. Sets with small generalized Kolmogorov complexity.Acta Informatica, 23(6):679–688, 1986. · Zbl 0616.68046 · doi:10.1007/BF00264313
[9] J. L. Balcázar, R. Book, and U. Schöning. Sparse sets, lowness and highness.SIAM Journal on Computing, 15:739–747, 1986. · Zbl 0621.68033 · doi:10.1137/0215053
[10] J. L. Balcázar, J. Díaz, and J. Gabarró.Structural Complexity I. EATCS Monographs on Theoretical Computer Science, Springer-Verlag, New York, 1988.
[11] H. Buhrman, L. Longpré, and E. Spaan. SPARSE reduces conjunctively to TALLY.Proceedings of the 8th Structure in Complexity Theory Conference, IEEE Computer Society Press, New York, May 1993, pp. 208–214. · Zbl 0830.68042
[12] R. Gavaldà and O. Watanabe. On the computational complexity of small descriptions.SIAM Journal on Computing, December 1993, to appear. · Zbl 0799.68085
[13] F. Hausdorff.Grundzüge der Mengenlehre. Leipzig, 1914. · JFM 45.0123.01
[14] L. Hemachandra. The strong exponential hierarchy collapses.Journal of Computer and System Sciences, 39:299–322, 1989. · Zbl 0693.03022 · doi:10.1016/0022-0000(89)90025-1
[15] J. Hartmanis and Y. Yesha. Computation times of NP sets of different densities.Theoretical Computer Science, 34:17–32, 1984. · Zbl 0985.68515 · doi:10.1016/0304-3975(84)90111-7
[16] J. Kadin. pNP[log n] and sparse Turing-complete sets for NP.Journal of Computer and System Sciences, 39(3):282–298, 1989. · Zbl 0693.68027 · doi:10.1016/0022-0000(89)90024-X
[17] R. Karp and R. Lipton. Some connections between nonuniform and uniform complexity classes.Proceedings of the 12th ACM Symposium on Theory of Computing, April 1980, pp. 302–309.
[18] K. Ko. On self-reducibility and weakp-selectivity.Journal of Computer and System Sciences, 26:209–221, 1983. · Zbl 0519.68062 · doi:10.1016/0022-0000(83)90013-2
[19] K. Ko. Distinguishing conjunctive and disjunctive reducibilities by sparse sets.Information and Computation, 81(1):62–87, 1989. · Zbl 0681.68066 · doi:10.1016/0890-5401(89)90029-1
[20] J. Köhler. Locating P/poly optimally in the extended low hierarchy.Theoretical Computer Science, 134:263–285, 1994. · Zbl 0834.68032 · doi:10.1016/0304-3975(94)00016-6
[21] K. Ko and U. Schöning. On circuit-size complexity and the low hierarchy in NP.SIAM Journal on Computing, 14:41–51, 1985. · Zbl 0562.68033 · doi:10.1137/0214003
[22] J. Köbler, U. Schöning, and K. W. Wagner. The difference and truth-table hierarchies of NP.Theoretical Informatics and Applications, 21(4):419–435, 1987. · Zbl 0642.03024
[23] R. Ladner, N. Lynch, and A. Selman. A comparison of polynomial time reducibilities.Theoretical Computer Science, 1(2):103–124, 1975. · Zbl 0321.68039 · doi:10.1016/0304-3975(75)90016-X
[24] T. J. Long and M.-J. Sheu. A refinement of the low and high hierarchies.Mathematical Systems Theory, 28(4):299–327, 1995. · Zbl 0849.68038 · doi:10.1007/BF01185399
[25] A. Lozano and J. Torán. Self-reducible sets of small density.Mathematical Systems Theory, 24:83–100, 1991. · Zbl 0722.68058 · doi:10.1007/BF02090392
[26] S. Mahaney. Spase complete sets for NP: solution of a conjecture of Berman and Hartmanis.Journal of Computer and System Sciences, 25(2):130–143, 1982. · Zbl 0493.68043 · doi:10.1016/0022-0000(82)90002-2
[27] A. Meyer, M. Paterson. With What Frequency Are Apparently Intractable Problems Difficult? Technical Report MIT/LCS/TM-126, Laboratory for Computer Science, MIT, Cambridge, MA, 1979.
[28] M. Mundhenk. On self-reducible sets of low information content.Proceedings of 2nd Italian Conference on Algorithms and Complexity, Lecture Notes in Computer Science, Vol. 778, Springer-Verlag, Berlin, 1994, pp. 203–212.
[29] P. Orponen, K. Ko, U. Schöning, and O. Watanabe. Instance complexity.Journal of the ACM, 41:96–121, 1994. · Zbl 0807.68035 · doi:10.1145/174644.174648
[30] M. Ogiwara and A. Lozano. On one query self-reducible sets.Theoretical Computer Science, 112:255–276, 1993. · Zbl 0780.68043 · doi:10.1016/0304-3975(93)90020-T
[31] M. Ogiwara and O. Watanabe. On polynomial-time bounded truth-table reducibility of NP sets to sparse sets.SIAM Journal on Computing, 20(3):471–483, 1991. · Zbl 0741.68049 · doi:10.1137/0220030
[32] S. Saluja. Relativized limitations of the left set technique and closure classes of sparse sets.Proceedings of the 8th Structure in Complexity Theory Conference, IEEE Computer Society Press, New York, May 1993, pp. 215–222.
[33] U. Schöning. A low hierarchy within NP.Journal of Computer and System Sciences, 27:14–28, 1983. · Zbl 0515.68046 · doi:10.1016/0022-0000(83)90027-2
[34] U. Schöning.Complexity and Structure, Lecture Notes in Computer Science, Vol. 211, Springer-Verlag, Berlin, 1985.
[35] S. Tang and R. Book. Reducibilities on tally and sparse sets.Theoretical Informatics and Applications, 25:293–302, 1991. · Zbl 0731.68039
[36] K. W. Wagner. More complicated questions about maxima and minima, and some closures of NP.Theoretical Computer Science, 51:53–80, 1987. · Zbl 0653.03027 · doi:10.1016/0304-3975(87)90049-1
[37] K. W. Wagner. Bounded query classes.SIAM Journal on Computing, 19(5):833–846, 1990. · Zbl 0711.68047 · doi:10.1137/0219058
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.