Gap-definable counting classes. (English) Zbl 0802.68051

Fenner, Stephen A.; Fortnow, Lance J.; Kurtz, Stuart A.

J. Comput. Syst. Sci. 48, No. 1, 116-148 (1994).

Summary: The function class \(\# {\mathbf P}\) lacks an important closure property: it is not closed under subtraction. To remedy this problem, we introduce the function class \(\text{Gap} {\mathbf P}\) as a natural alternative to \(\# {\mathbf P}\). \(\text{Gap} {\mathbf P}\) is the closure of \(\# {\mathbf P}\) under subtraction and has all the other useful closure properties of \(\# {\mathbf P}\) as well. We show that most previously studied counting classes, including \({\mathbf {PP}}\), C\(_ = {\mathbf P}\), and \(\text{Mod}_ k {\mathbf P}\), are “gap-definable,” i.e., definable using the values of \(\text{Gap} {\mathbf P}\) functions alone. We show that there is a smallest gap-definable class, \({\mathbf {SPP}}\), which is still large enough to contain Few. We also show that \({\mathbf S}\)PP consists of exactly those languages low for \(\text{Gap} {\mathbf P}\), and thus \({\mathbf S}\)PP languages are low for any gap-definable class. These results unify and improve erlier disparate results of J. Cai and L. Hemachandra [Math. Syst. Theory 23, No. 2, 95-106 (1990; Zbl 0718.68038)] and J. Köbler et al. [J. Comput. System Sci. 44, No. 2, 272-286 (1992; Zbl 0757.68056)]. We show further that any countable collection of languages is contained in a unique minimum gap-definable class, which implies that the gap-definable classes form a lattice under inclusion. Subtraction seems necessary for this result, since nothing similar is known for the \(\# {\mathbf P}\)-definable classes.

MSC:

68Q15

Complexity classes (hierarchies, relations among complexity classes, etc.)

Keywords:

counting classes; gap-definable class

Citations:

Zbl 0718.68038; Zbl 0757.68056

References:

[1]	Allender, E. W., The complexity of sparse sets in \(P\), (Structure in Complexity Theory. Structure in Complexity Theory, Lecture Notes in Computer Science, Vol. 223 (1986), Springer-Verlag), 1-11 · Zbl 0608.68035
[2]	(Proceedings, 31st Annual IEEE Symposium on Foundations of Computer Science (1990)), 26-34
[3]	Beigel, R., Perceptrons, PP and the polynomial hierarchy, (Proceedings, 7th Annual IEEE Structure in Complexity Theory Conference (1992)), 14-19
[4]	Beigel, R.; Gill, J., Counting classes: Thresholds, parity, mods, and fewness, Theoret. Comput. Sci., 103, 3-23 (1992) · Zbl 0760.68028
[5]	Beigel, R.; Gill, J.; Hertrampf, U., Counting classes: Thresholds, parity, mods, and fewness,, (Proceedings, Seventh Annual Symposium on Theoretical Aspects of Computer Science. Proceedings, Seventh 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.; Reingold, N.; Spielman, D., PP is closed under intersection, (Proceedings, 23rd Annual ACM Symposium on Theory of Computing (1991)), 1-9
[7]	Cai, J.; Hemachandra, L., On the power of parity polynomial time, Math. Systems Theory, 23, No. 2, 95-106 (1990) · Zbl 0718.68038
[8]	Fenner, S.; Fortnow, L.; Li, L., Gap-definability as a closure property, (Proceedings, 10th Annual Symposium on Theoretical Aspects of Computer Science. Proceedings, 10th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 665 (1993), Springer-Verlag: Springer-Verlag New York/Berlin), 484-493 · Zbl 0822.68031
[9]	Gill, J., Computational complexity of probabilistic complexity classes, SIAM J. Comput., 6, 675-695 (1977) · Zbl 0366.02024
[10]	Goldschlager, L. M.; Parberry, I., On the construction of parallel computers from various bases of Boolean functions, Theoret. Comput. Sci., 43, 43-58 (1986) · Zbl 0604.68054
[11]	Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete Mathematics (1989), Addison-Wesley: Addison-Wesley New York/Berlin · Zbl 0668.00003
[12]	Gupta, S., The power of witness reduction, (Proceedings, 6th Annual IEEE Structure in Complexity Theory Conference (1991)), 43-59
[13]	Hopcroft, J.; Ullman, J., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0426.68001
[14]	Köbler, J., Strukturelle Komplexität von Anzahlproblemen, (Ph.D. thesis (1989), Universität Stuttgart: Universität Stuttgart Cambridge, MA), 62
[15]	Köbler, J.; Schöning, U.; Toda, S.; Torán, J., Turing machines with few accepting computations and low sets for PP, J. Comput. System Sci., 44, No. 2, 272-286 (1992) · Zbl 0757.68056
[16]	Köbler, J.; Schöning, U.; Torán, J., On counting and approximation, Acta Inform., 26, 363-379 (1989) · Zbl 0663.03025
[17]	Köbler, J.; Schöning, U.; Torán, J., Graph Isomorphism is low for PP, (Proceedings, Ninth Annual Symposium on Theoretical Aspects of Computer Science. Proceedings, Ninth Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 577 (1992), Springer-Verlag), 401-411 · Zbl 1494.68200
[18]	Li, M.; Vitányi, P. M.B., Applications of Kolmogorov complexity in the theory of computation, (Selman, A. L., Complexity Theory Retrospective (1990), Springer-Verlag: Springer-Verlag New York/Berlin), 147-203, Chap. 6
[19]	Ogiwara, M.; Hemachandra, L. A., A complexity theory of feasible closure properties, (Proceedings, 6th Annual IEEE Structure in Complexity Theory Conference (1991)), 16-29
[20]	Papadimitriou, C. H.; Zachos, S. K., Two Remarks on the Power of Counting, (Lecture Notes in Computer Science, Vol. 145 (1983), Springer-Verlag: Springer-Verlag New York/Berlin), 269-276 · Zbl 0506.68039
[21]	Rogers, H., Theory of Recursive Functions and Effective Computability (1967), McGraw-Hill: McGraw-Hill New York/Berlin, reprinted, MIT Press, Cambridge, MA, 1987 · Zbl 0183.01401
[22]	(Proceedings, 2nd Annual IEEE Structure in Complexity Theory Conference (1987)), 2-8
[23]	Simon, J., On Some Central Problems in Computational Complexity, (Ph.D. thesis (1975), Cornell University: Cornell University New York), available as Cornell Department of Computer Science Technical Report TR75-224
[24]	Soare, R., Recursively Enumerable Sets and Degrees (1987), Springer-Verlag: Springer-Verlag Ithaca, NY · Zbl 0667.03030
[25]	Stockmeyer, L., The polynomial-time hierarchy, Theoret. Comput. Sci., 3, 1-22 (1977) · Zbl 0353.02024
[26]	S. Toda, private communication, 1990.; S. Toda, private communication, 1990.
[27]	Toda, S., PP is as hard as the polynomial-time hierarchy, SIAM J. Comput., 20, No. 5, 865-877 (1991) · Zbl 0733.68034
[28]	Toda, S.; Ogiwara, M., Counting classes are at least as hard as the polynomial-time hierarchy, SIAM J. Comput., 21, No. 2, 316-328 (1992) · Zbl 0755.68055
[29]	Valiant, L., The complexity of computing the permanent, Theoret. Comput. Sci., 5, 189-201 (1979) · Zbl 0415.68008
[30]	Wagner, K., The complexity of combinatorial problems with succinct input representation, Acta Inform., 23, 325-356 (1986) · Zbl 0621.68032