P-Kompletność i obliczenia równoległe

23

Niedawno czytałem o algorytmach sprawdzania podobieństwa i czytałem, że problem jest P-zupełny . Co więcej, konsekwencją tego jest to, że ten problem lub jakikolwiek problem P-zupełny prawdopodobnie nie będzie miał wydajnych algorytmów równoległych.

Jaka jest intuicja stojąca za tym ostatnim stwierdzeniem?

complexity-theory parallel-computing

— Dave Clarke
źródło

Odnosi się to do NC (patrz odpowiedzi), który imho jest okropnym sposobem sformalizowania „wydajnie równoległego”.

— Raphael

17

Prawdopodobnie jakikolwiek problem z $P$ kompleksem nie ma wydajnego algorytmu równoległego. Czemu ?

Istnienie $P$ -Complete problemów jest najważniejszą wskazówką, że $(P ∩ POLYLOGSPACE) ≠ P$ . Pytanie brzmi zatem, dlaczego ta hipoteza jest istotna dla obliczeń równoległych? Zacznijmy od zasobów używanych w obliczeniach. W przypadku przetwarzania sekwencyjnego: czas i przestrzeń; dla obliczeń równoległych: czas i sprzęt (liczba procesorów). Czy istnieje związek? Tak! Przestrzeń sekwencyjna ↔ czas równoległy; Czas sekwencyjny ↔ sprzęt równoległy. Zależność między przestrzenią sekwencyjną a czasem równoległym wydaje się być niezależna od przyjętego modelu obliczeń równoległych; prowadzi to do następnej, tak zwanej tezy obliczeń równoległych, która nie jest udowodniona.

(Chandra i Stockmeyer) Każde obliczenie bazy TM o złożoności przestrzennej może być symulowane w równoległym modelu obliczeniowym w czasie i każde obliczenie równoległy model obliczeniowy o złożoności czasowej może być symulowany przez TM o złożoności przestrzennej . $S(n)$ $T(n) = O(S(n)^{O(1)})$ $T’(n)$ $S’(n) = O(T’(n)^{O(1)})$

Klasą problemów możliwych do rozwiązania sekwencyjnie w przestrzeni wielomianowej jest a zestaw problemów możliwych do rozwiązania w czasie wielomianowym to Ponieważ uważa się za znacznie większą klasę problemów niż , teza określa ilościowo efektywną poprawę możliwą dzięki równoległości. Konsekwencją tej tezy jest to, że PRAM może rozwiązać problemy związane z w czasie wielomianowym… Niestety nie! Teza obliczeń równoległych sugeruje, że faktycznie możemy poradzić sobie z problemami należącymi do $PSPACE$ $P$ $PSPACE$ $P$ $NP$ $PSPACE$ … Ale wymaga to wykładniczej liczby procesorów! Działa kompromis czasoprzestrzenny: wykładniczy czas w sekwencyjnym modelu obliczeniowym jest przekształcany w wykładniczą liczbę procesorów w równoległym modelu obliczeniowym, podczas gdy przestrzeń wielomianowa w sekwencyjnym modelu obliczeniowym jest przekształcana w czas wielomianowy równolegle model obliczeniowy.

Ten kompromis jest łatwiejszy do zrozumienia, jeśli staramy się ograniczyć zarówno czas równoległe i równoległe sprzętu: jeśli model obliczeń równoległych posiada szereg wielomian procesory, wtedy klasa problemy rozwiązywalne w równoległym czasie wielomian . Ograniczając liczbę procesorów do wielomianu, możemy poprawić wydajność maszyny sekwencyjnej, ale nie więcej niż czynnik wielomianowy. W ten sposób możemy zmniejszyć stopień wielomianu reprezentującego złożoność czasową, ale nie jesteśmy w stanie wykorzystać równoległości do zmniejszenia kosztów wykładniczych do kosztów wielomianowych. $P$

Problemy rozwiązane równolegle wielomianowej złożoności czasowej są problemy te należące do . Wielomianowe ograniczenie liczby procesorów prowadzi do równoległego modelu obliczeniowego równoważnego TM. Istnieją dwa ważne względy praktyczne: która wielomianowa liczba procesorów jest akceptowalna / niedroga? W praktyce wielomianowa liczba procesorów ma być liniowa lub bliska. Który czas subpolinomialny jest osiągalny? Okazało się, że prawie wszystkie możliwe równolegle możliwe problemy mogą osiągnąć równoległy czas polilogarytmiczny. Równolegle złożoność czasowa, która jest logarytmiczna w długości wejściowej, stanowi wydajne obliczenie równoległe. Algorytm równoległy jest uważany za wydajny, jeśli przy wielomianowej liczbie procesorów jego złożoność czasowa jest polilogarytmiczna. $P$

