Problemy w NC nie są znane z NC2

Czy istnieją interesujące problemy, które występują w ale nie są znane w ? W artykule „taksonomii problemów z szybkim Równoległe algorytmy” Kucharz wspomina, że MIS był znany tylko w , ale od tego czasu została sprowadzona do . 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 lub ? $\mathsf{NC^{2}}$ $\mathsf{AC^{1}}$ $\mathsf{DET}$

complexity-classes dc.parallel-comp

— Xal
źródło

Zobacz to pytanie i odpowiedź Josha.

— Kaveh

Tęskniłem za tym całkowicie Kaveh --- dzięki! Ostatni akapit odpowiedzi na

N L = c o N L

$\mathsf{NL}=\mathsf{coNL}$ a odpowiadającą hierarchii załamania dostarcza użytecznych wyczuciu stanu

N C

$\mathsf{NC}$

— xal

Zastanawiałem się właśnie nad twoim ostatnim pytaniem; Myślę, że warto byłoby opublikować jako osobne pytanie (ponieważ jest to technicznie inne pytanie, niezależne od pytania w twoim tytule). Xal, czy byłbyś otwarty na opublikowanie pytania dotyczącego problemów w

nie wiadomo, że są

{N C}^{2}

$\mathsf{NC}^2$

jako osobne pytanie? I @Kaveh, co sądzisz o tym z perspektywy proceduralnej?

({A C}^{1} \cup D E T)

$(\mathsf{AC}^1 \cup \mathsf{DET})$

— Joshua Grochow,

@Josh, nie widzę w tym żadnego problemu. Poprosiliśmy już autorów o podzielenie pytań na osobne posty.

— Kaveh

Dzięki, że pytasz Josha, podzielę

— Xal

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)$

— Geoffroy Couteau
źródło

Ciekawy! Czy wiesz, czy któryś z nich jest kompletny (lub przypuszcza się, że jest kompletny) dla tych wyższych poziomów hierarchii NC? Byłoby miło mieć takie naturalne przykłady pod ręką.

— Joshua Grochow

Niestety nie mam o tym pojęcia, w artykułach, które wymieniłem powyżej, nie wspomniano nic takiego (o ile widzę). Wszystko to jest bardzo dalekie od mojej specjalizacji; Właśnie przeszukałem literaturę, aby odpowiedzieć na pytanie OP, ponieważ uznałem to za bardzo interesujące, ale moja ograniczona wiedza nie daje mi żadnej jasnej intuicji na temat twardości tych problemów.

— Geoffroy Couteau