A very hard log-space counting class
From MaRDI portal
Publication:1208403
DOI10.1016/0304-3975(93)90252-OzbMath0813.68098OpenAlexW1984509356MaRDI QIDQ1208403
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
Related Items
Completeness Results for Counting Problems with Easy Decision, NL-printable sets and nondeterministic Kolmogorov complexity, How hard is to compute the edit distance, Completeness, approximability and exponential time results for counting problems with easy decision version, The Isomorphism Problem for k-Trees Is Complete for Logspace, A note on logspace optimization, Evaluating Matrix Circuits, Structure and importance of logspace-MOD class, Rational transductions and complexity of counting problems, On the connection between interval size functions and path counting, Processing succinct matrices and vectors, On the power of unambiguity in log-space, On parallel complexity of analytic functions, On languages accepted with simultaneous complexity bounds and their ranking problem, Rational transductions and complexity of counting problems, Parallel algorithms for power circuits and the word problem of the Baumslag group, The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes., Model-checking hierarchical structures, Adaptive logspace reducibility and parallel time, Recursion-theoretic ranking and compression, Isolation, matching, and counting uniform and nonuniform upper bounds, Relationships among $PL$, $\#L$, and the determinant, On adaptive DLOGTIME and POLYLOGTIME reductions, Unambiguous Boolean grammars, Federation and Navigation in SPARQL 1.1, Evaluation of circuits over nilpotent and polycyclic groups, Parallel Computation Using Active Self-assembly, NL-printable sets and Nondeterministic Kolmogorov Complexity, On the reducibility of sets inside NP to sets with low information content, Descriptional and computational complexity of finite automata -- a survey, The isomorphism problem for \(k\)-trees is complete for logspace, Complexity classes of equivalence problems revisited, Closure and nonclosure properties of the classes of compressible and rankable sets, Descriptional and Computational Complexity of Finite Automata, \textsc{ReachFewL} = \textsc{ReachUL}, Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs, Compressed Decision Problems in Hyperbolic Groups., Non-commutative arithmetic circuits: depth reduction and size lower bounds, Nondeterministic \(NC^1\) computation, Non-cancellative Boolean circuits: A generalization of monotone boolean circuits, On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits, FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS, Identifiability of Graphs with Small Color Classes by the Weisfeiler--Leman Algorithm, Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems, The complexity of computing maximal word functions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- On the complexity of ranking
- Space-bounded hierarchies and probabilistic computations
- The method of forced enumeration for nondeterministic automata
- The complexity of optimization problems
- On counting and approximation
- On uniform circuit complexity
- Space-bounded reducibility among combinatorial problems
- The polynomial-time hierarchy and sparse oracles
- Polynomial Space Counting Problems
- The complexity of ranking simple languages
- A taxonomy of problems with fast parallel algorithms
- Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
- Nondeterministic Space is Closed under Complementation
- Two Applications of Inductive Counting for Complementation Problems
- The Complexity of Enumeration and Reliability Problems
- Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
- New problems complete for nondeterministic log space
- Relativization of questions about log space computability
- Some Results on Tape-Bounded Turing Machines
