Złożoność obliczeniowa/Wykład 11: Obliczenia równoległe

Wstęp

W miarę jak technologia zbliża się do wynikających z podstawowych praw fizyki ograniczeń na szybkość obliczeń, wydaje się, że jednym z obiecujących kierunków badań są obliczenia równoległe. W istocie ta idea jest w stanie przynieść nowe możliwości, chociaż należy przyznać, że początkowa fascynacja algorytmami równoległymi nieco zmalała. Tym niemniej teoretyczne zagadnienia, jakie pojawiły się w trakcie badań nad obliczeniami równoległymi, istotnie poszerzyły dziedzinę teorii obliczeń i uczyniły ją jeszcze ciekawszą.

Wprowadzając algorytmy równoległe wraz z odpowiednia technologią, chcielibyśmy uzyskać następujące korzyści:

• Radykalne przyspieszenie obliczeń. Na ogół wymagamy, by czas był funkcją polilogarytmiczną od rozmiaru wejścia.
• Liczba procesorów nie była nierozsądnie duża. Sprowadza się to do wymagania, aby była ona wielomianowa od rozmiaru danych.

Modele obliczeń równoległych

Najważniejsze modele obliczeń równoległych to:

• PRAM -- równoległa maszyna RAM
• sieci procesorów o ustalonej topologii połączeń: krata, hiperkostka i wiele innych,
• układy logiczne.

Podstawowym modelem do opisu algorytmów równoległych jest maszyna PRAM, posłużymy się nią, przedstawiając równoległe rozwiązania przykładowych problemów. Technologicznie PRAM nie jest realizowalna, ale abstrahuje od uwarunkowań konstrukcyjnych i pozwala wypowiadać się wystarczająco ogólnie i ściśle o złożoności problemów algorytmicznych. W przeciwieństwie do niej, sieci procesorów o ustalonej topologii praktycznie się produkuje, natomiast poszczególne rozwiązania algorytmiczne dla tych modeli trudniej przenoszą się na inne modele i przez to są mniej ogólne. W naszych rozważaniach ten model pominiemy.

Natomiast układy logiczne stanowią dobrze zbadany model, pozwalający analizować problemy również pod kątem rozwiązań równoległych, i dlatego poświęcimy mu sporo miejsca. Tym bardziej, że na ogół klasy złożoności równoległej definuje się dla tego modelu.

PRAM

