×

On sparse hard sets for counting classes. (English) Zbl 0780.68043

Summary: We study one-word-decreasing self-reducible sets which are introduced by A. Lozano and J. Toran [Math. Syst. Theory 24, No. 2, 83-100 (1991; Zbl 0722.68058)]. These are the usual self-reducible sets with the peculiarity that the self-reducibility machine makes at most one query and this is lexicographically smaller than the input. We show first that for all counting classes defined by a predicate on the number of accepting paths there exist complete sets which are one-word-decreasing self-reducible. Using this fact, we can prove that for any class \(K\) chosen from \(\{PP,NP,C_ =P,MOD_ 2P,Mod_ 3P,...,\}\) it holds that
(1) if there is a sparse \(\leq^ P_{btt}\)-hard set for \(K\) then \(K\subseteq P\) and
(2) if there is a sparse \(\leq^{SN}_{btt}\)-hard set for \(K\) then \(K\subseteq NP\cap co-NP\). This generalizes the result of M. Ogiwara and O. Watanabe [SIAM J. Comput. 20, No. 3, 471-483 (1991; Zbl 0741.68049)] to the mentioned complexity classes.

MSC:

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

References:

[1] Balcázar, J. L., Self-reducibility, (Proc. 4th Symp. on Theoretical Aspects of Computer Science. Proc. 4th Symp. on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 247 (1987), Springer: Springer Berlin), 136-147, J. Comput. System Sci.(to appear) · Zbl 0628.68048
[2] Balcázar, J. L.; Díaz, J.; Gabarró, J., Structural Complexity I, (EATCS Monographs on Theoretical Computer Science, Vol. 11 (1988), Springer: Springer Berlin) · Zbl 0574.68039
[3] Beigel, R.; Hemachandra, L.; Wechsung, G., Probabilistic polynomial time is closed under parity reductions, Inform. Process. Lett., 37, 91-94 (1991) · Zbl 0714.68031
[4] Beigel, R.; Reingold, N.; Spielman, D., PP is closed under intersection, (Proc. 23rd Ann. Symp. on Theory of Computing (1991), ACM: ACM New York), 1-9
[5] Berman, L.; Hartmanis, J., On isomorphism and density of NP and other sets, SIAM J. Comput., 6, 305-322 (1977) · Zbl 0356.68059
[6] Book, R. V.; Ko, K., On sets truth-table reducible to sparse sets, SIAM J. Comput., 17, 903-919 (1988) · Zbl 0665.68040
[7] Cai, J.; Hemachandra, L. A., On the power of parity polynomial time, Math. Systems Theory, 23, 95-106 (1990) · Zbl 0718.68038
[8] Erdös, P.; Rado, R., Intersection theorems for systems of sets, J. London Math. Soc., 35, 85-90 (1960) · Zbl 0103.27901
[9] Fortnow, L.; Reingold, N., PP is closed under truth-table reductions, (Proc. 6th Ann. Conf. on Structure in Complexity Theory (1991), IEEE), 13-15 · Zbl 0851.68029
[10] Fortune, S., A note on sparse complete sets, SIAM J. Comput., 8, 431-433 (1979) · Zbl 0415.68006
[11] Gill, J., Computational complexity of probabilistic Turing machines, SIAM J. Comput., 6, 675-695 (1975) · Zbl 0366.02024
[12] Gundermann, T.; Nasser, N. A.; Wechsung, G., A survey on counting classes, (Proc. 5th Ann. Conf. on Structure in Complexity Theory (1990), IEEE), 140-153
[13] Kadin, J., \(P^{NP[log n]}\) and sparse Turing-complete sets for NP, (Proc. 2nd Ann. Conf. on Structure in Complexity Theory (1987), IEEE), 33-40
[14] Karp, R. M.; Lipton, R. J., Some connections between nonuniform and uniform complexity classes, (Proc. 12th Ann. Symp. on Theory of Computing (1980), ACM: ACM New York), 302-309
[15] Ko, K., Distinguishing bounded reducibilities by sparse sets, (Proc. 3rd Ann. Conf. on Structure in Complexity Theory (1988), IEEE), 181-191
[16] Ko, K., Distinguishing conjunctive and disjunctive reducibilities by sparse sets, Inform. and Comput., 81, 62-87 (1989) · Zbl 0681.68066
[17] Ladner, R. E.; Lynch, N. A.; Selman, A., A comparison of polynomial time reducibilities, Theoret. Comput. Sci., 1, 103-123 (1975) · Zbl 0321.68039
[18] Lautemann, C., BPP and the polynomial hierarchy, Inform. Process. Lett., 17, 215-217 (1983) · Zbl 0515.68042
[19] Long, T. J., On γ-reducibility versus polynomial time reducibility, Theoret. Comput. Sci., 14, 91-101 (1981) · Zbl 0454.68031
[20] Long, T. J., Strong nondeterministic polynomial time reducibilities, Theoret. Comput. Sci., 21, 1-25 (1982) · Zbl 0521.03028
[21] Lozano, A.; Torán, J., Self-reducible sets of small density, Math. Systems Theory, 24, 83-100 (1991) · Zbl 0722.68058
[22] Mahaney, S. R., Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis, J. Comput. System Sci., 25, 130-143 (1982) · Zbl 0493.68043
[23] Ogiwara, M., On sparse bounded truth-table hard sets for PP and NP, Manuscript (1990)
[24] Ogiwara, M.; Watanabe, O., On polynomial-time bounded truth-table reducibility of NP sets to sparse sets, SIAM J. Comput., 20, 471-483 (1991) · Zbl 0741.68049
[25] Papadimitriou, C.; Zachos, S., Two remarks on the power of counting, (Proc. 6th GI Conf. on Theoretical Computer Science. Proc. 6th GI Conf. on Theoretical Computer Science, Lecture Notes in Computer Science, Vol. 145 (1983), Springer: Springer Berlin), 269-276 · Zbl 0506.68039
[26] Russo, D. A., Structural properties of complexity classes, (Ph.D. Dissertation (1985), Department of Mathematics, University of California: Department of Mathematics, University of California Santa Barbara)
[27] Schöning, U., Probabilistic complexity classes and lowness, J. Comput. System Sci., 39, 84-100 (1988) · Zbl 0688.68045
[28] Simon, J., On the difference between one and many, (Proc. 4th Coll. on Automata, Languages and Programming. Proc. 4th Coll. on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 52 (1977), Springer: Springer Berlin), 480-491 · Zbl 0364.68066
[29] Sipser, M., A complexity theoretic approach to randomness, (Proc. 15th Ann. Symp. on Theory of Computing (1983), ACM: ACM New York), 330-335
[30] Stockmeyer, L. J., The polynomial-time hierarchy, Theoret. Comput. Sci., 3, 1-22 (1977) · Zbl 0353.02024
[31] Tarui, J., Randomized polynomials, threshold circuits, and the polynomial hierarchy, (Proc. 8th Ann. Symp. on Theoretical Aspects of Computer Science. Proc. 8th Ann. Symp. on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 480 (1991), Springer: Springer Berlin), 238-250 · Zbl 0764.94026
[32] Toda, S., On the computational power of PP and ⊕ P, (Proc. 30th Symp. on Foundation of Computer Science (1989), IEEE), 514-519
[33] Toda, S.; Ogiwara, M., Counting classes are as hard as the polynomial-time hierarchy, (Proc. 6th Ann. Conf. on Structure in Complexity Theory (1991), IEEE), 2-12
[34] Torán, J., An oracle characterization of the counting hierarchy, (Proc. 3rd Ann. Conf. on Structure in Complexity Theory (1988), IEEE), 213-223
[35] Ukkonen, E., Two results on polynomial time truth-table reductions to sparse sets, SIAM J. Comput., 12, 580-587 (1983) · Zbl 0532.68051
[36] Valiant, L. G., The complexity of computing the permanent, Theoret. Comput. Sci., 8, 189-201 (1979) · Zbl 0415.68008
[37] Wagner, K. W., The complexity of combinatorial problems with succinct input representation, Acta Inform., 23, 325-356 (1986) · Zbl 0621.68032
[38] Watanabe, O., On ⩽\(^P_{1-tt}\) sparseness and nondeterministic complexity classes, (Proc. 15th Internat. Coll. on Automata, Languages and Programming. Proc. 15th Internat. Coll. on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 317 (1988), Springer: Springer Berlin), 697-709 · Zbl 0672.68021
[39] Wrathall, C., Complete-sets and the polynomial-time hierarchy, Theoret. Comput. Sci., 3, 23-33 (1977) · Zbl 0366.02031
[40] Yap, C. K., Some consequences of nonuniform conditions on uniform classes, Theoret. Comput. Sci., 26, 287-300 (1983) · Zbl 0541.68017
[41] Yesha, Y., On certain polynomial-time truth-table reducibilities of complete sets to sparse sets, SIAM J. Comput., 12, 411-425 (1983) · Zbl 0545.03023
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.