A very hard log-space counting class
From MaRDI portal
Publication:1208403
DOI10.1016/0304-3975(93)90252-OzbMATH Open0813.68098OpenAlexW1984509356MaRDI QIDQ1208403FDOQ1208403
Authors: Carme Àlvarez, Birgit Jenner 
Publication date: 16 May 1993
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(93)90252-o
Recommendations
Cites Work
- The complexity of optimization problems
- Title not available (Why is that?)
- The complexity of computing the permanent
- Space-bounded hierarchies and probabilistic computations
- On uniform circuit complexity
- A taxonomy of problems with fast parallel algorithms
- The Complexity of Enumeration and Reliability Problems
- Relativization of questions about log space computability
- Nondeterministic Space is Closed under Complementation
- Title not available (Why is that?)
- The method of forced enumeration for nondeterministic automata
- New problems complete for nondeterministic log space
- On counting and approximation
- The polynomial-time hierarchy and sparse oracles
- Space-bounded reducibility among combinatorial problems
- Some Results on Tape-Bounded Turing Machines
- Title not available (Why is that?)
- Two Applications of Inductive Counting for Complementation Problems
- Title not available (Why is that?)
- Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
- Polynomial Space Counting Problems
- On the complexity of ranking
- Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
- Title not available (Why is that?)
- The complexity of ranking simple languages
Cited In (49)
- On the reducibility of sets inside NP to sets with low information content
- Unambiguous Boolean grammars
- NL-printable sets and nondeterministic Kolmogorov complexity
- Structure and importance of logspace-MOD class
- Model-checking hierarchical structures
- Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
- On adaptive DLOGTIME and POLYLOGTIME reductions
- Space complexity of the directed reachability problem over surface-embedded graphs
- The isomorphism problem for \(k\)-trees is complete for logspace
- Complexity classes of equivalence problems revisited
- Parallel algorithms for power circuits and the word problem of the Baumslag group
- Nondeterministic \(NC^1\) computation
- Evaluation of circuits over nilpotent and polycyclic groups
- Completeness results for counting problems with easy decision
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
- Title not available (Why is that?)
- Completeness, approximability and exponential time results for counting problems with easy decision version
- Uniform-circuit and logarithmic-space approximations of refined combinatorial optimization problems
- The complexity of computing maximal word functions
- The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
- Closure and nonclosure properties of the classes of compressible and rankable sets
- Descriptional and Computational Complexity of Finite Automata
- On the connection between interval size functions and path counting
- A note on logspace optimization
- \textsc{ReachFewL} = \textsc{ReachUL}
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- The Isomorphism Problem for k-Trees Is Complete for Logspace
- Identifiability of graphs with small color classes by the Weisfeiler-Leman algorithm
- Relationships among $PL$, $\#L$, and the determinant
- A note on SpanP functions
- Isolation, matching, and counting uniform and nonuniform upper bounds
- A compendium of problems complete for symmetric logarithmic space
- Adaptive logspace reducibility and parallel time
- Comparing counting classes for logspace, one-way logspace, and first-order
- Descriptional and computational complexity of finite automata -- a survey
- On the power of unambiguity in log-space
- Compressed Decision Problems in Hyperbolic Groups.
- How hard is to compute the edit distance
- Parallel Computation Using Active Self-assembly
- Rational transductions and complexity of counting problems
- Rational transductions and complexity of counting problems
- On languages accepted with simultaneous complexity bounds and their ranking problem
- NL-printable sets and nondeterministic Kolmogorov complexity
- Federation and navigation in SPARQL 1.1
- Evaluating matrix circuits
- Recursion-theoretic ranking and compression
- Power of counting by nonuniform families of polynomial-size finite automata
- FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS
- On parallel complexity of analytic functions
This page was built for publication: A very hard log-space counting class
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1208403)