Biorąc pod uwagę problem gdzie i są stałymi, równoległa teza obliczeniowa implikuje istnienie równoległego algorytmu dla o złożoności czasowej gdzie jest stałą. Porównanie czasu sekwencyjnego i równoległego pozwala na sklasyfikowanie jako problemu wysoce równoległego (z perspektywy czasu). $R \in TIME\_SPACE_{TM}(n^k, (log n)^h)$ $k$ $h$ $R$ $O((log n)^{k’})$ $k’$ $R$

Z tezy o obliczeniach równoległych wynika, że jest klasą problemów wysoce równoległych. nie zawiera kompletnych problemów związanych z redukcją przestrzeni na kłody; oznacza to . Wygląda na to że $POLYLOGSPACE$ $POLYLOGSPACE$ $POLYLOGSPACE \neq P$

$POLYLOGSPACE ⊄ P$
$P ⊄ POLYLOGSPACE$

$P ∩ POLYLOGSPACE$ zawiera problemy, które można rozwiązać w czasie wielomianowym za pomocą przestrzeni polilogarytmicznej. Problemy z prawdopodobnie należą do . $P$ $P - (P ∩ POLYLOGSPACE)$

$NC$ (klasa Nicka - tak zwana na cześć Nicholasa Pippengera, pierwsza w 1979 roku, która ją zidentyfikowała i scharakteryzowała) to klasa problemów, które można rozwiązać w czasie polilogarytmicznym (tj. Ze złożonością czasową z wielomianową liczbą procesorów (tj. ograniczona przez dla niektórych funkcji wielomianu gdzie jest rozmiarem problemu) Teza obliczeń równoległych zakłada . $O((log n)^k))$ $O(f(n))$ $f$ $n$ $NC ⊂ (P ∩ POLYLOGSPACE)$

Niestety, z definicji obejmuje również wiele problemów, których nie można skutecznie zrównoleglać. Najbardziej niesławnym przykładem jest równoległe wyszukiwanie binarne . Problem polega na tym, że ten problem ma złożoność polilogarytmiczną nawet dla = 1. Każdy algorytm sekwencyjny wymagający co najwyżej czasu logarytmicznego w najgorszym przypadku jest w niezależnie od jego równoległej wykonalności! $NC$ $p$ $NC$

Teraz możemy wreszcie wyjaśnić, dlaczego problemy z uzupełnieniem są najtrudniejszymi problemami możliwymi do zrównoleglenia. Biorąc pod uwagę problem ukończony , bardzo mało prawdopodobne jest istnienie wydajnego algorytmu równoległego: jeśli taki równoległy algorytm istniałby ze złożonością czasową , to teza obliczeń równoległych sugeruje istnienie algorytm sekwencyjny o złożoności przestrzennej dla tego samego problemu. Ponieważ jest -Complete Problem ten z kolei oznacza, że każdy problem może być rozwiązany w przestrzeni poli-log: . Jak już wiesz, zamiast tego wierzymy w to $P$ $P$ $Q$ $O((log n)^k)$ $O((log n)^{k’})$ $Q$ $P$ $P$ $(P ∩ POLYLOGSPACE) = P$ $(P ∩ POLYLOGSPACE) ⊂ P$ , chociaż nie jesteśmy jeszcze w stanie tego udowodnić.

Ostatnia uwaga na temat wymagań procesora wielomianowego. To jest teoretyczne stwierdzenie. W praktyce: wymagania procesora, które rosną szybciej niż rozmiar problemu, mogą nie być naprawdę przydatne.

— Massimo Cafaro
źródło

10

Ponieważ „wydajna równoległość” mieści się w („Klasa Nicka” problemów rozstrzygalnych w czasie polilogarytmicznym z wielomianową liczbą procesorów) i powszechnie uważa się, że . Tak więc nie uważa się, że jakikolwiek problem ma wydajny algorytm równoległy (ponieważ oznaczałoby to, że ). $\mathsf{NC}$ $\mathsf{NC} \neq \mathsf{P}$ $\mathsf{P\text{-}complete}$ $\mathsf{P} = \mathsf{NC}$

Oczywiście wszystko to ma na celu przypuszczenie, że , ponieważ wiesz, że jest to otwarty problem, że nie znajduje się na pierwszym poziomie , tzn. nie wiemy, czy . $\mathsf{NC} \neq \mathsf{P}$ $\mathsf{P}$ $\mathsf{NC}$ $\mathsf{NC^1} \neq \mathsf{P}$

Co więcej, nie wiemy nawet, czy nie możesz rozwiązać problemów w w , tj. Obwody boolowskie o stałej głębokości (= stały czas równoległy) z . $\mathsf{P}$ $\mathsf{AC^0[6]}$ $\mod_6$

