Problemy w NC nie są znane z NC2

Czy istnieją interesujące problemy, które występują w ale nie są znane w N C 2 ? W artykule „taksonomii problemów z szybkim Równoległe algorytmy” Kucharz wspomina, że MIS był znany tylko w N C 5 , ale od tego czasu została sprowadzona do N C 2 . Zastanawiam się, czy są jakieś inne problemy z równoległymi algorytmami głębokości polilogu, w których wydaje się, że utknęliśmy na poprawianiu głębokości.$\mathsf{NC}$$\mathsf{NC^{2}}$$\mathsf{NC^{5}}$$\mathsf{NC^{2}}$

Aby zmniejszyć jeszcze bardziej w dół, czy są jakieś problemy , które nie są znane jako na A C 1 lub D E T ?$\mathsf{NC^{2}}$$\mathsf{AC^{1}}$$\mathsf{DET}$

Disclaimer: Nie jestem ekspertem w szybkich algorytmów równoległych, stąd prawdopodobieństwo, że brakowało mi bardziej niedawne wyniki umieścić problemy Wspominam w niższych poziomach $\mathsf{NC}$ hierarchii nie jest znikome. Jeśli zauważysz, że tak jest, powiedz mi, a ja zaktualizuję odpowiedź.

• Raport Równoległe algorytmy dla wyszukiwania wgłębnego omawia znane równoległe algorytmy dla DFS na różnych typach wykresów. Lista podana na stronach 9-10 wskazuje kilka algorytmów w $\mathsf{NC} \setminus \mathsf{NC}_2$ , takich jak DFS dla płaskich grafów bezkierunkowych lub w $\mathsf{RNC} \setminus \mathsf{RNC}_2$ , jak DFS ogólnych wykresów niekierowanego.

• $\mathsf{NC}_3$

• Obliczenie wszystkich maksymalnych klików na wykresie jest w $\mathsf{NC} \setminus \mathsf{NC}_2$

• $\mathsf{NC}_5$

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