Kilka pytań na temat obliczeń równoległych i klasy NC

14

Mam wiele powiązanych pytań dotyczących tych dwóch tematów.

Po pierwsze, większość tekstów złożoności tylko tuszować klasę . Czy istnieje dobry zasób, który bardziej szczegółowo omawia badania? Na przykład coś, co omawia wszystkie moje pytania poniżej. Ponadto, jestem przy założeniu, że nadal widzi ilość godziwą badań ze względu na jego link do zrównoleglenia, ale mogę się mylić. Sekcja w zoo złożoności niewiele pomaga. $\mathbb{NC}$ $\mathbb{NC}$

Po drugie, obliczenia na półgrupie są w jeśli założymy, że działanie na półgrupach zajmuje stały czas. Ale co, jeśli operacja nie zajmie stałego czasu, jak ma to miejsce w przypadku nieograniczonych liczb całkowitych? Czy są jakieś znane problemy z kompletnością ? $\mathbb{NC}^1$ $\mathbb{NC}^i$

Po trzecie, czy od istnieje algorytm do konwersji dowolnego algorytmu obszaru logów do wersji równoległej? $\mathbb{L} \subseteq \mathbb{NC}^2$

Po czwarte, to brzmi jak większość ludzi zakłada, że w taki sam sposób, . Jaka jest intuicja? $\mathbb{NC} \ne \mathbb{P}$ $\mathbb{P} \ne \mathbb{NP}$

Po piąte, każdy przeczytany tekst wspomina o klasie ale nie zawiera żadnych przykładów problemów, które zawiera. Czy są jakieś? $\mathbb{RNC}$

Wreszcie w odpowiedzi wspomniano o problemach w z równoległym podliniowym czasem wykonania. Jakie są przykłady tych problemów? Czy istnieją inne klasy, które zawierają złożoność algorytmów równoległych, które nie są znane być w ? $\mathbb{P}$ $\mathbb{NC}$

— Mike Izbicki
źródło

1

Zwróć też uwagę na to podobne pytanie.

— Nicholas Mancuso

9

Po trzecie, czy od istnieje algorytm do konwersji dowolnego algorytmu obszaru logów do wersji równoległej? $\sf{L} \subseteq \sf{NC}^2$

Można wykazać (Arora Barak podręcznik), którym podano -czas TM , zważając że TM TM, którego ruch głowicy jest niezależna od jego wejściowego ) można zbudować obwód obliczyć gdzie $t(n)$ $M$ $M'$ $x$ $C_n$ $M(x)$ . $|x| = n$

Szkic dowodu jest wzdłuż linii mający symulacyjny oraz określenie „obrazów” swojego stanu (czyli pozycji głowy, symbole na głowach) na każdym kroku czasu (myślę o obliczeniowej dzienniku). Każdy krok można obliczyć na podstawie stanu $M'$ $M$ $t_i$ $t_i$ $x$ $t_{i-1}$ . Ponieważ każdy migawek obejmuje tylko łańcuch stałej wielkości, a istnieje jedynie stałą ilość łańcuchów tej wielkości, migawkę może być obliczone przez układ o stałej wielkości. $t_i$

Jeśli utworzysz obwody o stałej wielkości dla każdego , mamy obwód, który oblicza . Korzystając z tego faktu, wraz z ograniczeniem, że język jest w , widzimy, że nasz obwód jest z definicji jednolity w przestrzeni logicznej , gdzie jednorodność oznacza po prostu, że nasze obwody w naszej rodzinie obwodów obliczają $t_i$ $M(x)$ $M$ $\sf{L}$ $C_n$ $\{C_n\}$ wszystkie mają ten sam algorytm. Nie jest to specjalnie opracowany algorytm dla każdego obwodu działającego na wielkości wejściowej . $M(x)$ $n$

Ponownie, z definicji jednorodności wynika, że obwody decydujące o dowolnym języku w muszą mieć funkcji obliczalny w Rodzina obwodów ma najwyżej $\sf{L}$ $\text{size}(n)$ $O(\log n).$ $\sf{AC}^1$ głębokość . $O(\log n)$

Wreszcie można wykazać, że daje daną relację. $\sf{AC}^1 \subseteq \sf{NC}^2$

Po czwarte, wygląda na to, że większość ludzi zakłada, że w taki sam sposób jak $\sf{NC} \neq \sf{P}$ . Jaka jest intuicja? $\sf{P} \neq \sf{NP}$

Zanim przejdziemy dalej, zdefiniujmy, co oznacza kompletność $\sf{P}$

Język jest kompletny, jeśli i każdy język w jest redukowany do niego. Dodatkowo, jeśli jest -kompletne, wówczas spełnione są następujące warunki $L$ $\sf{P}$ $L \in \sf{P}$ $\sf{P}$ $L$ $\sf{P}$

$L \in \sf{NC} \iff \sf{P} = \sf{NC}$
$L \in \sf{L} \iff \sf{P} = \sf{L}$

Teraz uważamy będzie klasa języków efektywnie zdecydowały przez komputer równoległy (nasza trasa). Istnieją pewne problemy $\sf{NC}$ które wydają się opierać każdej próbie równoległości (tj. Programowanie liniowe i problem z wartością obwodu). To znaczy, że niektóre problemy wymagają obliczeń, które należy wykonać krok po kroku. $\sf{P}$

Na przykład problem z wartością obwodu określa się jako:

Biorąc pod uwagę obwód , wejście i bramkę , jaka jest wydajność na $C$ $x$ $g \in C$ $g$ $C(x)$ ?

Nie wiemy, jak to obliczyć lepiej niż obliczenie wszystkich bramek które występują przed . Biorąc pod uwagę niektóre z nich mogą być obliczane równolegle, na przykład, jeśli wszystkie one występują w pewnym kroku to , ale nie wiemy, jak obliczyć moc bram w kroku to i kroku czasu dla oczywistej trudności że bramy na wymaga wyjścia bramek w ! $g'$ $g$ $t_i$ $t_i$ $t_{i+1}$ $t_{i+1}$ $t_i$

To intuicji za . $\sf{NC} \neq \sf{P}$

Limits to Parallel Computation to książka o kompletności w podobnej formie, jak książka kompletności Garey & Johnson . $\sf{P}$ $\sf{NP}$

— Nicholas Mancuso
źródło

Dzięki za 2 referencje i częściową odpowiedź. Książka Limits to Parallel Computation radzi sobie lepiej niż inne książki, które oglądałem, ale wciąż jest stosunkowo stara i nie tak dokładna, jak bym chciał.

— Mike Izbicki

3

Po piąte, każdy przeczytany tekst wspomina o klasie RNC, ale nie zawiera żadnych przykładów problemów, które zawiera. Czy są jakieś?

$\mathbb{RNC}^2$

— Mike Izbicki
źródło