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

Uwaga: przekonwertowane latex2mediawiki; prawdopodobnie trzeba wprowadzi� poprawki {article}

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 bardzie, ż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 wykonuja daną czynność. Słowo kluczowe in-par-do jest skrótem od in parallel do.

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.{5mm}for 1 <= i,j,k <= n in-par-do
2.{10mm}D[i,j,k]:=A[i,k]*B[k,j]
3.{5mm}for q=1,2,...,p do
4.{10mm}for 1<=i,j<=n, 1<=k<=n/(2**q) in-par-do
5.{15mm}D[i,j,k]:=D[i,j,2k-1]+D[i,j,2k]
6.{5mm}for 1<=i,j<=n in-par-do
7.{10mm}{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+\dots 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.

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

Owody logiczne poznaliśmy już w module 2. Przekonaliśmy się, że stanowią uniwersalny model obliczeń: mogą symulować maszyne 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.

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,\dots ,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.

1. 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, aby struktura obwodu dla coraz większych rozmiarów danych była obliczalna.

Definicja

Rodzina $(W_1,W_2,\dots )$ 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

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 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ą!

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

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

Dla $n\ge 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}N{C}^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

$N{C}^1\subseteq L$.

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

Twierdzenie

$NL\subseteq N{C}^2$.

Dowód

Niech $L$ bedzie 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 byc 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.

1. 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 $N{C}^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:

1. wywołaj procedurę 1 aby obliczyć rozmiar grafu $G$
2. wypisz nowe bramki wejściowe $b_1,\dots ,b_n$
3. 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

$NC\subseteq P$.

Udowodnij powyższe twierdzenie.

Rozwiązanie

Dla zadanego języka $L\in N{C}^i$ należy najpierw wygenerować obwód $W_i$, co mozna 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?

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\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

Język $L\subseteq \{0,1{\}}^{*}$ jest P-zupełny, jeśli $L\in P$ oraz dla każdego języka $L^{\prime }\in P$, istnieje redukcja logarytmiczna $L^{\prime }{\le }_{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

Jeśli $Q_1{\le }_L{Q}_2$ oraz $Q_2\in N{C}^j,j\ge 2$, to $Q_1\in N{C}^j$.

Udowodnij powyższe twierdzenie.

Rozwiązanie

Zauważ, że złożenie dwóch algorytmów klasy $N{C}^j$ jest algorytmem klasy $N{C}^j$. Wystarczy teraz skorzystać z faktu, że $NL\subseteq N{C}^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 $\mathrm{\Pi }$ jest P-zupełny, wystarcza:

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

$\mathrm{\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

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^{\prime }$, 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 byc 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

Problem PARITY MAX FLOW jest P-zupełny.

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.

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.

Graf $G$ przekształcamy w sieć $N=(V^{\prime },E^{\prime },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 $d{2}^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

Zauważmy, że rozpatrując tylko krawędzie grafu $G$, dla każdej bramki typu AND lub OR przepustowość wchodzącą jest co najmniej dwa razy większa 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ścia 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.

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.

Ćwiczenia dodatkowe

Udowodnij, że $N{C}^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ć przydatnym, 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 N{C}^1$. Na wejściu zatem jest słowo o długości n. Składowe maszyny $M$ są następujące:
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.

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.

Dzieki 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$.

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.