×

zbMATH — the first resource for mathematics

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.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Balcázar, J.L., Self-reducibility, (), 136-147, J. Comput. System Sci.(to appear)
[2] Balcázar, J.L.; Díaz, J.; Gabarró, J., Structural complexity I, () · 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, (), 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, (), 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, (), 140-153
[13] Kadin, J., P^{NP[log n]} and sparse Turing-complete sets for NP, (), 33-40
[14] Karp, R.M.; Lipton, R.J., Some connections between nonuniform and uniform complexity classes, (), 302-309
[15] Ko, K., Distinguishing bounded reducibilities by sparse sets, (), 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, (), 269-276
[26] Russo, D.A., Structural properties of complexity classes, ()
[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, (), 480-491
[29] Sipser, M., A complexity theoretic approach to randomness, (), 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, (), 238-250 · Zbl 0764.94026
[32] Toda, S., On the computational power of PP and ⊕ P, (), 514-519
[33] Toda, S.; Ogiwara, M., Counting classes are as hard as the polynomial-time hierarchy, (), 2-12
[34] Torán, J., An oracle characterization of the counting hierarchy, (), 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, (), 697-709
[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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.