Problemas en NC no conocidos en NC2

¿Hay problemas interesantes que están en pero no se sabe que están en N C 2 ? En el documento 'Una taxonomía de problemas con algoritmos paralelos rápidos', Cook menciona que se sabía que MIS solo estaba en N C 5, pero esto se ha reducido a N C 2 . Me pregunto si hay otros problemas con los algoritmos paralelos de profundidad de polylog donde parece que estamos atascados en mejorar la profundidad.$\mathsf{NC}$$\mathsf{NC^{2}}$$\mathsf{NC^{5}}$$\mathsf{NC^{2}}$

Para reducir aún más, ¿hay algún problema en que no se sabe que está en A C 1 o D E T ?$\mathsf{NC^{2}}$$\mathsf{AC^{1}}$$\mathsf{DET}$

$\mathsf{NC}$

• $\mathsf{NC} \setminus \mathsf{NC}_2$$\mathsf{RNC} \setminus \mathsf{RNC}_2$

• $\mathsf{NC}_3$

• $\mathsf{NC} \setminus \mathsf{NC}_2$

• $\mathsf{NC}_5$

$O(\log^6n)$$O(\log^3n)$