Aby uzyskać więcej informacji, spójrz na następującą książkę:

Raymond Greenlaw, H. James Hoover, Walter L. Ruzzo, „ Granice obliczeń równoległych: teoria P-kompletności ”, 1995.

— Kaveh
źródło

NC obejmuje również wiele problemów, których nie można skutecznie zrównoleglać. Zobacz moją odpowiedź, aby poznać szczegóły.

— Massimo Cafaro,

Możesz wprost powiedzieć, że „Jeśli jakiś problem z występuje w to ".

P - c o m p l e t e

$\mathsf{P\text{-}complete}$

N C

$\mathsf{NC}$

N C = P

$\mathsf{NC} = \mathsf{P}$

— Alex ten Brink

1

@nieprzekazane, istnieją różne opinie na temat tego, która klasa poprawnie przechwytuje „wydajne algorytmy równoległe”, dlatego użyłem klasy uważanej za górną granicę. Myślę, że P vs. NC jest typowym powodem, dla którego ludzie myślą, że problemy z kompletnością P nie mają wydajnych algorytmów równoległych, chociaż istnieją interesujące szczegóły, jak podano w odpowiedzi. Dodałem odniesienie do mojej odpowiedzi.

— Kaveh

1

@Kaveh, zgadzam się z tobą. Większość ludzi myśli o tym właśnie w tych kategoriach. Dlatego chciałem zaproponować nieco inny punkt widzenia, oparty na tezie obliczeń równoległych. Odniesienia, które podałeś, są doskonałe i stanowią de facto najlepsze podejście do tematu, jaki kiedykolwiek czytałem.

— Massimo Cafaro

6

Odpowiedź Kaveha obejmuje zwykłą definicję „równoległości”, którą jest NC. Pytanie, czy P NC jest jednym z trudniejszych pytań w teorii złożoności (i pod pewnymi względami równie istotnymi jak pytanie P NP). $<$ $<$

Intuicja za tym stoi, że niektóre problemy w P, takie jak programowanie liniowe lub kolejność DFS, wydają się mieć wiele zależności, które wymuszają długą „ścieżkę krytyczną”, której nie można zrównoważyć. Nie jest to dowodem bardziej niż niedeterminizm, który wydaje się być bardzo potężny, ale jest to podstawowa idea.

Edycja: Aby wyjaśnić komentarze, celem tej odpowiedzi jest wyjaśnienie, dlaczego (niektórzy) ludzie nie myślą, że P i NC są takie same. Podobnie jak w przypadku P i NP, nikt nie wie, jak udowodnić, że oba są różne, ale jest coś w twardych problemach, które sprawiają, że (niektórzy) informatycy uważają, że są.

Inną kwestią jest to, że NC to „czas polilogu na wielomianowo wielu procesorach”, który wymaga bardzo dramatycznego przyspieszenia, ale daje wiele procesorów. Dlatego może nie pasować do praktycznego pojęcia równoległości.

W szczególności, jeśli uważasz, że P NP, od razu zaczniesz analizować heurystykę i algorytmy aproksymacyjne dla problemów z NP-zupełnym. Z drugiej strony, nawet jeśli uważasz, że NC jest mniejsze niż P, możesz być w stanie uzyskać nietrywialne przyspieszenia z rodzajów równoległości dostępnych na dzisiejszych komputerach. $<$

— Louis
źródło

Podana intuicja jest nieprawidłowa, fakt, że nie można zamienić określonego algorytmu w wydajny, równoległy, nie oznacza, że problemu nie można rozwiązać w efektywnym czasie równoległym. Można by powiedzieć, że coś podobnego do powiedzenia przede wszystkim nie jest w ponieważ musisz przetestować wiele liczb i wygląda na to, że większość z nich jest niezwiązana, ale to nieprawda, jak wiemy, a pierwotność jest w .

P

$\mathsf{P}$

P

$\mathsf{P}$

— Kaveh

Ale punkt Louisa powinien być postrzegany jako intuicja i nie jest całkowicie błędny. Problemem jest jednak to, że P-kompletność DFS jest bardzo delikatna - potrzebujesz leksykografii DFS, a także w RNC itp.

— Suresh

@Suresh: Tak. Mam na myśli, że nie mam pojęcia, jak to udowodnić. kolejność DFS nie może być symulowana deterministycznie w sposób znacznie lepszy niż po prostu to, ale ludzie nie „czują”, że jest to możliwe bez przypadkowości. (Jeśli to ma znaczenie, moja „religia” polega na tym, że wiele przypadkowości ma pewną moc.)

— Louis

