Adaptive logspace reducibility and parallel time
From MaRDI portal
Publication:4327383
DOI10.1007/BF01191473zbMath0815.68054MaRDI QIDQ4327383
Carme Àlvarez, José L. Balcázar, Birgit Jenner
Publication date: 5 April 1995
Published in: Mathematical Systems Theory (Search for Journal in Brave)
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Relationships among $PL$, $\#L$, and the determinant, Reductions to Graph Isomorphism, On adaptive DLOGTIME and POLYLOGTIME reductions, Reductions to graph isomorphism, A note on closure properties of logspace MOD classes, A note on logspace optimization, Equivalence problems for circuits over sets of natural numbers
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On uniform circuit complexity
- A very hard log-space counting class
- A comparison of polynomial time reducibilities
- On uniformity within \(NC^ 1\)
- On the Decomposability of $NC$ and $AC$
- Bounded Query Classes
- A taxonomy of problems with fast parallel algorithms
- On similarity and duality of computation (I)
- RelativizedNC
- Two Applications of Inductive Counting for Complementation Problems
- Relativization of questions about log space computability
- On Relating Time and Space to Size and Depth
- Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
