10
$\begingroup$

Do we know of any problems in $\mathsf{NC^{2}}$ that are not known to be in $\mathsf{AC^{1}}$ or $\mathsf{DET}$?

Context: based on Josh's answer to this question, it could be possible that all interesting problems (to humans) lie somewhere in the $\mathsf{NL}$ hierarchy, which collapses due to $\mathsf{NL} = \mathsf{coNL}$, meaning that all of these problems are in $\mathsf{NC}^2$. Yet, I'm not aware of any problems that are in $\mathsf{NC}^2$ but are not contained in a smaller class.

Related to this, are there any useful resources listing problems known to be in $\mathsf{AC}^1$ or $\mathsf{DET}$? The best resource I have found is Cook's paper "A taxonomy of problems with fast parallel algorithms".

Thanks to Josh for suggesting to split this question from here.

$\endgroup$
  • 2
    $\begingroup$ Indeed, Cook '85 (cited in the question) points out that all problems known to be in $\mathsf{NC}^2$ at the time were either in $\mathsf{AC}^1$ or $\mathsf{DET}$. This same statement is re-iterated in Mulmuley-Vazirani-Vazirani '87, and, for me, part of the motivation for this question is whether this situation has changed in the last 30 years. Note that it's possible that $\mathsf{DET} = \mathsf{NC}^2$; the algebraic variant of this would be $\mathsf{VP}_{ws} = \mathsf{VP}$, since we already know $\mathsf{VP} = \mathsf{VNC}^2$. $\endgroup$ – Joshua Grochow Dec 23 '17 at 8:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.