A very hard log-space counting class
type: Item
instance of: scholarly article
title: A very hard log-space counting class
zbMATH Open document ID: 0813.68098
DOI: 10.1016/0304-3975(93)90252-O
author: Carme Àlvarez
author: Birgit Jenner
published in: Theoretical Computer Science
publication date: 1993-05-16T00:00:00Z
review text: 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.
reviewed by: Ulrich Hertrampf
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 166418
zbMATH Keywords: logarithmic space
zbMATH Keywords: log-space counting classes
MaRDI profile type: Publication
cites work: Q4035689
cites work: The polynomial-time hierarchy and sparse oracles
cites work: Q3773366
cites work: Two Applications of Inductive Counting for Complementation Problems
cites work: A taxonomy of problems with fast parallel algorithms
cites work: Q4122837
cites work: Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
cites work: On the complexity of ranking
cites work: Some Results on Tape-Bounded Turing Machines
cites work: Q3862379
cites work: The complexity of ranking simple languages
cites work: Nondeterministic Space is Closed under Complementation
cites work: Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
cites work: Space-bounded reducibility among combinatorial problems
cites work: New problems complete for nondeterministic log space
cites work: On counting and approximation
cites work: The complexity of optimization problems
cites work: Polynomial Space Counting Problems
cites work: Relativization of questions about log space computability
cites work: Q3682474
cites work: On uniform circuit complexity
cites work: Space-bounded hierarchies and probabilistic computations
cites work: The method of forced enumeration for nondeterministic automata
cites work: The complexity of computing the permanent
cites work: The Complexity of Enumeration and Reliability Problems
full work available at URL: 0304-3975(93)90252-o
OpenAlex ID: W1984509356
description: scientific article; zbMATH DE number 166418