Relationships among $PL$, $\#L$, and the determinant

DOI10.1051/ITA/1996300100011zbMath0851.68033OpenAlexW2105859078MaRDI QIDQ4889814

Ogihara, Mitsunori, Eric W. Allender

Publication date: 10 November 1996

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92523

zbMATH Keywords

reducibilitynondeterministic logspace-bounded machine

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (22)

Monomials, multilinearity and identity testing in simple read-restricted circuits ⋮ 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 ⋮ Emptiness problems for integer circuits ⋮ A Logspace Algorithm for Partial 2-Tree Canonization ⋮ Parameterised counting in logspace ⋮ The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes. ⋮ The orbit problem is in the GapL hierarchy ⋮ The Orbit Problem Is in the GapL Hierarchy ⋮ Isolation, matching, and counting uniform and nonuniform upper bounds ⋮ Space-bounded quantum complexity ⋮ The Space Complexity of k-Tree Isomorphism ⋮ On expressive power of regular realizability problems ⋮ On the complexity of matrix rank and rigidity ⋮ Equivalence problems for circuits over sets of natural numbers ⋮ Power of counting by nonuniform families of polynomial-size finite automata ⋮ Non-commutative arithmetic circuits: depth reduction and size lower bounds ⋮ Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\) ⋮ On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits ⋮ Emptiness Problems for Integer Circuits ⋮ A note on closure properties of logspace MOD classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Space-bounded hierarchies and probabilistic computations
• The complexity of combinatorial problems with succinct input representation
• Deterministic simulation of tape-bounded probabilistic Turing machine transducers
• On tape-bounded probabilistic Turing machine acceptors
• A note on the permanent value problem
• A very hard log-space counting class
• A comparison of polynomial time reducibilities
• Gap-definable counting classes
• \(\text{RL}\subseteq \text{SC}\)
• PP is closed under intersection
• The power of the middle bit of a \(\#\)P function
• PP is closed under truth-table reductions
• A complexity theory for feasible closure properties
• On uniformity within \(NC^ 1\)
• On the Decomposability of $NC$ and $AC$
• A taxonomy of problems with fast parallel algorithms
• Parallel computation for well-endowed rings and space-bounded probabilistic machines
• RelativizedNC
• Two Applications of Inductive Counting for Complementation Problems
• #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
• Structure and importance of logspace-MOD class
• An Optimal Parallel Algorithm for Formula Evaluation
• Relativization of questions about log space computability
• Computational Complexity of Probabilistic Turing Machines
• Complexity classes defined by counting quantifiers
• Adaptive logspace reducibility and parallel time
• Depth reduction for noncommutative arithmetic circuits

This page was built for publication: Relationships among $PL$, $\#L$, and the determinant