Recommendations
Cites work
- scientific article; zbMATH DE number 3904572 (Why is no real title available?)
- scientific article; zbMATH DE number 4033108 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 176523 (Why is no real title available?)
- scientific article; zbMATH DE number 3548469 (Why is no real title available?)
- A taxonomy of problems with fast parallel algorithms
- Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
- Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
- New problems complete for nondeterministic log space
- Nondeterministic Space is Closed under Complementation
- On counting and approximation
- On the complexity of ranking
- On uniform circuit complexity
- Polynomial Space Counting Problems
- Relativization of questions about log space computability
- Some Results on Tape-Bounded Turing Machines
- Space-bounded hierarchies and probabilistic computations
- Space-bounded reducibility among combinatorial problems
- The Complexity of Enumeration and Reliability Problems
- The complexity of computing the permanent
- The complexity of optimization problems
- The complexity of ranking simple languages
- The method of forced enumeration for nondeterministic automata
- The polynomial-time hierarchy and sparse oracles
- Two Applications of Inductive Counting for Complementation Problems
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
- Model-checking hierarchical structures
- Structure and importance of logspace-MOD class
- Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
- On adaptive DLOGTIME and POLYLOGTIME reductions
- The isomorphism problem for \(k\)-trees is complete for logspace
- Complexity classes of equivalence problems revisited
- Space complexity of the directed reachability problem over surface-embedded graphs
- Nondeterministic NC^1 computation
- Evaluation of circuits over nilpotent and polycyclic groups
- Parallel algorithms for power circuits and the word problem of the Baumslag group
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
- Completeness results for counting problems with easy decision
- scientific article; zbMATH DE number 176518 (Why is no real title available?)
- 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
- On the connection between interval size functions and path counting
- Descriptional and Computational Complexity of Finite Automata
- 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
- Adaptive logspace reducibility and parallel time
- Descriptional and computational complexity of finite automata -- a survey
- A compendium of problems complete for symmetric logarithmic space
- On the power of unambiguity in log-space
- Comparing counting classes for logspace, one-way logspace, and first-order
- 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
- On parallel complexity of analytic functions
- FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS
- Power of counting by nonuniform families of polynomial-size finite automata
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)
