Structure and importance of logspace-MOD class
From MaRDI portal
Publication:4009813
DOI10.1007/BF01374526zbMath0749.68033MaRDI QIDQ4009813
Ulrich Hertrampf, Christoph Meinel, Carsten Damm, Gerhard Buntrock
Publication date: 27 September 1992
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Related Items
NL-printable sets and nondeterministic Kolmogorov complexity ⋮ Solving linear equations parameterized by Hamming weight ⋮ The Isomorphism Problem for k-Trees Is Complete for Logspace ⋮ The complexity of intersecting finite automata having few final states ⋮ The parallel complexity of graph canonization under abelian group action ⋮ On the power of unambiguity in log-space ⋮ Unnamed Item ⋮ ABE for circuits with constant-size secret keys and adaptive security ⋮ Separating complexity classes related to bounded alternating ?-branching programs ⋮ On the Descriptive Complexity of Linear Algebra ⋮ Tight space-noise tradeoffs in computing the ergodic measure ⋮ Isolation, matching, and counting uniform and nonuniform upper bounds ⋮ On arithmetic branching programs ⋮ Relationships among $PL$, $\#L$, and the determinant ⋮ On the parameterized complexity of non-monotonic logics ⋮ On the acceptance power of regular languages ⋮ Lower bounds for monotone span programs ⋮ The complexity of circumscriptive inference in Post's lattice ⋮ NL-printable sets and Nondeterministic Kolmogorov Complexity ⋮ On the reducibility of sets inside NP to sets with low information content ⋮ On the complexity of matrix rank and rigidity ⋮ The isomorphism problem for \(k\)-trees is complete for logspace ⋮ Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems ⋮ The complexity of propositional implication ⋮ THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA ⋮ \textsc{ReachFewL} = \textsc{ReachUL} ⋮ Universal algebra and hardness results for constraint satisfaction problems ⋮ Affine systems of equations and counting infinitary logic ⋮ Complexity Theory Basics: NP and NL ⋮ Non-cancellative Boolean circuits: A generalization of monotone boolean circuits ⋮ A note on closure properties of logspace MOD classes ⋮ Identifiability of Graphs with Small Color Classes by the Weisfeiler--Leman Algorithm ⋮ Reachability and recurrence in a modular generalization of annihilating random walks (and Lights-Out games) to hypergraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- On computing the determinant in small parallel time using a small number of processors
- The method of forced enumeration for nondeterministic automata
- Modified branching programs and their computational power
- A very hard log-space counting class
- Relative complexity of checking and evaluating
- A taxonomy of problems with fast parallel algorithms
- Nondeterministic Space is Closed under Complementation
- Two Applications of Inductive Counting for Complementation Problems
- Relativization of questions about log space computability
- Fast parallel matrix and GCD computations
- Counting classes: Thresholds, parity, mods, and fewness
