On the Decomposability of NC and AC
From MaRDI portal
Publication:3034828
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
Cited in
(16)- Reductions to graph isomorphism
- On adaptive DLOGTIME and POLYLOGTIME reductions
- Equivalence of NC\(^ k\) and AC\(^{k-1}\) closures of NP and other classes
- Adaptive logspace reducibility and parallel time
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Circuit depth relative to a random oracle
- Characterizing parallel hierarchies by reducibilities
- Reductions to Graph Isomorphism
- Relationships among $PL$, $\#L$, and the determinant
- Computing functions with parallel queries to NP
- scientific article; zbMATH DE number 140491 (Why is no real title available?)
- Separating NC along the \(\delta\) axis
- Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
- Relativized logspace and generalized quantifiers over finite ordered structures
- Characterizations of some complexity classes between \(\Theta_2^{\mathrm{P}}\) and \(\Delta_2^{\mathrm{P}}\)
- On NC-real complexity classes for additive circuits and their relations with NC
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)
