On adaptive DLOGTIME and POLYLOGTIME reductions
From MaRDI portal
DOI10.1016/0304-3975(95)00033-SzbMATH Open0873.68069MaRDI QIDQ672322FDOQ672322
Authors: Carme Àlvarez, Birgit Jenner 
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Recommendations
Cites Work
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- On uniform circuit complexity
- On uniformity within \(NC^ 1\)
- A taxonomy of problems with fast parallel algorithms
- RelativizedNC
- Alternation
- The polynomial-time hierarchy
- Parity, circuits, and the polynomial-time hierarchy
- Bounded Query Classes
- Computing functions with parallel queries to NP
- An Optimal Parallel Algorithm for Formula Evaluation
- A very hard log-space counting class
- On the Tape Complexity of Deterministic Context-Free Languages
- Constant Depth Reducibility
- On adaptive DLOGTIME and POLYLOGTIME reductions
- On the Decomposability of $NC$ and $AC$
- Two Applications of Inductive Counting for Complementation Problems
- Adaptive logspace reducibility and parallel time
- Characterizations of some complexity classes between \(\Theta_2^{\mathrm{P}}\) and \(\Delta_2^{\mathrm{P}}\)
Cited In (8)
This page was built for publication: On adaptive DLOGTIME and POLYLOGTIME reductions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q672322)
