On adaptive DLOGTIME and POLYLOGTIME reductions
From MaRDI portal
Recommendations
Cites work
- A taxonomy of problems with fast parallel algorithms
- A very hard log-space counting class
- Adaptive logspace reducibility and parallel time
- Alternation
- An Optimal Parallel Algorithm for Formula Evaluation
- Bounded Query Classes
- Characterizations of some complexity classes between \(\Theta_2^{\mathrm{P}}\) and \(\Delta_2^{\mathrm{P}}\)
- Computing functions with parallel queries to NP
- Constant Depth Reducibility
- On adaptive DLOGTIME and POLYLOGTIME reductions
- On the Decomposability of $NC$ and $AC$
- On the Tape Complexity of Deterministic Context-Free Languages
- On uniform circuit complexity
- On uniformity within \(NC^ 1\)
- Parity, circuits, and the polynomial-time hierarchy
- RelativizedNC
- The polynomial-time hierarchy
- Two Applications of Inductive Counting for Complementation Problems
- \(\Sigma_ 1^ 1\)-formulae on finite structures
Cited in
(8)- On stalling in LogP
- On adaptive DLOGTIME and POLYLOGTIME reductions
- scientific article; zbMATH DE number 6538681 (Why is no real title available?)
- Machines, Computations, and Universality
- Characterizing parallel hierarchies by reducibilities
- Rudimentary reductions revisited
- Adaptive logspace reducibility and parallel time
- STACS 2005
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)
