On the Decomposability of NC and AC
From MaRDI portal
Publication:3034828
DOI10.1137/0219024zbMATH Open0692.68045OpenAlexW2007483355MaRDI QIDQ3034828FDOQ3034828
Authors: Christopher B. Wilson 
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
Recommendations
- On conditional decomposability
- scientific article; zbMATH DE number 3902038
- scientific article; zbMATH DE number 1057354
- scientific article; zbMATH DE number 1071774
- scientific article; zbMATH DE number 3892078
- On an analog of the Peirce decomposition
- scientific article; zbMATH DE number 5323644
- Separation of the monotone NC hierarchy
- On decomposability and interaction functions
- scientific article; zbMATH DE number 2110054
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Cited In (16)
- Reductions to graph isomorphism
- On NC-real complexity classes for additive circuits and their relations with NC
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Relativized logspace and generalized quantifiers over finite ordered structures
- On adaptive DLOGTIME and POLYLOGTIME reductions
- Characterizations of some complexity classes between \(\Theta_2^{\mathrm{P}}\) and \(\Delta_2^{\mathrm{P}}\)
- Reductions to Graph Isomorphism
- Title not available (Why is that?)
- Characterizing parallel hierarchies by reducibilities
- Computing functions with parallel queries to NP
- Equivalence of NC\(^ k\) and AC\(^{k-1}\) closures of NP and other classes
- Relationships among $PL$, $\#L$, and the determinant
- Adaptive logspace reducibility and parallel time
- Circuit depth relative to a random oracle
- Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
- Separating NC along the \(\delta\) axis
This page was built for publication: On the Decomposability of $NC$ and $AC$
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3034828)
