NC (złożoność)

W teorii złożoności jedną z dziedzin informatyki teoretycznej , NC (dla klasy Nicka ) jest klasa złożoności obejmująca równoległość . Jest to zbiór problemów decyzyjnych rozstrzyganych w czasie polilogarytmicznym przez wielomianową liczbę maszyn równolegle. Odpowiada problemom uważanym za łatwe do rozwiązania przez architekturę równoległą. Klasa została nazwana przez Stephena Cooka na cześć Nicka Pippengera (z wewnątrz ) , który pracował nad tym tematem.

Na przykład (problem decyzyjny związany z obliczeniem) iloczynu macierzy jest w NC .

Definicja

Problem A występuje w NC, jeśli istnieją dwie stałe c i k takie, że możliwe jest rozwiązanie A w jednym czasie przy użyciu równoległych procesorów. Bardziej precyzyjną definicję możemy podać dzięki obwodom boolowskim . Chodzi o to, że dwie bramki logiczne mogą równolegle obliczać swoje wyjście. Zatem liczba bramek logicznych to - z grubsza mówiąc - liczba procesorów. Głębokość obwodu reprezentuje czas wykonania. Dokładniej, dla wszystkiego najpierw definiujemy klasę NC c jako zbiór języków wyznaczonych przez rodzinę obwodów (gdzie jest rozmiar wejścia) zwanych uniformami (to znaczy, że możemy faktycznie obliczyć z integer ) wielomianu wielkości i głębokości . Jest wtedy klasa NC . $O (\ log ^ {c} (n))$ $O (n ^ {k})$ $vs$ ${\ Displaystyle ({\ mathcal {C}} _ {n}) _ {n \ in \ mathbb {N}}}$ $nie$ ${\ mathcal {C}} _ {n}$ $nie$ $nie$ $O (\ log ^ {c} (n))$ $\ cup _ {{c \ geq 1}} NC ^ {c}$

Te dwie definicje są równoważne.

Przykłady problemów w NC

W NC znajdują się problemy decyzyjne związane z następującymi problemami obliczeniowymi:

dodanie dwóch liczb całkowitych (dokładniej w AC 0 ), pomnożenie dwóch liczb całkowitych w NC 1, ale nie w AC 0 ;
dodanie dwóch macierzy, pomnożenie dwóch macierzy;
obliczyć maksymalne sprzężenie na wykresie ;
N- bitowa funkcja parzystości znajduje się w NC 1 : konstruujemy, dzielimy i podbijamy drzewo binarne z bramką XOR, które można przepisać za pomocą bramek NOT, AND i OR, uzyskując w ten sposób obwód o wysokości O (log n ). Funkcja parzystości nie występuje w AC 0 .
W 1987 roku Buss wykazał, że ocena wzoru (jest to szczególny przypadek problemu obliczania obwodu boolowskiego , ponieważ formuła boolowska jest obwodem boolowskim, który jest drzewem) jest zakończona dla klasy ALOGTIME z redukcjami czasu logarytmicznego (te klasy w czasie logarytmicznym są definiowane na maszynach Turing RAM). ALOGTIME jest równy NC 1 z pewnym warunkiem jednorodności.

Relacje z innymi klasami

Znane są następujące relacje, które wprowadzają do gry klasy L , NL i P :

{\ Displaystyle \ mathbf {NC} ^ {1} \ subseteq \ mathbf {L} \ subseteq \ mathbf {NL} \ subseteq \ mathbf {AC} ^ {1} \ subseteq \ mathbf {NC} ^ {2} \ subseteq \ mathbf {NC} \ subseteq \ mathbf {P}.}

Możemy również zdefiniować klasy AC i AC klas I w sposób analogiczny do NC i NC i oprócz tego, że arity z bramek logicznych jest nieograniczona. W rzeczywistości, tak jak dla wszystkich i , mamy: AC = NC. ${\ Displaystyle \ mathbf {NC} ^ {i} \ subseteq \ mathbf {AC} ^ {i} \ subseteq \ mathbf {NC} ^ {i + 1}}$

