Relationships among PL, \#L, and the determinant
From MaRDI portal
DOI10.1051/ITA/1996300100011zbMATH Open0851.68033OpenAlexW2105859078MaRDI QIDQ4889814FDOQ4889814
Authors: Ogihara, Mitsunori, Eric 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
Recommendations
Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- The complexity of computing the permanent
- Space-bounded hierarchies and probabilistic computations
- On uniformity within \(NC^ 1\)
- A taxonomy of problems with fast parallel algorithms
- RelativizedNC
- Relativization of questions about log space computability
- Complexity classes defined by counting quantifiers
- Title not available (Why is that?)
- On computing the determinant in small parallel time using a small number of processors
- Computational Complexity of Probabilistic Turing Machines
- The complexity of combinatorial problems with succinct input representation
- Structure and importance of logspace-MOD class
- Title not available (Why is that?)
- PP is closed under intersection
- An Optimal Parallel Algorithm for Formula Evaluation
- A comparison of polynomial time reducibilities
- A very hard log-space counting class
- \(\text{RL}\subseteq \text{SC}\)
- #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
- Gap-definable counting classes
- PP is closed under truth-table reductions
- A complexity theory for feasible closure properties
- The power of the middle bit of a \(\#\)P function
- On tape-bounded probabilistic Turing machine acceptors
- On the Decomposability of $NC$ and $AC$
- Title not available (Why is that?)
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- Two Applications of Inductive Counting for Complementation Problems
- Title not available (Why is that?)
- Adaptive logspace reducibility and parallel time
- Deterministic simulation of tape-bounded probabilistic Turing machine transducers
- Title not available (Why is that?)
- A note on the permanent value problem
- Depth reduction for noncommutative arithmetic circuits
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (22)
- The complexity of intersecting finite automata having few final states
- The Orbit Problem Is in the GapL Hierarchy
- Parameterised counting in logspace
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
- The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
- On the complexity of matrix rank and rigidity
- Space-bounded quantum complexity
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- Equivalence problems for circuits over sets of natural numbers
- The orbit problem is in the GapL hierarchy
- Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\)
- Isolation, matching, and counting uniform and nonuniform upper bounds
- On the power of unambiguity in log-space
- Emptiness problems for integer circuits
- Emptiness problems for integer circuits
- Monomials, multilinearity and identity testing in simple read-restricted circuits
- A Logspace Algorithm for Partial 2-Tree Canonization
- The parallel complexity of graph canonization under abelian group action
- On expressive power of regular realizability problems
- Power of counting by nonuniform families of polynomial-size finite automata
- A note on closure properties of logspace MOD classes
- The Space Complexity of k-Tree Isomorphism
This page was built for publication: Relationships among $PL$, $\#L$, and the determinant
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4889814)
