Adaptive logspace reducibility and parallel time
From MaRDI portal
Publication:4327383
DOI10.1007/BF01191473zbMath0815.68054MaRDI QIDQ4327383
Birgit Jenner, Carme Àlvarez, José L. Balcázar
Publication date: 5 April 1995
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (8)
A note on logspace optimization ⋮ Relationships among $PL$, $\#L$, and the determinant ⋮ On adaptive DLOGTIME and POLYLOGTIME reductions ⋮ On expressive power of regular realizability problems ⋮ Equivalence problems for circuits over sets of natural numbers ⋮ Reductions to graph isomorphism ⋮ Reductions to Graph Isomorphism ⋮ A note on closure properties of logspace MOD classes
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$
This page was built for publication: Adaptive logspace reducibility and parallel time
