On the Decomposability of $NC$ and $AC$
From MaRDI portal
Publication:3034828
DOI10.1137/0219024zbMath0692.68045OpenAlexW2007483355MaRDI QIDQ3034828
Publication date: 1990
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0219024
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items
Uniform constant-depth threshold circuits for division and iterated multiplication., Characterizations of some complexity classes between Θ2p and Δ2p, Adaptive logspace reducibility and parallel time, Relationships among $PL$, $\#L$, and the determinant, Relativized logspace and generalized quantifiers over finite ordered structures, Characterizing parallel hierarchies by reducibilities, On adaptive DLOGTIME and POLYLOGTIME reductions, Computing functions with parallel queries to NP, Circuit depth relative to a random oracle, Reductions to graph isomorphism, Reductions to Graph Isomorphism, Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
