×

Generalized theorems on relationships among reducibility notions to certain complexity classes. (English) Zbl 0813.68105

The author shows that if a class is closed under either (I) NP many-one reductions and polynomial-time conjunctive reductions or (II) coNP many- one reductions and polynomial-time disjunctive reductions, then reducibility notions of sets from the class under polynomial-time constant-round truth-table reducibility, polynomial-time log-Turing reducibility, logspace constant-round truth-table reducibility, logspace log-Turing reducibility, and logspace Turing reducibility are all equivalent and the class is also closed under polynomial-time positive Turing reductions.

MSC:

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

Keywords:

reducibility
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. Beigel, R. Chang, and M. Ogiwara, A relationship between difference hierarchies and relativized polynomial hierarchies,Math. Systems Theory 26 (1993), 293–310. Also available as Technical Report TR 91-1184, Department of Computer Science, Cornell University, Ithaca, NY, 1991. · Zbl 0776.68043
[2] R. Beigel, J. Gill, and U. Hertrampf, Counting classes: thresholds, parity, mods, and fewness,Proc. 7th Symp. on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 415, Springer-Verlag, Berlin (1990), pp. 49–57. · Zbl 0729.68023
[3] R. Beigel, L. A. Hemachandra, and G. Wechsung, Probabilistic polynomial time is closed under parity reductions.Inform. Process. Lett. 37 (1991), 91–94. · Zbl 0714.68031
[4] R. Beigel, N. Reingold, and D. Spielman, PP is closed under intersection.Proc. 23rd ACM Symp. on Theory of Computing (1991), pp. 1–9. · Zbl 0827.68040
[5] S. R. Buss and L. Hay, On truth-table reducibility to SAT and the difference hierarchy over NP,Proc. 3rd IEEE Conf. on Structure in Complexity Theory (1988), pp. 224–233.
[6] J. Cai and L. A. Hemachandra, On the power of parity polynomial time,Math. Systems Theory 23 (1990), 95–106. · Zbl 0718.68038
[7] S. A. Cook, The complexity of theorem proving procedures,Proc. 3rd ACM Symp. on Theory of Computing (1971), pp. 151–158. · Zbl 0253.68020
[8] L. Fortnow and N. Reingold, PP is closed under truth-table reductions.Proc. 6th IEEE Conf. on Structure in Complexity Theory (1991), pp. 13–15. · Zbl 0851.68029
[9] J. Gill, Computational complexity of probabilistic Turing machines,SIAM J. Comput. 6 (1975), 675–695. · Zbl 0366.02024
[10] F. Green, On the power of deterministic reductions to C=P,Math. Systems Theory 26 (1993), 215–233. · Zbl 0776.68045
[11] T. Gundermann, N. Nasser, and G. Wechsung, A survey of counting classes,Proc. 5th IEEE Symp. on Structure in Complexity Theory (1990), pp. 140–153.
[12] L. Hemachandra, The strong exponential hierarchy collapses,J. Comput. System Sci. 39 (1989), 299–322. · Zbl 0693.03022
[13] R. Karp, Reducibility among combinatorial problems, in R. E. Miller and J. W. Thatcher (eds.),Complexity of Computer Computations, Plenum, New York (1982), pp. 85–113.
[14] J. Köbler, U. Schöning, and K. W. Wagner, The difference and truth-table hierarchies of NP,Theoret. Inform. Applications (RAIRO) 21 (1987), 419–435. · Zbl 0642.03024
[15] M. Krentel, The complexity of optimization problems,J. Comput. System Sci. 36 (1988), 490–509. · Zbl 0652.68040
[16] R. Ladner and N. Lynch, Relativization of questions about logspace computability,Math. Systems Theory 10 (1976), 19–32. · Zbl 0341.68036
[17] R. Ladner, N. Lynch, and A. Selman, A comparison of polynomial-time reducibilities,Theoret. Comput. Sci. 1 (1975), 103–123. · Zbl 0321.68039
[18] M. Ogiwara, On the computational power of exact counting, Manuscript, April 1990.
[19] M. Ogiwara and L. Hemachandra, A complexity theory for feasible closure properties,Proc. 6th IEEE Symp. on Structure in Complexity Theory (1991), pp. 16–29. · Zbl 0798.68060
[20] C. Papadimitriou and S. Zachos, Two remarks on the power of counting,Proc. 6th GI Conference on Theoretical Computer Science, Lecture Notes in Computer Science, Vol. 145, Springer-Verlag, Berlin (1983), pp. 269–276.
[21] D. A. Russo, Structural properties of complexity classes, Ph.D. dissertation, Department of Mathematics, University of California at Santa Barbara, Santa Barbara, CA, 1985.
[22] A. Selman, Reductions on NP and P-selective sets,Theoret. Comput. Sci. 19 (1982), 287–304. · Zbl 0489.03016
[23] J. Simon, On some central problems in computational complexity, Ph.D. dissertation, Department of Computer Science, Cornell University, Ithaca, NY, 1975.
[24] J. Tarui, Randomized polynomials, threshold circuits, and the polynomial hierarchy,Proc. 8th Symp. on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 480, Springer-Verlag, Berlin (1991), pp. 238–250. · Zbl 0764.94026
[25] S. Toda, On the computational power of PP and ,Proc. 30th IEEE Symp. on Foundation of Computer Science (1989), pp. 514–519.
[26] S. Toda, On polynomial-time truth-table reducibility to C=P sets, Colloquium at the Department of Computer Science, University of Chicago, October 1990.
[27] S. Toda and M. Ogiwara, Counting classes are at least as hard as the polynomial-time hierarchy,SIAM J. Comput. 21 (1992), 316–328. · Zbl 0755.68055
[28] L. G. Valiant, The complexity of computing the permanent,Theoret. Comput. Sci. 8 (1979), 189–201. · Zbl 0415.68008
[29] K. W. Wagner, The complexity of combinatorial problems with succinct input representation,Acta Inform. 23 (1986), 325–356. · Zbl 0621.68032
[30] K. W. Wagner, More complicated questions about maxima and minima, and some closures of NP,Theoret. Comput. Sci. 51 (1987), 53–80. · Zbl 0653.03027
[31] K. W. Wagner, Bounded query computations,Proc. 3rd IEEE Conf. on Structure in Complexity Theory (1988), pp. 224–233.
[32] K. W. Wagner, On restricting the access to an NP oracle,Proc. 16th Conf. on Algorithm and Linear Programming, Lecture Notes in Computer Science, Vol. 317, Springer-Verlag, Berlin (1989), pp. 682–696.
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.