NC (złożoność) - NC (complexity)

W teorii złożoności obliczeniowej klasa NC (od „Klasy Nicka”) jest zbiorem problemów decyzyjnych rozstrzyganych w czasie polilogarytmicznym na komputerze równoległym z wielomianową liczbą procesorów. Innymi słowy, problem występuje w NC, jeśli istnieją stałe c i k takie, że można je rozwiązać w czasie O (log ^c  n ) przy użyciu procesorów równoległych O ( n ^k ) . Stephen Cook ukuł nazwę „klasa Nicka” na cześć Nicka Pippengera , który przeprowadził rozległe badania nad obwodami o głębokości polilogarytmicznej i wielkości wielomianu.

Tak jak klasę P można traktować jako problemy wykonalne ( teza Cobhama ), tak NC można traktować jako problemy, które można efektywnie rozwiązać na komputerze równoległym. NC jest podzbiorem P, ponieważ równoległe obliczenia polilogarytmiczne mogą być symulowane przez sekwencyjne obliczenia wielomianowe. Nie wiadomo, czy NC = P , ale większość badaczy podejrzewa, że ​​jest to fałszywe, co oznacza, że ​​prawdopodobnie istnieją pewne problemy, które są „z natury sekwencyjne” i nie można ich znacząco przyspieszyć za pomocą równoległości. Tak jak klasa NP-zupełna może być uważana za „prawdopodobnie niewykonalną”, tak klasa P-zupełna , przy użyciu redukcji NC , może być uważana za „prawdopodobnie niemożliwa do zrównoleglenia” lub „prawdopodobnie z natury sekwencyjna”.

Komputer równoległy w definicji można założyć jako równoległą maszynę o dostępie swobodnym ( PRAM ). Jest to komputer równoległy z centralną pulą pamięci, a każdy procesor może uzyskać dostęp do dowolnego fragmentu pamięci w stałym czasie. Na definicję NC nie ma wpływu wybór sposobu, w jaki PRAM obsługuje jednoczesny dostęp do pojedynczego bitu przez więcej niż jeden procesor. Może to być CRCW, CREW lub EREW. Zobacz PRAM dla opisów tych modeli.

Równoważnie, NC można zdefiniować jako te problemy decyzyjne, które są rozstrzygane przez jednorodny obwód boolowski (który można obliczyć na podstawie długości wejścia, dla NC przypuszczamy, że możemy obliczyć obwód boolowski o rozmiarze n w przestrzeni logarytmicznej w n ) za pomocą polilogarytmicznego głębokość i wielomianową liczbę bramek z maksymalnym rozłożeniem równym 2.

RNC to klasa rozszerzająca NC o dostęp do losowości.

Problemy w NC

Podobnie jak w przypadku P , przez lekkie nadużycie języka można sklasyfikować problemy funkcji i problemy wyszukiwania jako występujące w NC . Wiadomo, że NC zawiera wiele problemów, w tym:

• Dodawanie, mnożenie i dzielenie liczb całkowitych;
• Mnożenie macierzy , wyznacznik, odwrotność , rząd;
• Wielomianowy GCD, poprzez redukcję do algebry liniowej przy użyciu macierzy Sylwestra
• Znalezienie maksymalnego dopasowania.

Często algorytmy dla tych problemów musiały być wymyślone oddzielnie i nie mogły być naiwnie zaadaptowane ze znanych algorytmów – eliminacja Gaussa i algorytm euklidesowy opierają się na operacjach wykonywanych po kolei. Można skontrastować sumator przenoszenia tętnienia z sumatorem przenoszenia z wyprzedzeniem .

Hierarchia NC

NC ⁱ jest klasą problemów decyzyjnych rozwiązywalnych przez jednorodne układy logiczne z wielomianową liczbą bramek co najwyżej dwóch wejść i głębokości O (log ⁱ  n ) lub klasą problemów decyzyjnych rozwiązywalnych w czasie O (log ⁱ  n ) na komputer równoległy z wielomianową liczbą procesorów. Oczywiście mamy

