Structure and importance of logspace-MOD class. (English) Zbl 0749.68033

Buntrock, Gerhard; Damm, Carsten; Hertrampf, Ulrich; Meinel, Christoph

Math. Syst. Theory 25, No. 3, 223-237 (1992).

Summary: We refine the techniques of R. Beigel, J. Gill and U. Hertramp [Lect. Notes Comput. Sci. 415, 49-57 (1990; Zbl 0729.68023)] who investigated polynomial-time counting classes, in order to make them applicable to the case of logarithmic space. We define the complexity classes \({\mathcal M}{\mathcal O}{\mathcal D}_ k{\mathcal L}\) and demonstrate their significance by proving that all standard problems of linear algebra over the finite rings \(Z/kZ\) are complete for these classes. We then define new complexity classes LogFew and LogFew \({\mathcal N}{\mathcal L}\) and identify them as adequate logspace versions of Few and Few\({\mathcal P}\). We show that LogFew\({\mathcal N}{\mathcal L}\) is contained in \({\mathcal M}{\mathcal O}{\mathcal D}{\mathcal Z}_ k{\mathcal L}\) and that LogFew is contained in \({\mathcal M}{\mathcal O}{\mathcal D}_ k{\mathcal L}\) for all \(k\). Also an upper bound for \({\mathcal L}^{\#{\mathcal L}}\) in terms of computation of integer determinants is given from which we conclude that all logspace classes are contained in \({\mathcal N}{\mathcal C}^ 2\).

MSC:

68Q15

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

Keywords:

counting classes

Citations:

Zbl 0729.68023

References:

[1]	E. W. Allender. The complexity of sparse sets in P. InProc. 1st Structure in Complexity Conference, pp. 1-11. Lecture Notes in Computer Science, Vol. 223. Springer-Verlag, Berlin, 1986. · Zbl 0608.68035
[2]	C. Àlvarez and B. Jenner. A very hard log space counting class. InProc. 5th Conference on Structure in Complexity Theory, pp. 154-168, 1990. · Zbl 0813.68098
[3]	J. L. Balcácar, J. Diaz, and J. Gabarró.Structural Complexity Theory I. Springer-Verlag, New York, 1988.
[4]	R. Beigel, J. Gill, and U. Hertrampf. Counting classes: threshold, parity, mods, and fewness. InProc. 7th STACS, pp. 49-57. Lecture Notes in Computer Science, Vol. 415. Springer-Verlag, Berlin, 1990. · Zbl 0729.68023
[5]	S. J. Berkowitz. On computing the determinant in small parallel time using a small number of processors.Inform. process. Lett., 18:147-150, 1984. · Zbl 0541.68019 · doi:10.1016/0020-0190(84)90018-8
[6]	A. Borodin, S. A. Cook, P. W. Dymond, W. L. Ruzzo, and M. Tompa. Two applications of inductive counting for complementation problems.SIAM J. Comput., 18(3):559-578, 1989. · Zbl 0678.68031 · doi:10.1137/0218038
[7]	A. Borodin, J. von zur Gathen, and J. E. Hopcroft. Fast parallel matrix and gcd computations.Inform. and Control, 52:241-256, 1982. · Zbl 0507.68020 · doi:10.1016/S0019-9958(82)90766-5
[8]	G. Buntrock, L. A. Hemachandra, and D. Siefkes. Using inductive counting to simulate nondeterministic computation. InProc. 15th MFCS, pp. 187-194. Lecture Notes in Computer Science, Vol. 452. Springer-Verlag, Berlin, 1990. (To appear inInform. and Comput.) · Zbl 0747.68015
[9]	Jin-yi Cai and L. A. Hemachandra. On the power of parity polynomial time. InProc. 6th STACS, pp. 229-233. Lecture Notes in Computer Science, Vol. 349. Springer-Verlag, Berlin, 1989.
[10]	S. A. Cook. A taxonomy of problems with fast parallel algorithms.Inform. and Control, 64:2-22, 1985. · Zbl 0575.68045 · doi:10.1016/S0019-9958(85)80041-3
[11]	T. Gundermann, N. A. Nasser, and G. Wechsung. A survey on counting classes. InProc. 5th Conference on Structure in Complexity Theory, pp. 140-153, 1990.
[12]	N. Immerman. Nondeterministic space is closed under complement.SIAM J. Comput., 17(5): 935-938, 1988. · Zbl 0668.68056 · doi:10.1137/0217058
[13]	R. E. Ladner and N. A. Lynch. Relativization of questions about log space computability.Math. Systems Theory, 10:19-32, 1976. · Zbl 0341.68036 · doi:10.1007/BF01683260
[14]	K.-J. Lange and P. Rossmanith. Characterizing unambiguous augmented pushdown automata by circuits. InProc. 15th MFCS, pp. 399-406. Lecture Notes in Computer Science, Vol. 452. Springer-Verlag, Berlin, 1990. · Zbl 0731.68038
[15]	C. Meinel.Modified Branching Programs and Their Computational Power. Lecture Notes in Computer Science, Vol. 370. Springer-Verlag, Berlin, 1989. · Zbl 0669.68042
[16]	K. Mulmuley. A fast parallel algorithm to compute the rank of a matrix over an arbitrary field. InProc. 18th STOC, pp. 338-339, 1986.
[17]	C. H. Papadimitriou and S. K. Zachos. Two remarks on the power of counting. InProc. 6th GI Conference on Theoretical Computer Science, pp. 269-276. Lecture Notes in Computer Science, Vol. 145. Springer-Verlag, Berlin, 1983.
[18]	R. Szelepcsényi. The method of forced enumeration for nondeterministic automata.Acta Inform., 26:279-284, 1988. · Zbl 0638.68046 · doi:10.1007/BF00299636
[19]	J. Torán. Counting the number of solutions. InProc. 15th MFCS, pp. 121-134. Lecture Notes in Computer Science, Vol. 452. Springer-Verlag, Berlin, 1990.
[20]	L. G. Valiant. The relative complexity of checking and evaluating.Inform. Process. Lett., 5:20-23, 1976. · Zbl 0342.68028 · doi:10.1016/0020-0190(76)90097-1
[21]	L. G. Valiant. The complexity of computing the permanent.Theoret. Comput. Sci., 8:189-201, 1979. · Zbl 0415.68008 · doi:10.1016/0304-3975(79)90044-6