@Kaveh: Ta „ścieżka krytyczna” (zwana również „głębokością roboczą”) nie jest cechą algorytmu, ale problemem; dlatego trudno to pokazać. Jest to najdłuższa sekwencja „ścieżek roboczych”, które są badane kolejno (według dowolnego algorytmu).

— Raphael

@ Rafael, biorąc pod uwagę język, nie ma znanego powodu, dla którego algorytm go rozwiązujący powinien wykonać określoną sekwencję kroków, jeśli można wykazać, że oznaczałoby to dolną granicę, której nie mamy. I to jest jeden z powodów, dla których udowodnienie dolnych granic jest tak trudne, że nie można zakładać niczego o tym, jak będzie wyglądało obliczenie algorytmu rozwiązującego problem. O to mi chodzi.

— Kaveh

3

Należy bardzo uważać na to, kto dokładnie rozumie „wydajne algorytmy równoległe”.

Starsze odpowiedzi wyjaśniają perspektywę teorii złożoności. Tam „efektywny” zwykle oznacza coś niejasnego jak „czas działania w czasie z procesorami ”. Pamiętaj, że liczba procesorów może zależeć od wielkości wejściowej! $O(f(n))$ $O(g(n))$

W szczególności często nazywaną klasą NC jest

zestaw problemów decyzyjnych rozstrzygalnych w czasie polilogarytmicznym na równoległym komputerze z wielomianową liczbą procesorów.

Nie ma to nic wspólnego z tym, czy istnieją równoległe algorytmy dla tych problemów, które są bardziej praktyczne pod względem praktycznym¹:

Jeśli masz algorytm NC, nie otrzymujesz informacji o tym, jak rozwiązać problem (efektywnie) na dowolnym komputerze ze stałą liczbą procesorów.
To, że nie ma algorytmu NC dla problemu, nie oznacza, że nie ma „prawdziwego”; tylko dlatego, że nie możemy rozdzielić problemu na wielomianowo wiele bardzo małych kawałków, nie oznacza, że nie możemy rozbić go na ciągle wiele wystarczająco małych, gdy rośnie. $n$

Na przykład na stale wielu procesorach ze wspólną pamięcią parsowanie CYK może odbywać się równolegle z asymptotycznie optymalnym przyspieszeniem (patrz moja praca magisterska , nawet jeśli parsowanie bezkontekstowe jest P-zakończone).

Opisanie wydajności na maszynach z skończoną liczbą procesorów w przydatny sposób wymaga dokładniejszej analizy niż ponieważ przyspieszenie jest ograniczone stałą skończoną, liczbą procesorów². Rzadko znajduje się to w teorii złożoności. Dlatego jeśli chcesz dowiedzieć się o algorytmach równoległych, które są przydatne w prawdziwym świecie, radziłbym szukać gdzie indziej. $O(\dots)$

Niech funkcja czasu wykonywania algorytmu równoległego. Możesz chcieć nazwać algorytm „wydajnym”, jeśli , lub jeśli dla to funkcja czasu działania dobrego algorytmu sekwencyjnego. Proponuję to bardziej rygorystycznie w mojej pracy magisterskiej , opierając się na cytowanej tam literaturze. $T_p : \mathbb{N} \to \mathbb{R_{\geq 0}}$ $T_1(n)/T_p(n) \approx p$ $T_1(n) \approx T(n)$ $T$
Nie zawsze jest to prawdą; hierarchia pamięci i sprzęt mogą pozwolić na większe przyspieszenie, przynajmniej czasami. Będzie jednak kolejna stała granica.

— Raphael
źródło

0

Załóżmy, że jutro ktoś odkryje dowód, że P = NC. Jakie byłyby konsekwencje badań informatycznych i praktycznych zastosowań w tym przypadku?

To pytanie zostało oznaczone jako duplikat tego pytania, więc załóżmy, że to naprawdę duplikat, i podaj jedną możliwą odpowiedź.

Wiemy, że NC! = PSPACE, stąd dowód, że P = NC również potwierdzi P! = PSPACE. To może nie brzmieć jak wielka sprawa, ale jest to jedna z konsekwencji badań informatycznych.

Dlaczego znamy NC! = PSPACE? Cóż, znamy NC ^k ⊆ DSPACE (O (log ^k )), więc możemy po prostu użyć twierdzenia o hierarchii przestrzeni.

W zakresie praktycznych zastosowań aplikacje wokół programowania liniowego (i wypukłego) mogą być tak kuszące, że niestandardowe architektury równoległe wraz z kompilatorami do efektywnego tłumaczenia formuł programowania liniowego na ten sprzęt mogą być opracowane i sprzedawane.

— Thomas Klimpel
źródło