10

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.

xal
  • 429
  • 3
  • 8
  • 2
    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$. – Joshua Grochow Dec 23 '17 at 08:29

0 Answers0