Relationships among $PL$, $\#L$, and the determinant
From MaRDI portal
Publication:4889814
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
Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
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, 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