${\ Displaystyle {\ mathsf {NC}} ^ {1} \ podseteq {\ mathsf {NC}} ^ {2} \ podseteq \ cdots \ podseteq {\ mathsf {NC}} ^ {i} \ podseteq \ cdots {\ matematyka {NC}}}$

który tworzy hierarchię NC .

Możemy powiązać klasy NC z klasami przestrzeni L i NL oraz AC .

${\displaystyle {\mathsf {NC}}^{1}\subseteq {\mathsf {L}}\subseteq {\mathsf {NL}}\subseteq {\mathsf {AC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq {\mathsf {P}}.}$

Klasy NC są powiązane z klasami AC, które są definiowane podobnie, ale z bramami o nieograniczonym wachlarzu. Dla każdego ja mamy

${\ Displaystyle {\ mathsf {NC}} ^ {i} \ subseteq {\ mathsf {AC}} ^ {i} \ subseteq {\ mathsf {NC}} ^ {i + 1}.}$

Bezpośrednią konsekwencją tego jest to, że NC = AC . Wiadomo, że oba wtrącenia są ścisłe dla i = 0.

Podobnie mamy, że NC jest równoważne z problemami, które można rozwiązać na przemiennej maszynie Turinga, ograniczonym do co najwyżej dwóch opcji na każdym kroku z przestrzenią O (log n ) i alternatywami. ${\ Displaystyle (\ log n) ^ {O (1)}}$

Otwarty problem: czy NC jest prawidłowe?

Jednym z głównych otwartych pytań w teorii złożoności jest to, czy każde ograniczenie w hierarchii NC jest właściwe. Papadimitriou zaobserwował, że jeśli NC ⁱ = NC ^{i +1} dla niektórych i , to NC ⁱ = NC ^j dla wszystkich j  ≥  i , aw rezultacie NC ⁱ = NC . Ta obserwacja jest znana jako NC – upadek hierarchii, ponieważ nawet pojedyncza równość w łańcuchu powstrzymywania

${\displaystyle {\mathsf {NC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq \cdots}$

oznacza, że ​​cała hierarchia NC „zapada się” do pewnego poziomu i . Tak więc istnieją 2 możliwości:

1. ${\ Displaystyle {\ mathsf {NC}} ^ {1} \ podzbiór \ cdots \ podzbiór {\ mathsf {NC}} ^ {i} \ podzbiór \ cdots \ podzbiór {\ mathsf {NC}} ^ {i + j} \subset \cdots {\mathsf {NC}}}$
2. ${\ Displaystyle {\ mathsf {NC}} ^ {1} \ podzbiór \ cdots \ podzbiór {\ mathsf {NC}} ^ {i} = \ cdots = {\ mathsf {NC}} ^ {i + j} = \ cdots {\mathsf {NC}}}$

Powszechnie uważa się, że (1) tak jest, chociaż nie odkryto jeszcze żadnego dowodu na prawdziwość któregokolwiek ze stwierdzeń.

NC ⁰

Specjalna klasa NC ⁰ działa tylko na stałej długości bitów wejściowych. Jest zatem opisana jako klasa funkcji definiowalnych przez jednorodne obwody logiczne o stałej głębokości i ograniczonym wachlarzu.

Twierdzenie Barringtona

Program rozgałęziający z n zmiennymi o szerokości k i długości m składa się z sekwencji m instrukcji. Każda z instrukcji jest krotką ( i , p , q ), gdzie i jest indeksem zmiennej do sprawdzenia (1 ≤ i ≤ n ), a p i q są funkcjami od {1, 2, ..., k } do {1, 2, ..., k }. Liczby 1, 2, ..., k nazywane są stanami programu rozgałęziającego. Program początkowo startuje w stanie 1, a każda instrukcja ( i , p , q ) zmienia stan z x na p ( x ) lub q ( x ), w zależności od tego, czy i- ta zmienna ma wartość 0 czy 1. Funkcja mapująca dane wejściowe do stanu końcowego programu nazywamy wydajnością programu (dokładniej, wydajność na wejściu to funkcja mapująca dowolny stan początkowy na odpowiadający mu stan końcowy). Program akceptuje zestaw wartości zmiennych, gdy istnieje taki zestaw funkcji , że sekwencja zmiennej jest w A dokładnie wtedy, gdy jej wydajność jest w F . ${\ Displaystyle A \ podzbiór 2 ^ {n}}$${\ Displaystyle F \ podzbiór k ^ {k}}$${\ Displaystyle x \ w 2 ^ {n}}$

Rodzina programów rozgałęziających składa się z programu rozgałęziającego z n zmiennymi na każde n . Akceptuje język, gdy program ze zmienną n akceptuje język ograniczony do długości n wejść.

Łatwo pokazać, że każdy język L na {0,1} może być rozpoznany przez rodzinę programów rozgałęziających o szerokości 5 i wykładniczej długości lub przez rodzinę wykładniczą szerokości i długości liniowej.

Każdy język regularny na {0,1} może być rozpoznany przez rodzinę programów rozgałęziających o stałej szerokości i liniowej liczbie instrukcji (ponieważ DFA można przekonwertować na program rozgałęziający). BWBP oznacza klasę języków rozpoznawalnych przez rodzinę programów rozgałęziających się o ograniczonej szerokości i długości wielomianu.

Twierdzenie Barringtona mówi, że BWBP jest dokładnie niejednorodnym NC ¹ . Dowód wykorzystuje nierozwiązywalność symetrycznej grupy S ₅ .

Twierdzenie jest dość zaskakujące. Na przykład implikuje, że funkcja większości może być obliczona przez rodzinę programów rozgałęziających się o stałej szerokości i rozmiarze wielomianu, podczas gdy intuicja może sugerować, że aby osiągnąć rozmiar wielomianu, potrzebna jest liniowa liczba stanów.

Dowód twierdzenia Barringtona

Program rozgałęziający o stałej szerokości i rozmiarze wielomianu można łatwo przekształcić (poprzez dziel i zwyciężaj) na obwód w NC ¹ .

I odwrotnie, załóżmy, że podany jest obwód w NC ¹ . Bez utraty ogólności załóżmy, że używa tylko bramek AND i NOT.

Rozmiar programu rozgałęzienia wynosi co najwyżej 4 ^d , gdzie d jest głębokością obwodu. Jeśli obwód ma głębokość logarytmiczną, program rozgałęziający ma długość wielomianu.

Uwagi

Bibliografia

• Arora, Sanjeev ; Barak, Boaz (2009). Złożoność obliczeniowa. Nowoczesne podejście . Wydawnictwo Uniwersytetu Cambridge . Numer ISBN 978-0-521-42426-4. Zbl  1193.68112 .
• Clote, Piotrze; Kranakis, Evangelos (2002). Funkcje logiczne i modele obliczeniowe . Teksty w informatyce teoretycznej. Seria EATCS. Berlin: Springer-Verlag . Numer ISBN 3-540-59436-1. Zbl  1016.94046 .
• Greenlaw, Raymond, James Hoover i Walter Ruzzo. Granice obliczeń równoległych; Teoria P-zupełności . ISBN  0-19-508591-4
• Kozen, Dexter C. (1992). Projektowanie i analiza algorytmów . Wykłady 28 - 34 i 36
• Kozen, Dexter C. (2006). Teoria Obliczeń . Teksty w informatyce. Springer-Verlag . Numer ISBN 1-84628-297-7. Zbl  1102.68025 .Wykład 12: Związek NC z klasami czasoprzestrzeni
• Papadimitriou, Christos (1993). „Punkt 15.3: Klasa NC ”. Złożoność obliczeniowa (wyd. 1). Addisona Wesleya. s. 375-381. Numer ISBN 0-201-53082-1.
• Straubinga, Howarda (1994). Automaty skończone, logika formalna i złożoność obwodów . Postęp w informatyce teoretycznej. Bazylea: Birkhäuser. Numer ISBN 3-7643-3719-2. Zbl  0816.68086 .
• Vollmer, Heribert (1998). Wprowadzenie do złożoności obwodów. Jednolite podejście . Teksty w informatyce teoretycznej. Berlin: Springer-Verlag . Numer ISBN 3-540-64310-9. Zbl  0931.68055 .