Przypomnijmy w skrócie najważniejsze cechy modelu PRAM, znanego czytelnikowi z kursu Zaawansowane algorytmy i struktury danych. W maszynie PRAM (ang. Parallel Random Access Machine mamy:

• nieograniczoną liczbę procesorów; każdy ma swój numer i swoje własne rejestry,
• nieograniczoną wspólną pamięć, jak w maszynie RAM,
• mechanizm (szynę) umożliwiający komunikację każdego procesora z pamięcią w tym samym czasie (o konfliktach dostępu poniżej).

Najczęściej dla modelu PRAM (ale i również modelu sieci procesorów o ustalonej topologii) zakłada się, że procesory wykonują synchronicznie ten sam program, operując być może na różnych danych w tej samej pamięci, ale w każdym momencie wykonując taki sam rozkaz. Odstępstwo może być tylko jedno: procesor może w danym cyklu rozkazowym nie wykonywać żadnej czynności, czyli wyłączać się na skutek spełnienia określonych warunków.

Opuszczając techniczne problemy przydziału procesorów do poszczególnych operacji, zapiszmy przykładowy prosty algorytm równoległy: mnożenie macierzy. Stosujemy język "work/time", w którym opisuje się pracę wykonywaną przez program w kolejnych jednostkach czasu, bez podawania dokładnie które procesory wykonują daną czynność. Słowo kluczowe in-par-do jest skrótem od in parallel do.

Algorytm [Równoległe mnożenie macierzy]

---

Wejście: Macierze $A,B$ rozmiaru $n\times n,n=2^{p}$.
Wyjście: Iloczyn $C=AB$.
begin
1.  for 1 <= i,j,k <= n  in-par-do
2.    D[i,j,k]:=A[i,k]*B[k,j]
3.  for q=1,2,\ldots,p do
4.    for 1<=i,j<=n, 1<=k<=n/(2**q) in-par-do
5.      D[i,j,k]:=D[i,j,2k-1]+D[i,j,2k]
6.  for 1<=i,j<=n in-par-do
7.    {C[i,j]:=D[i,j]
end

Algorytm działa na $n^{3}$ procesorach, w czasie równoległym $O(\log n)$. Praca jaką wykonuje jest następująca:

Krok 2: $n^{3}$.

Krok 5: $n^{3}/2+n^{3}/4+\ldots n^{3}/n=O(n^{3})$.

Krok 7: $n^{2}$.

W sumie $O(n^{3})$. Jest to zatem algorytm optymalny pod względem pracy. Można go w łatwy sposób przekształcić, tak aby zachowana była praca oraz czas, natomiast liczba procesorów była optymalna i wynosiła $O(n^{3}/\log n)$.

Załóżmy teraz, że na wejściu jest kwadratowa macierz logiczna, $A[i,j]=1$ oznacza, że w grafie istnieje krawędź z $i$ do $j$. Interesuje nas rozwiązanie problemu REACHABILITY.

Ćwiczenie 2.1

Naszkicuj algorytm równoległy znajdowania przechodniego domknięcia grafu. Pożądany czas równoległy i praca to odpowiednio $O(\log ^{2}n)$ oraz $O(n^{3}\log n)$.

Wskazówka

Zastosuj algorytm mnożenia macierzy.

Rozwiązanie

W algorytmie mnożenia macierzy załóż, że na wejściu jest macierz logiczna $A$ oraz zamień dodawanie na alternatywę, a mnożenie na koniunkcję. Obliczanie przechodniego domknięcia sprowadza się do obliczenia $A^{n}$. Następnie zastosuj znany Ci na pewno algorytm potęgowania obliczający $x^{k}$ za pomocą $O(\log k)$ mnożeń.

Obwody logiczne

Obwody logiczne poznaliśmy już w module 2. Przekonaliśmy się, że stanowią uniwersalny model obliczeń: mogą symulować maszynę Turinga. Ta własność, a jeszcze bardziej jej dowód, przyda nam się podczas omawiania klas złożoności dla obliczeń równoległych.

Ze względu na podobieństwo do rzeczywistej architektury komputera obwody logiczne wydają się być bardzo realistycznym modelem. Z drugiej strony, w "prawdziwych" komputerach równoległych równocześnie działają procesory, a nie tylko bramki logiczne. Tutaj więc każdą bramkę obwodu traktujemy jako procesor, co wydaje się bardzo ograniczającym założeniem. Tak jednak nie jest, a rezultaty złożonościowe dotyczące obwodów przenoszą się na rzeczywiste obliczenia równoległe.

Równoległość w obwodzie logicznym polega na tym, że bramki na kolejnych poziomach, poczynając od bramek wejściowych do wyjściowych, obliczane są równocześnie. Praca algorytmu (odpowiadająca złożoności sekwencyjnej, czyli po rozwinięciu obliczenia na jednym procesorze) to wielkość obwodu, czyli liczba bramek. Czas równoległy to głębokość obwodu, długość najdłuższej ścieżki od bramki wejściowej do wyjściowej. Warto przypomnieć sobie algorytm, który dla zadanego obwodu oblicza głębokość obwodu oraz poszczególne poziomy.

Ćwiczenie 2.2

Napisz algorytm, który dla zadanego grafu $G=(V,E)$ skierowanego acyklicznego wylicza długość $d$ najdłuższej ścieżki w tym grafie oraz dzieli zbiór wierzchołków $V$ na $d+1$ podzbiorów $V_{0},\ldots ,V_{d}$ takich, że dla każdego $i$, $V_{i}$ jest zbiorem niezależnym oraz dla każdej krawędzi $(u,v)$ w $G$, jeśli $u\in V_{i},v\in V_{j}$, to $i<j$.

Wskazówka

Posortuj topologicznie graf $G$.

Istnieje bardzo ważna różnica między maszyną PRAM a obwodami logicznymi, nie w aspekcie mocy obliczeniowej, a uniwersalności.

1. Algorytm na maszynie PRAM (podobnie jak dla RAM czy maszyny Turinga) jest skonstruowany dla danych dowolnych rozmiarów.
2. Obwód logiczny ma ściśle określoną liczbę bramek, a więc rozpoznaje instancje ściśle określonego rozmiaru. Dla innego rozmiaru danych obwód może mieć zupełnie inną "logikę budowy".

Aby upodobnić pod tym względem obwody logiczne do innych modeli, nakładamy dodatkowo wymaganie, by struktura obwodu dla coraz większych rozmiarów danych była obliczalna.

Definicja 2.3

Rodzina $(W_{1},W_{2},\ldots )$ obwodów logicznych jest jednostajna, jeśli istnieje maszyna Turinga $M$ o złożoności pamięciowej $O(\log n)$, która dla danych wejściowych postaci $1^{n}$ generuje $W_{n}$.

Uwaga 2.4

Rodzina układów logicznych, która nie jest jednostajna, może rozwiązać problem nierozstrzygalny! Na przykład, nierozstrzygalny jest język unarny (czyli o słowach nad alfabetem jednoelementowym) $L=\{1^{<M,w>}:$ M akceptuje w $\}$ ($<M,w>$ oznacza kod binarny maszyny M i słowa wejściowego w). Układy dla poszczególnych $n$ są zbudowane w ten sposób, że jeśli $1^{n}\in L$, to układ oblicza koniunkcję wszystkich wejść, więc akceptuje tylko wtedy, gdy są to same jedynki, a dla $1^{n}\notin L$ ma dodatkową bramkę wyjściową generującą zero i żadnych innych połączeń (ignoruje wejście). Nie potrafimy obliczać takich układów dla wszystkich $n$, ale wiemy, że one istnieją!

Ćwiczenie 2.5

Skonstruuj obwód logiczny, możliwie o najmniejszej głębokości, rozwiązujący problem REACHABILITY.

Wskazówka

Najprościej jest wykorzystać algorytm równoległy obliczania przechodniego domknięcia, który jest tematem jednego z poprzednich ćwiczeń.

Rozwiązanie

Algorytm ma tę własność, że niezależnie od wyników obliczeń dotychczasowych, obliczenia następne wykonywane są zawsze dla takich samych danych (własność niewrażliwości na dane, ang. oblivious. Ponieważ jedyne operacje na danych to alternatywa i koniunkcja, więc algorytm, będący kolejnymi wywołaniami procedury mnożenia macierzy, można zapisać jako wielopiętrowy układ logiczny, o głębokości równej złożoności algorytmu, czyli $O(\log ^{2}n)$.

Klasy złożoności

Model obwodów logicznych

Umownie zakładamy, że algorytm równoległy jest efektywny, jeśli działa w czasie polilogarytmicznym, na wielomianowej liczbie procesorów. O problemie mówimy, że można go efektywnie zrównoleglić, jeśli ten problem posiada efektywny algorytm równoległy. Formalnie definiujemy takie algorytmy, wprowadzając klasę NC.

Definicja 3.1

Dla $n\geq 1$ klasa $N^{i}$ to zbiór języków $L$ takich, że $L$ jest akceptowany przez jednostajną rodzinę układów logicznych rozmiaru wielomianowego i głębokości $O(\log ^{i}n)$. Przyjmujemy oznaczenie $NC=\bigcup _{j>0}NC^{i}$.

Istnieją ciekawe związki między klasami złożoności równoległej czasowej a klasami złożoności pamięciowej -- przy zbliżonych funkcjach ograniczających dany zasób. Podstawowe z nich to poniższe dwa twierdzenia.

Twierdzenie 3.2

$NC^{1}\subseteq L$.

Dowód tego twierdzenia jest jednym z ćwiczeń końcowych.

Twierdzenie 3.3

$NL\subseteq NC^{2}$.

Dowód

Niech $L$ będzie językiem nad alfabetem 0,1 akceptowanym przez niedeterministyczna maszynę $M$ o złożoności pamięciowej $\log n$. Aby wykazać, że istnieje jednostajna rodzina obwodów logicznych $(W_{1},W_{2},\dots )$ akceptujących $L$, o głębokości $O(\log ^{2}n)$, należy skonstruować maszynę Turinga $M$, działająca w pamięci logarytmicznej, która dla słowa wejściowego $1^{n}$ generuje obwód $W_{n}$ akceptujący zbiór $L\cap \{0,1\}^{n}$. Najpierw opisujemy procedury składowe:

1. Generowanie grafu konfiguracji $G$. Konfiguracja składa się ze stanu, zawartości taśmy roboczej i położenia głowic na obu taśmach. Nie zawiera ona zawartości taśmy wejściowej, zatem wierzchołki tego grafu zależą, przy ustalonej $M$, tylko od $n$.
   Niech $u,v$ będą różnymi konfiguracjami, przy czym $u$ zawiera pozycję $j$ na taśmie wejściowej. Definiujemy krawędź $(u,v)$ w $G$, jeśli $v$ może być osiągnięta z $u$ w 1 ruchu $M$. Jeśli przejście z $u$ do $v$ ma miejsce tylko gdy $i$-ty bit wejściowego słowa jest równy 1, to etykietujemy tę krawędź jedynką, jeśli tylko dla 0, to zerem, a jeśli niezależnie od tego bitu, to etykieta jest pusta. Wynikiem jest lista wierzchołków i lista krawędzi, z etykietami.
   Ponieważ liczba możliwych konfiguracji maszyny $M$ wynosi $O(n)$, więc skonstruowanie takiego grafu jest wykonalne w pamięci logarytmicznej.
2. Konstrukcja obwodu logicznego obliczającego przechodnie domknięcie grafu $H$ o $p$ wierzchołkach. Bramek wejściowych jest $p^{2}$ i każda informuje o istnieniu - lub nie - jednej krawędzi. Problem przechodniego domknięcia należy do $NC^{2}$, o czym przekonaliśmy się, analizując algorytm równoległy w modelu PRAM dla tego problemu. Zatem procedura 2 działa w pamięci logarytmicznej od rozmiaru grafu.

Maszyna Turinga $M$ generująca obwód $W$ o $n$ wejściach, działa następująco:
# wywołaj procedurę 1 aby obliczyć rozmiar grafu $G$.
# wypisz nowe bramki wejściowe $b_{1},\ldots ,b_{n}$.
# wywołaj procedurę 2 zmodyfikowaną następująco:
- za każdym razem, gdy wypisujesz na wyjście bramkę wejściową
(odpowiadającą za jakąś krawędź grafu) wywołuj od początku procedurę
1, aby otrzymać etykietę tej krawędzi i jakich konfiguracji dotyczy,
i w zależności czy etykieta jest równa 0, 1 czy pusta, dodaj
odpowiedni układ pobierający jedną z nowych bramek wejściowych $b_{i}$,
- dodaj układ sprawdzający na końcu czy istniej ścieżka od
konfiguracji początkowej do akceptującej; jego wynik to
wartość wyliczana przez obwód

Zauważmy jeszcze, że w punkcie 3 maszyna $M$ wielokrotnie wywołuje procedurę 2, gdyż ze względu na ograniczenie pamięciowe nie może sobie pozwolić na zapisanie $G$ na taśmie roboczej. Jest to ten sam chwyt, co zastosowany w dowodzie przechodniości redukcji logarytmicznej, w module 2.

Zakończymy ten fragment rozważań własnością, która nie jest niespodzianką.

Twierdzenie 3.4

$NC\subseteq P$.

Ćwiczenie 3.5

Udowodnij powyższe twierdzenie.

Rozwiązanie

Dla zadanego języka $L\in NC^{i}$ należy najpierw wygenerować obwód $W_{i}$, co można zrobić w pamięci logarytmicznej, a więc w czasie wielomianowym. Następnie wykonuje się najzwyklejszą symulację obwodu, rozpatrując jego bramki w porządku topologicznym. Bramek jest wielomianowa liczba. Pytanie: czy głębokość obwodu ma tutaj znaczenie?

Klasy w modelu PRAM

Ważny aspekt dotyczący modelu PRAM, o którym do tej pory nic nie mówiliśmy, to kwestia konfliktów podczas dostępu do pamięci. Czy dana komórkę w tym samym czasie może czytać lub zapisywać więcej niż jeden procesor? Przy równoczesnym zapisie należy jeszcze określić jego semantykę. Wyróżniamy następujące (pod)modele, w kolejności od najsłabszych:

• EREW (exclusive read/write): algorytmy, w których równoczesny dostęp do tej samej komórki pamięci w ogóle nie występuje,
• CREW (concurrent read, exclusive write): dopuszczalny jest równoczesny odczyt z tej samej komórki,
• CRCW: dopuszczalny równoczesny odczyt oraz równoczesny zapis. Z synchroniczności modelu PRAM wynika, że nie jest możliwe, aby jeden procesor czytał, a drugi zapisywał w tym samym czasie do tej samej komórki.

W modelu CRCW wyróżnia się kilka dalszych (pod)modeli, ze względu na sposób rozstrzygania konfliktów zapisu. Dla naszych rozważań są one nieistotne, gdyż możliwe są symulacje między poszczególnymi wariantami modelu CRCW, zmieniające wprawdzie wielomianowo liczbę procesorów (zarazem więc pracę), ale działające w tym samym czasie.

Przyjmijmy oznaczenie następujące: $\mathrm {EREW} ^{k}$ to zbiór języków akceptowanych przez maszynę EREW o wielomianowej liczbie procesorów i złożoności czasowej $O(\log ^{k}n)$. Analogiczne oznaczenia wprowadzamy dla modeli CREW i CRCW.

Wspomnijmy jeszcze o jednym modelu oznaczanym przez AC. Jest to wariant jednostajnych obwodów logicznych, w którym pomijamy ograniczenie na stopień wejściowy bramki. Na przykład, alternatywa $k$ bitów może być obliczana obwodem o głębokości 1. $AC^{j}$ z definicji to klasa języków akceptowanych przez takie obwody, o głębokości $O(log^{j}n)$.

Znając techniki konstrukcji maszyn PRAM, nietrudno dowieść, że $NC^{j}\subseteq \mathrm {EREW} ^{j}$. Jeszcze łatwiej pokazać, że $AC^{j}\subseteq NC^{j+1},j=0,1,\ldots$. Znacznie bardziej złożony jest dowód trzeciej własności: $\mathrm {CRCW} (log^{j}n)=AC^{j}$.

Z powyższych trzech inkluzji otrzymujemy hierarchię klas złożoności równoległej. Dla $j=1,2,\ldots$:

$\mathrm {NC} ^{j}\subseteq \mathrm {EREW} ^{j}\subseteq \mathrm {CREW} ^{j}\subseteq \mathrm {CRCW} ^{j}\subseteq \mathrm {AC} ^{j}\subseteq \mathrm {NC} ^{j+1}$

P-zupełność

Przekonaliśmy się już, że pojęcie NP-zupełności odgrywa fundamentalną rolę w analizie złożoności problemu pod kątem istnienia rowiązań wielomianowych. Okazuje się, że P-zupełność, poza tym, że jest to narzędzie badań teoretycznych nad klasami złożoności, dostarcza analogicznych narzędzi do badania, czy dany problem jest łatwy do zrównoleglenia. To co wiadomo w praktyce, to:

• nie znaleziono jak dotąd żadnego języka wspólnego dla klasy NC oraz P-zupełnych,
• uzasadniona jest hipoteza, że $NC\not \subseteq P$.

W tej sytuacji problemy P-zupełne uważa się za trudne do zrównoleglenia.

Przypomnijmy definicję problemu P-zupełnego. Formalnie, pojęcie to definiuje się dla języków - są one odpowiednikami problemów decyzyjnych, powstałymi przez ustalone kodowanie instancji w słowa.

Definicja 4.1

Język $L\subseteq \{0,1\}^{*}$ jest P-zupełny, jeśli $L\in P$ oraz dla każdego języka $L'\in P$ istnieje redukcja logarytmiczna $L'\leq _{L}L$.

NP-zupełność możemy definiować za pomocą redukcji wielomianowej lub redukcji Turinga -- dla P-zupełności nie miałoby to sensu. Dlaczego?

Co więcej, redukcja logarytmiczna zachowuje złożoność równoległą. Związek między redukcją logarytmiczną a przynależnością do klasy NC jest następujący:

Twierdzenie 4.2

Jeśli $Q_{1}\leq _{L}Q_{2}$ oraz $Q_{2}\in NC^{j},j\geq 2$, to $Q_{1}\in NC^{j}$.

Ćwiczenie 4.3

Udowodnij powyższe twierdzenie.

Rozwiązanie

Zauważ, że złożenie dwóch algorytmów klasy $NC^{j}$ jest algorytmem klasy $NC^{j}$. Wystarczy teraz skorzystać z faktu, że $NL\subseteq NC^{2}$.

Metodologia dowodzenia zupełności w klasie P jest taka sama jak w przypadku klasy NP. Ponieważ praktycznie znaczenie P-zupełności jest jednak dużo mniejsze, repertuar metod pojawiających się tutaj nie ma porównania z wielką gamą technik i gadżetów w dowodach NP-zupełności. Większość znanych dowodów posługuje się redukcją z problemu CIRCUIT VALUE lub którąś z jego modyfikacji.

Przypomnijmy, że aby dowieść, że dany problem $\Pi$ jest P-zupełny, wystarcza:

• wykazać, że $\Pi \in P$,
• wybrać P-zupełny problem $Q$ i zredukować go logarytmicznie do $\Pi$.

Rolę pierwszego problemu zupełnego w P gra na ogół problem wartościowania obwodu logicznego.

Problem [CIRCUIT VALUE]

Wejście: Obwód logiczny z ustalonymi wartościami bramek wejściowych
Wyjście: TAK, jeśli wartość logiczna obwodu jest 1, NIE w przeciwnym przypadku.

Twierdzenie 4.4

Problem CIRCUIT VALUE jest P-zupełny.

Dowód

Dany jest język $L\in P$ i deterministyczna maszyna Turinga $M$ rozpoznająca $L$ w czasie wielomianowym. Należy skonstruować maszynę Turinga $M'$, która dla zadanego słowa $w\in \{0,1\}^{*}$ wygeneruje obwód $C(w)$ z ustalonymi wartościami bramek wejściowych taki, że $M$ akceptuje $w$ wtedy i tylko wtedy, gdy $C(w)=1$.

Przypomnijmy sobie redukcję maszyny Turinga do obwodu logicznego, skonstruowaną w module 2. Redukcja ta miała na celu wykazanie, że maszyna Turinga działająca w czasie $T(n)$ może być symulowana przez obwód logiczny o $O(T^{2}(n))$ bramkach.

Korzystamy z tej samej redukcji, co zapewnia nam warunek "wtedy i tylko wtedy". Uzupełnienia wymaga algorytmiczna strona redukcji. Należy wykazać, że obwód symulujący maszynę może być skonstruowany przez algorytm o logarytmicznej złożoności pamięciowej.

Łatwo jednak zauważyć, że to prawda. Dla ustalonej $M$ podukłady stosowane w redukcji są tej samej ustalonej postaci. Algorytm redukcji musi je wyprodukować w odpowiedniej ilości i łączyć w sieć. Ale do tego wystarcza zliczanie -- operacje na indeksach.

Przytoczmy jeszcze dla porządku rzecz oczywistą: problem CIRCUIT VALUE należy do P, co kończy dowód.

Jednym z trudniejszych problemów w klasie P jest problem znajdowania maksymalnego przepływu. Żadnego z wielu algorytmów dla tego problemu nie udało się efektywnie zrównoleglić. Znajduje to odzwierciedlenie w jego P-zupełności. Dowodzimy tej własności dla pewnej szczególnej wersji problemu, mianowicie pytania, czy maksymalny przepływ w sieci z całkowitymi przepustowościami jest nieparzysty.

Przyjmijmy oznaczenie: sieć przedstawiamy jako piątkę $N=(V,E,s,t,c)$, gdzie $V$ i $E$ to zbiór wierzchołków i krawędzi, $s$ i $t$ to źródło i spływ, $c$ to funkcja przepustowości krawędzi.

Problem [PARITY MAX FLOW]

Wejście: Sieć $N=(V,E,s,t,c)$.
Wyjście: TAK, jeśli maksymalny przepływ jest liczbą nieparzystą, NIE w przeciwnym przypadku.

Twierdzenie 4.5

Problem PARITY MAX FLOW jest P-zupełny.

Rysunek 11.1.

Rysunek 11.2.

Rysunek 11.3.

Rysunek 11.4.

Dowód

Do redukcji wybierzmy problem MONOTONE CIRCUIT VALUE. Obwody monotoniczne to takie, w których nie występują negacje. Jest to oczywiście zawężenie problemu CIRCUIT VALUE, dalej jednak P-zupełne (dowód stanowi ćwiczenie). Na wejściu mamy obwód logiczny w postaci grafu skierowanego $G=(V,E),|V|=n$. Przyjmijmy kilka założeń o tym grafie.

Założenie 1: bramka wyjściowa w $G$ jest typu OR. Jeśli tak nie jest (czyli jest AND), to można ją dać na wejście do nowej wyjściowej bramki OR, której drugim wejściem jest nowa bramka ustalona na stałe na 0.

Założenie 2: każda bramka ma stopień wyjściowy co najwyżej 2. Jeśli tak nie jest, to najpierw przekształcamy obwód, tak jak pokazano na Rysunku 11.1.

Założenie 3: Bramki ponumerowane są w odwrotnym porządku topologicznym -- bramka wyjściowa ma numer 0, poprzedniki każdej bramki mają numery od niej większe. Bramki utożsamiamy z ich numerami. Zobacz kolejny Rysunek 11.2.

Graf $G$ przekształcamy w sieć $N=(V',E',s,t,c)$ następująco:

• do zbioru wierzchołków dodajemy zródło $s$ i spływ $t$,
• ze źródła prowadzimy krawędź do każdego wierzchołka wejściowego $u$ o wartości 1 i ustalamy jej przepustowość na $d2^{u}$, gdzie $d$ jest stopniem wychodzącym z $u$,
• każdej krawędzi $(u,v)$ grafu $G$ dajemy przepustowość $2^{u}$,
• dodajemy krawędź $(0,t)$ z przepustowością 1,
• dla każdego wierzchołka $u$ typu OR dodajemy krawędź $(u,s)$ z przepustowością $S(u)$, gdzie $S(u)$ to suma pojemności wchodzących minus suma pojemności wychodzących,
• dla każdego wierzchołka $u$ typu AND dodajemy krawędź $(u,t)$ z przepustowością $S(u)$, gdzie $S(u)$ to suma pojemności wchodzących minus suma pojemności wychodzących.

Zobacz kolejny Rysunek 11.3.

Jeśli rozpatrujemy tylko krawędzie grafu $G$, to dla każdej bramki typu AND lub OR otrzymujemy przepustowość wchodzącą co najmniej dwa razy większą niż wychodzącą - bo o przepustowości krawędzi decyduje numer jej początku, który jest większy niż numer końca. Zatem krawędzie prowadzące do $s$ i $t$ mają niezerowe przepustowości.

Przepływ $F$ nazywamy standardowym, jeśli przez każdą bramkę, która ma wartość 1, ten przepływ jest maksymalny (równy sumie przepustowości wychodzących) oraz przez każdą bramkę o wartości 0 jest zerowy.

Po pierwsze, przepływ standardowy zawsze istnieje. Najpierw nasycamy wszystkie krawędzie wychodzące ze źródła, co powoduje, że bramki wejściowe z wartością 1 mają pełny przepływ, a bramki wejściowe z wartością 0 mają przepływ zerowy. Indukcyjnie, jeśli bramka $v$ jest typu OR i ma wartość 1, to co najmniej jeden poprzednik ma wartość 1 i przysyła przepływ wystarczający do nasycenia ewentualnych dwóch odpływów z bramki $v$, ewentualny nadmiar odpłynie do $s$. Jeśli bramka OR ma wartość 0, to oba poprzedniki mają wartość 0, i z założenia indukcyjnego nic nie przysyłają. Podobne rozumowanie działa dla bramek typu AND.

Zobacz kolejny Rysunek 11.4.

Po drugie, przepływ standardowy jest maksymalny. To łatwo pokazać na podstawie twierdzenia o maksymalnym przepływie i minimalnym przekroju. Wystarczy do jednego podzbioru dać źródło i wszystkie wierzchołki o wartości 1, do drugiego pozostałe.

Na koniec zauważmy, że przepływ standardowy ma wartość nieparzystą wtedy i tylko wtedy, gdy wykorzystuje krawędź z bramki wyjściowej do spływu, a to ma miejsce jedynie, gdy obwód na wyjściu ma wartość 1.

Równoległość i randomizacja

Załóżmy, że bardzo zależy nam, aby dany problem rozwiązać w sposób równoległy, z zachowaniem możliwie najlepszych parametrów złożonościowych. Ustaliwszy jego P-zupełność, zamiast pogodzić się z nieistnieniem (najprawdopodobniej) algorytmu klasy NC, możemy próbować osłabić nie złożoność, a dokładność rozwiązania. Jednak tym razem nie chodzi o podejście aproksymacyjne (jak w przypadku problemów NP-trudnych), a o wykorzystanie randomizacji.

W przypadku obwodów logicznych polega ona na dołożeniu do obwodu $W_{n}$ o $n$ wejściach kolejnych $m(n)$ bramek wejściowych, które zawierają bity losowe. Zakładamy przy tym, że $m(n)$ jest wielomianem. Taki obwód nazywamy randomizowanym.

Definicja 5.1

Klasą $\mathrm {RNC} ^{j}$ nazywamy zbiór języków $L$ takich, że $L$ posiada jednostajną rodzinę $W_{1},W_{2},\ldots$ obwodów logicznych randomizowanych o wysokości $O(\log ^{j}(n))$ i wielomianowej liczbie bramek taką, że dla dowolnego $x\in \{0,1\}^{n}$ prawdopodobieństwo, że obwód akceptuje $x$ jest:

• większe lub równe $1/2$, jeśli $x\in L$,
• mniejsze niż $1/2$, jeśli $x\notin L$.

Analogią z klasą RP (moduł 10) jest oczywista.

Powyżej wykazaliśmy, że problem maksymalnego przepływu jest P-zupełny, co w praktyce oznacza, że nie jesteśmy w stanie skonstruować algorytmu NC. Blisko związany z maksymalnym przepływem jest problem skojarzenia w grafach. W szczególności, problem znajdowania maksymalnego skojarzenia w grafach dwudzielnych redukuje się do problemu maksymalnego przepływu, na czym zresztą bazuje algorytm Hopcrofta - Karpa dla skojarzeń, który poznaliśmy na kursie Zaawansowane algorytmy i struktury danych.

Zatem wydaje się, że problem znajdowania maksymalnego skojarzenia jest nieco łatwiejszy niż znajdowanie maksymalnego przepływu. Do tej pory jednak nie znaleziono dla niego ani algorytmu o parametrach klasy {NC}, ani dowodu P-zupełności.

Okazuje się jednak, że randomizacja może w tym przypadku pomóc. Naszkicujmy ideę (bardzo skomplikowanego) algorytmu RMATCH znajdującego skojarzenie o maksymalnej liczności w dowolnym grafie.

Załóżmy, że na wejściu mamy graf $G=(V,E)$, o $n$ wierzchołkach i $m$ krawędziach. Tworzymy symboliczną macierz incydencji dla $G$ (macierz Tutte'go), kładąc:

• jeśli $(i,j)$ jest krawędzią (dowolnie ustalamy porządek wierzchołków na krawędzi), to $T(i,j)=x_{ij},T(j,i)=-x_{ij}$,
• w przeciwnym przypadku $T(i,j)=T(j,i)=0$.

Na przykład, dla grafu $G=(V,E)$, gdzie $V=\{1,2,3,4\}$, $E=\{(1,2),(2,3),(2,4),(1,3)\}$, macierz Tutte'go ma postać:

$\left[{\begin{array}{rrrr}0&x_{12}&x{_{1}3}&0\\-x_{21}&0&x_{23}&x_{24}\\-x_{31}&-x_{32}&0&0\\0&-x_{42}&0&0\end{array}}\right]$.

Wyznacznik tej macierzy to wielomian wielu zmiennych stopnia $n$.

Twierdzenie 5.2 [Tutte]

Graf $G$ ma skojarzenie doskonałe wtedy i tylko wtedy, gdy $det(T)\neq 0$.

Pierwszą składową algorytmu RMATCH jest procedura randomizacyjna, która sprawdza, czy $det(T)$ nie jest identycznościowo równe 0. Wykorzystuje ona z kolei szybką metodę randomizacyjną obliczania wyznacznika liczbowego. Złożoność tego fragmentu (w modelu PRAM) opisuje poniższy lemat:

Lemat 5.3

Na pytanie, czy zadany graf $G$ posiada doskonałe skojarzenie, można odpowiedzieć za pomocą równoległego algorytmu randomizacyjnego działającego w czasie $O(\log ^{2}n)$ i wykonującego pracę $O(n^{3.5})$.

Bardzo ciekawy jest również następny krok polegający na obliczeniu samego skojarzenia. Podstawowa trudność polega na tym, że graf może mieć wiele skojarzeń doskonałych i wtedy trudno jest "ukierunkować" obliczenie, aby znajdowało jeden z nich (sytuację taka można uznać za wersję problemu łamania symetrii w algorytmach równoległych).

Sposób polega na przypisaniu losowych wag krawędziom, co zapewni z dużym prawdopodobieństwem istnienie unikalnego, minimalnego pod względem wagi, skojarzenia doskonałego. Następnie ponownie korzysta się z macierzy Tutte,go, zastępując w niej symbole zmiennych wylosowanymi wagami. Badając podwyznaczniki tej macierzy ustala się, która krawędź należy do skojarzenia doskonałego.

Ten fragment obliczeń można wykonać algorytmem działającym w takim samym czasie i wykonującym podobną pracę jak poprzedni. Otrzymujemy:

Lemat 5.4

Dla zadanego grafu $G$ można znaleźć skojarzenie doskonałe, o ile takie istnieje, równoległym algorytmem randomizacyjnym działającym w czasie $O(\log ^{2}n)$ i wykonującym pracę $O(mn^{3.5})$.

Trzeci i ostatni krok to redukcja problemu znajdowania maksymalnego skojarzenia do problemu znajdowania maksymalnego skojarzenia doskonałego. Jest to bardzo interesujące ćwiczenie, chociaż ono do probabilistyki już się nie odnosi.

Ćwiczenie 5.5

Wykaż, że problem znajdowania maksymalnego skojarzenia redukuje się (w sensie redukcji Turinga) do problemu znajdowania maksymalnego skojarzenia doskonałego.

Wskazówka

Wystarczy dodawać w odpowiedni sposób nowe wierzchołki i sprawdzać, czy powstały graf ma skojarzenie doskonałe.

Rozwiązanie

Załóżmy, że maksymalne skojarzenie w $G$ ma liczność $s$. Czyli, po znalezieniu maksymalnego skojarzenia, $p=n-2s$ wierzchołków pozostaje nieskojarzonych. Jeślibyśmy utworzyli nowy graf $G'$, dodając do $Gk$ nowych wierzchołków, wraz z krawędziami łączącymi je ze wszystkimi "starymi" wierzchołkami, to teraz w $G'$ istnieje skojarzenie doskonałe. Co więcej, każde skojarzenie doskonałe w $G'$ zawiera maksymalne skojarzenie w $G$ -- bo między nowymi wierzchołkami nie ma krawędzi.

Redukcja zatem polega na przeglądaniu wartości $p,1\leq p\leq n-2$, takich że $n+p$ jest parzyste, i sprawdzaniu, czy otrzymany po dodaniu $p$ nowych wierzchołków (w sposób opisany powyżej) graf ma skojarzenie doskonałe. Po znalezieniu najmniejszego takiego $p$ skojarzenie dla $G$ już łatwo wyliczyć. Oczywiście, wyszukiwanie $p$ o żądanej własności odbywa się metodą połówkową.

Twierdzenie 5.6

Maksymalne pod względem liczności skojarzenie w dowolnym grafie można znaleźć równoległym algorytmem randomizacyjnym o złożoności czasowej $O(\log ^{3}n)$ i wykonywanej pracy $O(mn^{3}.5)$. A zatem, problem ten należy do klasy RNC.

Ćwiczenia dodatkowe

Ćwiczenie 6.1

Udowodnij, że $NC^{1}\subseteq L$.

Wskazówka

Trzeba w pamięci logarytmicznej dokonać wartościowania obwodu logicznego o głębokości $\log n$. Algorytm DFS wydaje się być przydatny, ale są pewne trudności z pamięcią na stos.

Wskazówka

Jeśli obwód nie jest drzewem (stopień wyjściowy bramek większy niż 1), to na stosie trzeba pamiętać numery wierzchołków i pamięć wzrasta do $\log ^{2}n$. Przekształć graf obwodu w drzewo i umiejętnie składaj procedury. Przypomnij sobie, jak się składa redukcje logarytmiczne.

Rozwiązanie

Naszym celem jest skonstruowanie maszyny Turinga z logarytmiczną pamięcią akceptującą zadany język $L\in NC^{1}$. Na wejściu zatem jest słowo o długości n. Składowe maszyny $M$ są następujące:

Rysunek 11.5.

1. Procedura wypisująca obwód logiczny z danej rodziny uniwersalnej. W opisie obwodu, dla każdej bramki podaje listę (co najwyżej dwuelementową) jej poprzedników.

2. Procedura przekształcająca obwód w drzewo. W tym celu rozpatruje wszystkie możliwe ścieżki od bramki wyjściowej obwodu do bramek wejściowych i powiela odpowiednią liczbę razy każdą bramkę, której stopień wyjściowy jest większy niż 1. Powstaje nowy obwód: drzewo, w którym nazwy wierzchołków są liczbami binarnymi, skonstruowanymi jak na Rysunku 11.5.

3. Procedura obliczająca wartość obwodu w postaci drzewa. Aby obliczyć wartość danej bramki, załóżmy, że jest to AND, najpierw rekurencyjnie oblicza się wartość lewego poprzednika i jeśli jest on równy 1, to rekurencyjnie oblicza się prawego następnika (o lewym można już zapomnieć). Powrót z rekurencji odbywa się przez obcięcie ostatniego bitu adresu bramki.

Dzięki adresacji węzłów drzewa rekurencję można zrealizować, pamiętając jedynie nazwę aktualnego wierzchołka -- adres poprzednika przy powrocie z wywołania rekurencyjnego wyznaczamy przez obcięcie ostatniego bitu w adresie aktualnego węzła. Zatem potrzebna pamięć robocza jest rzędu $\log n$.

Ćwiczenie 6.2

Wykaż, że problem MONOTONE CIRCUIT VALUE różniący się od CIRCUIT VALUE tylko tym, że nie dopuszcza się w obwodzie bramek negacji, jest P-zupełny.

Rozwiązanie

Należy zredukować CIRCUIT VALUE do MONOTONE C.V. Wystarcza za pomocą praw de Morgana przesunąć wszystkie negacje w dół, aż do bramek wejściowych. Następnie bramki wejściowe, których następnikami są negacje, zamienić na przeciwne, dodając nowe, jeśli trzeba - gdy bramka wejściowa jest poprzednikiem dwóch bramek, przy czym dokładnie jedna z tych dwóch jest negacją.

Można to zrobić w pamięci logarytmicznej, bo wystarcza przeglądać listę bramek (dla każdej podane jest jej sąsiedztwo), a nie badać struktury obwodu jako grafu.