×
Ogiwara, Mitsunori; Hemachandra, Lane A.

A complexity theory for feasible closure properties. (English) Zbl 0798.68060

J. Comput. Syst. Sci. 46, No. 3, 295-325 (1993).
Summary: The study of the complexity of sets encompasses two complementary aims: (1) establishing – usually via explicit construction of algorithms – that sets are feasible, and (2) studying the relative complexity of sets that plausibly might be feasible but are not currently known to be feasible (such as the NP-complete sets and the PSPACE-complete sets). For the study of the complexity of closure properties, a recent flurry of results has established an analog of (1); these papers explicitly demonstrate many closure properties possessed by PP and \(\text{C}_ =\text{P}\) (and the proofs implicitly give closure properties of the function class #P). The present paper presents and develops, just for function classes such as #P, SpanP, OptP, and MidP, and analog of (2): a general theory of the complexity of closure properties. In particular, we show that subtraction is hard for the closure properties of each of these classes: each is closed under subtraction if and only if it is closed under every polynomial-time operation. Previously, no property – natural or unnatural – had been known to have this behavior. We also prove other natural operations hard for the closure properties of #P, SpanP, OptP, and MidP, and we explore the relative complexity of operations that seem not to be #P-hard, such as maximum, minimum, decrement, and median. Moreover, for each of #P, SpanP, OptP, and MidP, we give a natural complete characterization – in terms of the collapse of complexity classes – of the conditions under which that class has every feasible closure property.

Cited in 1 Review
Cited in 39 Documents

MSC:

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

Keywords:

complexity of sets; closure properties; collapse of complexity classes
Cite Review PDF
Full Text: DOI

References:

[1] Adleman, L.; Huang, M., Recognizing primes in random polynomial time, (Proceedings, 19th ACM Symposium on Theory of Computing (1987), Assoc. Comput. Mach: Assoc. Comput. Mach New York), 462-469
[2] Allender, E.; Hemachandra, L., Lower bounds for the low hierarchy, J. Assoc. Comput. Mach., 39, 1, 234-250 (1992) · Zbl 0799.68081
[3] Ambos-Spies, K., Sublattices of the polynomial time degrees, Inform. and Control, 65, 63-84 (1985) · Zbl 0556.03033
[4] Beigel, R., Polynomial interpolation, threshold circuits, and the polynomial hierarchy (December 1989), manuscript
[5] Beigel, R.; Gill, J.; Hertrampf, U., Counting classes: Thresholds, parity, mods, and fewness, (Proceedings, 7th Annual Symposium on Theoretical Aspects of Computer Science. Proceedings, 7th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 415 (1990), Springer-Verlag: Springer-Verlag New York/Berlin), 49-57 · Zbl 0729.68023
[6] Beigel, R.; Hemachandra, L.; Wechsung, G., Probabilistic polynomial time is closed under parity reductions, Inform. Process. Lett., 37, No. 2, 91-94 (1991) · Zbl 0714.68031
[7] Beigel, R.; Reingold, N.; Spielman, D., PP is closed under intersection, (Proceedings, 23rd ACM Symposium on Theory of Computing (1991), Assoc. Comput. Mach: Assoc. Comput. Mach New York), 1-9
[8] Book, R.; Wrathall, C.; Selman, A.; Dobkin, D., Inclusion complete tally languages and the Berman-Hartmanis conjecture, Math. Systems Theory, 11, 1-8 (1977) · Zbl 0365.68044
[9] Cai, J.; Gundermann, T.; Hartmanis, J.; Hemachandra, L.; Sewelson, V.; Wagner, K.; Wechsung, G., The boolean hierarchy II: Applications, SIAM J. Comput., 18, No. 1, 95-111 (1989) · Zbl 0676.68012
[10] Cai, J.; Gundermann, T.; Hartmanis, J.; Hemachandra, L.; Sewelson, V.; Wagner, K.; Wechsung, G., The boolean hierarchy I: Structural properties, SIAM J. Comput., 17, No. 6, 1232-1252 (1988) · Zbl 0676.68011
[11] Cai, J.; Hemachandra, L., On the power of parity polynomial time, Math. Systems Theory, 23, No. 2, 95-106 (1990) · Zbl 0718.68038
[12] Chew, P.; Machtey, M., A note on structure and looking back applied to the complexity of computable functions, J. Comput. System Sci., 22, 53-59 (1981) · Zbl 0474.68063
[13] Cook, S., The complexity of theorem-proving procedures, (Proceedings, 3rd ACM Symposium on Theory of Computing (1971)), 151-158 · Zbl 0253.68020
[14] Fenner, S.; Fortnow, L.; Kurtz, S., Gap-Definable Counting Classes, (Technical Report 90-32 (November 1990), University of Chicago, Department of Computer Science: University of Chicago, Department of Computer Science Chicago, IL) · Zbl 0802.68051
[15] Fenner, S.; Fortnow, L.; Kurtz, S., Gap-definable counting classes, (Proceedings, of the 6th Structure in Complexity Theory Conference (1991), IEEE Comput. Soc: IEEE Comput. Soc Washington, DC), 30-42
[16] Fortnow, L.; Reingold, N., PP is closed under truth-table reductions, (Proceedings, 6th Structure in Complexity Theory Conference (1991), IEEE Comput. Soc: IEEE Comput. Soc Washington, DC), 13-15 · Zbl 0851.68029
[17] Garey, M.; Johnson, D., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[18] Geske, J.; Huynh, D.; Selman, A., A hierarchy theorem for almost everywhere complex sets with application to polynomial complexity degrees, (Proceedings, 4th Annual Symposium on Theoretical Aspects of Computer Science. Proceedings, 4th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 247 (1987), Springer-Verlag: Springer-Verlag New York/Berlin), 125-135 · Zbl 0623.03043
[19] Gill, J., Computational complexity of probabilistic Turing machines, SIAM J. Comput., 6, No. 4, 675-695 (1977) · Zbl 0366.02024
[20] Goldschlager, L.; Parberry, I., On the construction of parallel computers from various bases of boolean functions, Theoret. Comput. Sci., 43, 43-58 (1986) · Zbl 0604.68054
[21] Gundermann, T.; Nasser, N.; Wechsung, G., A survey of counting classes, (Proceedings, 5th Structure in Complexity Theory Conference (1990), IEEE Comput. Soc: IEEE Comput. Soc Washington, DC), 140-153 · Zbl 0825.68390
[22] Gupta, S., The power of witness reduction, (Proceedings, 6th Structure in Complexity Theory Conference (1991), IEEE Comput. Soc: IEEE Comput. Soc Washington, DC), 43-59
[23] Hopcroft, J.; Ullman, J., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0426.68001
[24] Knuth, D., A terminological proposal, SIGACT News, 6, No. 1, 12-18 (1974)
[25] Köbler, J., Strukturelle Komplexität von Anzahlproblemen, (Ph.D. thesis (1989), University of Stuttgart: University of Stuttgart Stuttgart, Germany)
[26] Köbler, J.; Schöning, U.; Toda, S.; Torán, J., Turing machines with few accepting computations and low sets for PP, (Proceedings, 4th Structure in Complexity Theory Conference (1989), IEEE Comput. Soc: IEEE Comput. Soc Washington, DC), 208-215
[27] Köbler, J.; Schöning, U.; Torán, J., On counting and approximation, Acta Inform., 26, 363-379 (1989) · Zbl 0663.03025
[28] Krentel, M., The complexity of optimization problems, J. Comput. System Sci., 36, 490-509 (1988) · Zbl 0652.68040
[29] Ladner, R., On the structure of polynomial time reducibility, Assoc. Comput. Mach., 22, No. 1, 155-171 (1975) · Zbl 0322.68028
[30] Ladner, R.; Lynch, N.; Selman, A., A comparison of polynomial time reducibilities, Theoret. Comput. Sci., 1, No. 2, 103-124 (1975) · Zbl 0321.68039
[31] Landweber, L.; Lipton, R.; Robertson, E., On the structure of sets in NP and other complexity classes, Theoret. Comput. Sci., 15, 181-200 (1981) · Zbl 0482.68042
[32] Levin, L., Universal sorting problems, Probl. Inform. Transmiss., 9, 265-266 (1973)
[33] Ogiwara, M., On the computational power of exact counting (April 1990), manuscript
[34] Ogiwara, M., Characterizing Low Levels of the Polynomial-Time Hierarchy Relative to \(C_=P\) via Metric Turing Machines, (Technical Report C-101 (February 1991), Department of Information Sciences, Tokyo Institute of Technology: Department of Information Sciences, Tokyo Institute of Technology Tokyo, Japan)
[35] Ogiwara, M.; Hemachandra, L., A Complexity Theory for Closure Properties, (Technical Report C-99 (October 1990), Tokyo Institute of Technology, Department of Information Sciences: Tokyo Institute of Technology, Department of Information Sciences Tokyo, Japan) · Zbl 0798.68060
[36] Papadimitriou, C.; Zachos, S., Two remarks on the power of counting, (Proceedings, 6th GI Conference on Theoretical Computer Science. Proceedings, 6th GI Conference on Theoretical Computer Science, Lecture Notes in Computer Science, Vol. 145 (1983)), 269-276, New York/Berlin · Zbl 0506.68039
[37] Rackoff, C., Relativized questions involving probabilistic algorithms, J. Assoc. Comput. Mach., 29, No. 1, 261-268 (1982) · Zbl 0477.68037
[38] Regan, K., Enumeration problems (1982), manuscript
[39] Russo, D., Structural Properties of Complexity Classes, (Ph.D. thesis (1985), University of California at Santa Barbara: University of California at Santa Barbara Santa Barbara, CA)
[40] Sahni, S., Computationally related problems, SIAM J. Comput., 3, No. 4, 262-279 (1974) · Zbl 0272.68040
[41] Sahni, S.; Gonzalez, T., P-complete approximation problems, J. Assoc. Comput. Mach., 23, No. 3, 555-565 (1976) · Zbl 0348.90152
[42] Schöning, U., A low and a high hierarchy in NP, J. Comput. System Sci., 27, 14-28 (1983) · Zbl 0515.68046
[43] Schöning, U., Probabilistic complexity classes and lowness, (Proceedings, 2nd Structure in Complexity Theory Conference (1987), IEEE Comput. Soc: IEEE Comput. Soc Washington, DC), 2-8
[44] Schöning, U., The power of counting, (Selman, A., Complexity Theory Retrospective (1990), Springer-Verlag: Springer-Verlag New/Berlin), 204-233
[45] Simon, J., On Some Central Problems in Computational Complexity, (Ph.D. thesis. Ph.D. thesis, Cornell Department of Computer Science Technical Report TR75-224 (January 1975), Cornell University: Cornell University Ithaca, NY)
[46] Stockmeyer, L., The polynomial-time hierarchy, Theoret. Comput. Sci., 3, 1-22 (1977) · Zbl 0353.02024
[47] Toda, S., On the computational power of PP and ⊕P, (Proceedings, 30th IEEE Symposium on Foundations of Computer Science (1989), IEEE Comput. Soc: IEEE Comput. Soc Washington, DC), 514-519
[48] Toda, S., The complexity of finding medians, (Proceedings, 31st IEEE Symposium on Foundations of Computer Science (1990), IEEE Comput. Soc: IEEE Comput. Soc Washington, DC), 778-787 · Zbl 0825.68599
[49] Toda, S., On Polynomial-Time Truth-Table Reducibility to \(C_=P\) Sets (October 26, 1990), Seminar, University of Chicago
[50] Toda, S.; Ogiwara, M., Counting classes are at least as hard as the polynomial-time hierarchy, (Proceedings, 6th Structure in Complexity Theory Conference (1991), IEEE Comput. Soc: IEEE Comput. Soc Washington, DC), 2-12
[51] Torán, J., An oracle characterization of the counting hierarchy, (Proceedings, 3rd Structure in Complexity Theory Conference (1988), IEEE Comput. Soc: IEEE Comput. Soc Washington, DC), 213-223
[52] Torán, J., Structural Properties of the Counting Hierarchies, (Ph.D. thesis (1988), Universitat Politècnica de Catalunya: Universitat Politècnica de Catalunya Barcelona, Spain)
[53] Valiant, L., The relative complexity of checking and evaluating, Inform. Process. Lett., 5, 20-23 (1976) · Zbl 0342.68028
[54] Valiant, L., The complexity of enumeration and reliability problems, SIAM J. Comput., 8, No. 3, 410-421 (1979) · Zbl 0419.68082
[55] Wagner, K., The complexity of combinatorial problems with succint input representations, Acta Inform., 23, 325-356 (1986) · Zbl 0621.68032
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.