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

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 N C 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ą N C i ?$\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, P ≠ N P . 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 N C ?$\mathbb{P}$$\mathbb{NC}$

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 M , zważając że TM M " (tj TM, którego ruch głowicy jest niezależna od jego wejściowego x ) można zbudować obwód C n obliczyć M ( x ) gdzie$t(n)$$M$$M'$$x$$C_n$$M(x)$ .$|x| = n$

Szkic dowodu jest wzdłuż linii mający symulacyjny M oraz określenie „obrazów” swojego stanu (czyli pozycji głowy, symbole na głowach) na każdym kroku czasu t I (myślę o obliczeniowej dzienniku). Każdy krok t i można obliczyć na podstawie xi stanu t i - $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 M ( x ) . Korzystając z tego faktu, wraz z ograniczeniem, że język M jest w L , widzimy, że nasz obwód C n jest z definicji jednolity w przestrzeni logicznej , gdzie jednorodność oznacza po prostu, że nasze obwody w naszej rodzinie obwodów { C n } obliczają M $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 n .$M(x)$$n$

Ponownie, z definicji jednorodności wynika, że ​​obwody decydujące o dowolnym języku w muszą mieć rozmiar funkcji ( n ) obliczalny w O ( log n ) . Rodzina obwodów A C 1 ma najwyżej $\sf{L}$$\text{size}(n)$$O(\log n).$$\sf{AC}^1$głębokość ( log n ) .$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 P- kompletny, jeśli L ∈ P i każdy język w P jest redukowany do niego. Dodatkowo, jeśli L jest P -kompletne, wówczas spełnione są następujące warunki$L$$\sf{P}$$L \in \sf{P}$$\sf{P}$$L$$\sf{P}$

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

2. $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 x i bramkę g ∈ C , jaka jest wydajność g na C ( x $C$$x$$g \in C$$g$$C(x)$ ?

Nie wiemy, jak to obliczyć lepiej niż obliczenie wszystkich bramek które występują przed g . 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 t I , ale nie wiemy, jak obliczyć moc bram w kroku to t I i kroku czasu t i + 1 dla oczywistej trudności że bramy na t I + 1 wymaga wyjścia bramek w t I !$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 N P- kompletności Garey & Johnson .$\sf{P}$$\sf{NP}$

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$