11
$\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.

Improve this question
$\endgroup$
1
  • 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
    Commented Dec 23, 2017 at 8:29

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.