Ruzzo wykazał, że NC jest dokładnie tą klasą problemów decyzyjnych, o których decyduje naprzemienna maszyna Turinga w przestrzeni log n z pewną liczbą zmian (log n ) O (1) , to znaczy NC = STA (log n , *, ( log n ) O (1) ) gdzie STA (s ( n ), t ( n ), a ( n )) to klasa problemów decyzyjnych rozstrzyganych przez naprzemienną maszynę Turinga w przestrzeni s ( n ), czas t ( n ) i przemian a ( n ).

Nie wiemy, czy NC jest równe P, czy nie. Jak określają Arora i Barak, nie wiemy, jak oddzielić NC 1 od hierarchii wielomianów PH .

Otwarty problem upadku

Ważnym pytaniem w teorii złożoności jest to, czy inkluzje w hierarchii NC są ścisłe, czy nie. Papadimitriou zauważył, że jeśli NC i = NC i +1 dla jakiegoś i , to NC i = NC j dla wszystkich j ≥ i , a zatem NC i = NC . Ta obserwacja nazywana jest załamaniem hierarchii NC, ponieważ tylko jedna równość w łańcuchu inkluzji ${\ Displaystyle {\ textbf {NC}} ^ {1} \ subseteq {\ textbf {NC}} ^ {2} \ subseteq \ cdots}$

{\ Displaystyle {\ textbf {NC}} ^ {1} \ subseteq {\ textbf {NC}} ^ {2} \ subseteq \ cdots}

oznacza, że cała hierarchia NC załamuje się na poziomie i . Są więc dwie możliwości:

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

Naukowcy myślą że w zasadzie inkluzje są ścisłe (1), ale nie ma dowodów.

Twierdzenie Barringtona

Barrington wykazał, że niejednorodna klasa NC odpowiada problemom rozstrzygniętym przez powiązane programy zdefiniowane w następujący sposób.

Link zewnętrzny

(en) Klasa NC w Complexity Zoo

Uwagi i odniesienia

(w) „ W stronę teorii złożoności synchronicznych obliczeń równoległych. » , Edukacja matematyczna , t. 27,Dziewiętnaście osiemdziesiąt jeden( czytaj online )
(w) Stephen A. Cook , " A taksonomia problemów z szybkimi algorytmami równoległymi " , Information and Control , Vol. 64, n o 1,1 st styczeń 1985, s. 2–22 ( ISSN 0019-9958 , DOI 10.1016 / S0019-9958 (85) 80041-3 , czytaj online )
(w) Nicholas Pippenger , „ jest jednoczesnym ograniczeniem zasobów ” , 20. doroczne sympozjum na temat podstaw informatyki (SFCs 1979) ,1979, s. 307-311 ( ISSN 0272-5428 , DOI 10,1109 / SFCS.1979.29 , czytać online )
(en) Sanjeev Arora i Boaz Barak , Złożoność obliczeniowa: nowoczesne podejście , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) 6.7.1.
(w) „ Kurs - Czytanie 2: Złożoność niektórych problemów ” [PDF] .
Samuel R. Buss , „ The Boolean formula value problem is in ALOGTIME ” , na www.math.ucsd.edu ,Styczeń 1987(dostęp 5 maja 2017 )
(w) „ Complexity Zoo: N - Complexity Zoo ” , na complexityzoo.uwaterloo.ca (dostęp: 29 października 2018 )
(in) „ Boolean Functions and Computation Models - Springer ” na link.springer.com (dostęp 9 czerwca 2016 ) .
(w) Walter L. Ruzzo , „ Jedna jednolita złożoność systemu ” , Journal of Computer and System Sciences , vol. 22 N O 3,1 st czerwiec 1981, s. 365–383 ( DOI 10.1016 / 0022-0000 (81) 90038-6 , czytaj online , dostęp: 30 października 2017 ).
(w) Dexter C. Kozen , Theory of Computation , Springer Publishing Company, Incorporated,2010( ISBN 1849965714 i 9781849965712 , czytaj online ).