A very hard log-space counting class. (English) Zbl 0813.68098

Àlvarez, Carme; Jenner, Birgit

Theor. Comput. Sci. 107, No. 1, 3-30 (1993).

The authors define three logarithmic space analogs to previously investigated polynomial time function classes, namely \(\#L\), opt-\(L\), and span-\(L\). They give various natural complete problems for all of these classes, thus showing that they should be considered to be natural function classes.
All of these classes are classified by upper and lower bounds: span-\(L\) is contained in \(\#P\), and \(P^{\text{span}-L} = P^{\#P}\); \(FL^{NL}\) is contained in opt-\(L\) and opt-\(L\) is contained in \(NC^ 2\); \(FL\) is contained in \(\#L\), and \(\#L\) is contained is \(NC^ 2\).
Evidence is given that opt-\(L\) is not contained in \(\#L\), because then nondeterministic logarithmic space computations could be made unambiguous, i.e. \(NL = UL\). Further, the authors give strong arguments to believe that neither \(\text{span-}L \subseteq \#L\), nor \(\text{span-}L \subseteq \text{opt-}L\).
This paper (which first appeared as a conference contribution on the 1990 IEEE Structure in Complexity Theory Conference) was a starting point for a lot of investigations concerning (functional) log-space counting classes.

Reviewer: U.Hertrampf (Lübeck)

MSC:

68Q15

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

Keywords:

logarithmic space; log-space counting classes

References:

[1]	Àlvarez, C.; Balcázar, J. L.; Jenner, B., Functional oracle queries as a measure of parallel time, (Proc. 8th STACS. Proc. 8th STACS, Lecture Notes in Computer Science, Vol. 480 (1991), Springer: Springer Berlin), 422-433 · Zbl 0773.68028
[2]	Balcázar, J. L.; Book, R. V.; Schöning, U., The polynomial-time hierarchy and sparse oracles, J. ACM, 33, 603-617 (1986) · Zbl 0625.68033
[3]	Bertoni, A.; Goldwurm, M.; Sabadini, N., Computing the counting function of context-free languages, (Proc. 4th STACS. Proc. 4th STACS, Lecture Notes in Computer Science, Vol. 247 (1987), Springer: Springer Berlin), 169-179 · Zbl 0634.68069
[4]	Borodin, A.; Cook, S. A.; Dymond, P. W.; Ruzzo, W. L.; Tompa, M., Two applications of inductive counting for complementation problems, SIAM J. Comput., 18, 559-578 (1989) · Zbl 0678.68031
[5]	Cook, S. A., A taxonomy of problems with fast parallel algorithms, Inform. and Comput., 64, 2-22 (1985) · Zbl 0575.68045
[6]	C. Damm, manuscript, 1991.; C. Damm, manuscript, 1991.
[7]	Goldberg, A. V.; Sipser, M., Compression and ranking, (Proc. 17th ACM STOC (1985)), 59-68
[8]	Hartmanis, J.; Hunt, H. B., The LBA problem and its importance in the theory of computing, (Karp, R. M., Complexity of Computation. Complexity of Computation, SIAM-AMS Proceedings, Vol. 7 (1974), American Mathematical Society: American Mathematical Society Providence, RI), 1-26 · Zbl 0352.68100
[9]	Hartmanis, J.; Mahaney, S., Languages simultaneously complete for one-way and two-way automata, SIAM J. Comput., 10, 383-390 (1981) · Zbl 0471.68059
[10]	Hemachandra, L.; Rudich, S., On the complexity of ranking, J. Comput. System Sci., 41, 251-271 (1990) · Zbl 0708.68020
[11]	Hopcroft, J.; Ullman, J., Some results on tape-bounded Turing machines, J. ACM, 16, 168-179 (1969) · Zbl 0188.33501
[12]	Hopcroft, J.; Ullman, J., Introduction on Automata Theory, Languages, and Computations (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0426.68001
[13]	Huynh, D. T., The complexity of ranking simple languages, Math. Systems Theory, 23, 1-19 (1990) · Zbl 0692.68059
[14]	Immerman, N., Nondeterministic space is closed under complement, SIAM J. Comput., 17, 935-938 (1988) · Zbl 0668.68056
[15]	Jenner, B.; Kirsig, B., Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata (extended version), RAIRO Inform. Théor. Appl., 23, 87-99 (1989) · Zbl 0665.68038
[16]	Jones, N. D., Space-bounded reducibility among combinatorial problems, J. Comput. System Sci., 11, 68-85 (1975) · Zbl 0317.02039
[17]	Jones, N. D.; Lien, E.; Laaser, W. T., New problems complete for nondeterministic log space, Math. Systems Theory, 10, 1-17 (1976) · Zbl 0341.68035
[18]	Köbler, J., Strukturelle Komplexität von Anzahlproblemen, (Doctoral dissertation (in German) (1989), Universität Stuttgart)
[19]	Köbler, J.; Schöning, U.; Torán, J., On counting and approximation, Acta Inform., 26, 363-379 (1989) · Zbl 0663.03025
[20]	Krentel, M. W., The complexity of optimization problems, J. Comput. System Sci., 36, 490-509 (1988) · Zbl 0652.68040
[21]	Ladner, R., Polynomial space counting problems, SIAM J. Comput., 18, 1087-1097 (1989) · Zbl 0692.68036
[22]	Ladner, R.; Lynch, N., Relativization of questions about log space computability, Math. Systems Theory, 10, 19-32 (1976) · Zbl 0341.68036
[23]	Lange, K. J., Nondeterministic log-space reductions, (Proc. 11th MFCS. Proc. 11th MFCS, Lecture Notes in Computer Science, Vol. 176 (1984), Springer: Springer Berlin), 378-388 · Zbl 0567.03016
[24]	Ruzzo, W., On uniform circuit complexity, J. Comput. System Sci., 22, 365-383 (1981) · Zbl 0462.68013
[25]	Ruzzo, W.; Simon, J.; Tompa, M., Space-bounded hierachies and probabilistic computation, J. Comput. System Sci., 28, 216-230 (1984) · Zbl 0573.68021
[26]	Schöning, U., The power of counting, (Proc. 3rd Structure in Complexity Theory (1988), IEEE), 2-9
[27]	Szelepcsényi, R., The method of forced enumeration for nondeterministic automata, Acta Inform., 26, 279-284 (1988) · Zbl 0638.68046
[28]	Toda, S., On the computational power of PP and ⊕P, (Proc. 30th IEEE FOCS (1989)), 514-519
[29]	Toda, S.; Watanabe, O., On the power of #P functions, manuscript, Theoret. Comput. Sci. (1980), to appear
[30]	Valiant, L. G., The complexity of computing the permanent, Theoret. Comput. Sci., 8, 189-201 (1989) · Zbl 0415.68008
[31]	Valiant, L. G., The complexity of enumeration and reliability problems, SIAM J. Comput., 8, 410-421 (1979) · Zbl 0419.68082
[32]	Vinay, V., Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits, (Proc. 6th Structure in Complexity Theory (1991), IEEE), 270-284