Structure and importance of logspace-MOD class

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)

zbMATH Keywords

counting classes

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (33)

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Structure and importance of logspace-MOD class