Złożoność obliczeniowa/Wykład 12: Problemy funkcyjne i złożoność zliczania

Problemy funkcyjne

Do tej pory rozważaliśmy problemy decyzyjne, które polegały na akceptacji słowa przez maszynę, czyli zwróceniu odpowiedzi "TAK/NIE". Czasem potrzebujemy jednak, aby algorytm zwrócił znacznie więcej informacji. Wtedy przydają nam się problemy funkcyjne, w których od maszyny oczekujemy obliczenia zadanej funkcji. Maszyna na taśmie wejściowej ma zapisane argumenty funkcji, a na taśmie wyjściowej wypisuje wartość funkcji. Naturalne przykłady problemów funkcyjnych są powiązane z analizowanymi już problemami decyzyjnymi.

Przykład 1.1 [Problem FSAT]

Wejście: formuła logiczna $\varphi$ jak dla problemu SAT.
Wyjście: wartościowanie spełniające $\varphi$ lub "NIE", gdy nie istnieje.

Choć nie można bezpośrednio porównać złożoności problemów funkcyjnych i decyzyjnych to łatwo zauważyć, że FSAT jest problemem nie łatwiejszym niż SAT. Z odpowiedzi na problem FSAT można trywialnie obliczyć odpowiedź dla SAT. Okazuje się jednak, że także w drugą stronę przenosi się wielomianowość rozwiązania:

Ćwiczenie 1.2

Sprowadź problem FSAT do SAT przy pomocy wielomianowej redukcji Turinga (korzystając z SAT jako wyroczni).

Wskazówka

Skorzystaj z własności samoredukowalności, tzn. wywnioskuj wartościowanie $\varphi$ na podstawie istnienia wartościowania podformuły $\varphi$.

Rozwiązanie

Najpierw poprzez wywołanie maszyny dla SAT sprawdzamy czy rozwiązanie w ogóle istnieje (w przeciwnym razie zwracamy "NIE"). Następnie algorytm oblicza wartościowanie w sposób następujący: przez $x_1,\dots ,x_n$ oznaczmy zmienne występujące w $\varphi$. W pierwszym kroku obliczamy wartościowanie dla $x_1$.

Najpierw próbujemy wartości 0: ustalamy $x_1$ na 0 i sprawdzamy czy formuła $\varphi$ z tak ustalonym $x_1$ ma rozwiązanie poprzez wywołanie SAT. Jeśli tak, to wartość $x_1$ już znamy. W przeciwnym wypadku wartościujemy $x_1$ na 1. Ponieważ rozwiązanie istnieje dla całej formuły $\varphi$ to druga możliwość podstawienia musi dać rozwiązanie. Powtarzamy krok dla pozostałych zmiennych. Taki algorytm ma złożoność wielomianową i wywołuje SAT liniową liczbę razy.

Podobna własność zachodzi dla problemu TSP, gdzie samoredukowalność nie występuje. Przypominamy problem TSP w wersji funkcyjnej:

Przykład 1.3 [ProblemTSP]

Wejście: graf nieskierowany ważony $G$.
Wyjście: optymalna trasa komiwojażera dla $G$ lub "NIE", gdy nie istnieje.

Ćwiczenie 1.4

Sprowadź problem TSP do TSP(D) (wersji decyzyjnej) przy pomocy wielomianowej redukcji Turinga.

Wskazówka

Rozważ modyfikację $G$, w której waga jednej krawędzi jest zwiększona.

Rozwiązanie

Najpierw ustalamy $K$ - wagę optymalnej trasy komiwojażera przy pomocy wyszukiwania binarnego wywołując każdorazowo algorytm dla TSP(D). Ponieważ maksymalna wartość trasy jest ograniczona z góry przez sumę wag wszystkich krawędzi to w tym procesie wykonamy co najwyżej logarytmiczną liczbę wywołań TSP(D) względem sumy wag, czyli liniową liczbę wywołań w zależności od rozmiaru wejścia. Gdy trasa nie istnieje zwracamy "NIE".

Następnie dla każdej krawędzi grafu sprawdzamy czy należy ona do optymalnej trasy. Oznaczmy kolejną krawędź przez $e$. Ustalamy wagę $e$ na $K+1$ i wywołujemy TSP(D) z kosztem $K$. Jeśli trasa o koszcie $K$ dalej istnieje, to wiemy że krawędź $e$ nie należy do niej, gdyż spowodowałoby to przekroczenie $K$. W tej sytuacji pozostawiamy zwiększoną wagę $e$ i przechodzimy do następnej krawędzi. Gdy trasa nie istnieje, to przywracamy oryginalną wagę $e$. Podobnie postępujemy z pozostałymi krawędziami. Po zakończeniu procesu krawędzie o wagach niższych niż $K+1$ będą stanowić optymalną trasę komiwojażera o koszcie $K$.

Klasy FP i FNP

Można przedstawić zależność pomiędzy problemami decyzyjnymi i funkcyjnymi w sposób formalny. Przypomnijmy, że klasę NP można zdefiniować używając wielomianowo zrównoważonej i rozstrzygalnej relacji. Jeśli $L$ należy do NP to istnieje relacja $R_L(x,y)$, taka że $x\in L$ wtedy i tylko wtedy gdy istnieje $y$ taki, że $R(x,y)$. Poprzez $FL$ oznaczamy problem funkcyjny polegający na obliczeniu na podstawie $x$ wartości $y$ takiej, że $R_L(x,y)$ o ile taka wartość istnieje lub zwróceniu odpowiedzi "NIE" w przeciwnym wypadku.

Klasę wszystkich problemów funkcyjnych, które powstają w ten sposób z klasy NP oznaczamy poprzez FNP. Klasę FP definiujemy jako podzbiór tych problemów z FNP dla których istnieje algorytm wielomianowy. Oczywiście FP$\subseteq$FNP natomiast pytanie czy FP=FNP jest otwarte. Co ciekawe problem FSAT należy do FNP jednakże o TSP tego nie wiemy. Dzieje się tak dlatego, iż nie znamy algorytmu stwierdzającego, czy podana trasa jest optymalna. FHORNSAT (czyli funkcyjna wersja HORNSAT -- zawężenia SAT) a także obliczanie idealnego skojarzenia w grafie dwudzielnym są przykładami problemów z klasy FP.

Podobnie do klas decyzyjnych i tutaj można zdefiniować pojęcia redukcji i zupełności. Mówimy, że problem funkcyjny $A$ redukuje się do $B$ jeśli istnieją funkcje na słowach $R(x)$ oraz $S(y)$ obliczalne w pamięci logarytmicznej takie, że jeśli $x$ jest instancją dla problemu $A$ to $R(x)$ jest instancją dla problemu $B$. Oraz jeśli $y$ jest dopuszczalnym rozwiązaniem dla $B$ to $S(y)$ jest dopuszczalnym rozwiązaniem dla $A$. Redukcje można składać. Klasy FP i FNP są zamknięte na redukcje.

Zupełność jest definiowana w sposób naturalny, tzn. problem funkcyjny $L$ jest zupełny w klasie FC jeśli należy do FC i wszystkie problemy z tej klasy redukują się do niego. Problem FSAT jest natomiast przykładem problemu FNP-zupełnego (patrz ćwiczenie 3.1).

Twierdzenie 1.5

$FP=FNP$ $\iff$ $P=NP$.

Dowód

Z wcześniejszych analiz wiemy, że FSAT jest wielomianowy wtedy i tylko wtedy gdy SAT jest wielomianowy. Ponieważ są to problemy zupełne dla odpowiednich klas to stąd otrzymujemy tezę.

Klasa TFNP

Wśród problemów z klasy FNP można wyróżnić interesującą klasę problemów całkowitych. Odpowiadają one tym problemom funkcyjnym, dla których rozwiązanie zawsze istnieje. Formalnie problem funkcyjny z klasy FNP nazywamy całkowitym jeśli $R$ (relacja występująca w definicji problemu funkcyjnego) spełnia warunek, iż dla każdego $x$ istnieje przynajmniej jedno $y$ takie, że $R(x,y)$.

Klasę wszystkich problemów całkowitych oznaczamy przez TFNP. Klasa ta zawiera wiele ciekawych problemów, o których nie wiadomo, czy należą do FP, a które mogą sugerować, że są prostsze niż problemy zupełne z FNP. Sztandarowym problemem jest problem rozkładu liczby na czynniki pierwsze, niesłychanie interesujący z punktu widzenia praktycznego i wciąż bez znanego algorytmu wielomianowego:

Przykład 1.6 [Problem FACTORING]

Wejście: liczba naturalna $n$
Wyjście: rozkład $n$ na czynniki pierwsze.

Każda liczba naturalna posiada swój rozkład na czynniki pierwsze. To sprawia, że FACTORING jest problemem funkcyjnym całkowitym z klasy TFNP. Kluczowy dla tego stwierdzenia jest fakt, że dzięki przynależności problemu sprawdzania czy liczba jest pierwsza do klasy P łatwo jest stwierdzić, czy rozkład jest rzeczywiście rozkładem na czynniki pierwsze. Fakt, że rozwiązanie zawsze istnieje, może ułatwić znalezienie efektywnego algorytmu. Takiego warunku nie spełniają rozważane wcześniej FSAT i TSP.

Rozważmy poniższy problem funkcyjny obliczania optymalnego stanu sieci:

Problem HAPPYNET.

Przykład 1.7 [Problem HAPPYNET]

Wejście: graf nieskierowany ważony $G=(V,E)$ z wagami całkowitymi $w$
Wyjście: wartościowanie $S:V\mapsto \{-1,1\}$ takie, że każdy wierzchołek $v\in V$ jest szczęśliwy, tzn.:

$S(v)\sum _{(v,u)\in E}S(u)w(v,u)⩾0$

Mówiąc obrazowo, warunek szczęśliwości oznacza, że wierzchołek chce mieć ten sam stan co wierzchołki połączone z nim wagą dodatnią i przeciwny dla wagi ujemnej. Na rysunku Problem HAPPYNET wierzchołek 1 jest nieszczęśliwy, a 4 jest szczęśliwy.

Łatwo zauważyć, że HAPPYNET należy do klasy FNP, gdyż łatwo sprawdzić, czy wartościowanie daje stan szczęśliwy. Co zaskakujące jednak, jest on problemem funkcyjnym całkowitym, tzn. szukany stan "szczęśliwości" zawsze istnieje:

Ćwiczenie 1.8

Udowodnij, że problem HAPPYNET należy do klasy TFNP.

Wskazówka

Rozważ algorytm iteracyjny polegający na zmianie stanu wierzchołka nieszczęśliwego.

Rozwiązanie

Zdefiniujmy funkcję jakości wartościowania $S$:

$\varphi (S)=\sum _{(v,u)\in E}S(v)S(u)w(v,u)$

Załóżmy, że $v$ nie jest szczęśliwy przy ustalonym wartościowaniu $S$, tzn.:

$S(v)\sum _{(v,u)\in E}S(u)w(v,u)=\alpha <0$

Zdefiniujmy wartościowanie $S^{\prime }$ jako $S$ ze zmienionym stanem dla $v$. Nietrudno zauważyć, że $\varphi (S^{\prime })=\varphi (S)+2\alpha$. Zatem funkcja $\varphi$ wzrosła o przynajmniej 2. Możemy zapisać algorytm iteracyjny:

 $S:=$ dowolne wartościowanie
 while istnieje wierzchołek nieszczęśliwy $v$ do
   $S(v):=-S(v)$
 end while

Ponieważ wartość $\varphi$ jest ograniczona na moduł przez sumę wszystkich wag $G$ to algorytm ten zatrzyma się zwracając "szczęśliwy" stan.

Powyższy algorytm jest oczywiście pseudowielomianowy ze względu na powiązanie czasu działania z wartością sumy wag. Obecnie nie jest znany algorytm wielomianowy dla HAPPYNET.

Ciekawym problem funkcyjnym jest także poniższy problem:

Przykład 1.9 [Problem ANOTHER HAMILTON CYCLE]

Wejście: graf nieskierowany $G$ i jego cykl Hamiltona $c$
Wyjście: cykl Hamiltona dla $G$ różny od $c$

Stwierdzenie czy istnieje cykl Hamiltona w grafie jest problemem NP-zupełnym. Ale czy wiedza o jednym cyklu pomaga nam w szukaniu kolejnego? Okazuje się, że ANOTHER HAMILTON CYCLE jest problem FNP-zupełnym. Interesujące jest jednak to, że gdy zawężymy klasę dostępnych grafów do grafów kubicznych, to sytuacja ulega specyficznej zmianie. Grafy kubiczne to grafy, w których każdy wierzchołek ma stopień 3. W takiej sytuacji okazuje się, że jeśli graf ma jeden cykl Hamiltona to musi mieć również inny:

Ćwiczenie 1.10

Udowodnij, że problem ANOTHER HAMILTON CYCLE dla grafów kubicznych należy do klasy TFNP.

Wskazówka

Pokaż, że w grafie kubicznym istnieje parzysta liczba ścieżek Hamiltona wykorzystujących krawędź z podanego cyklu.

Rozwiązanie

Load video

Local File

Local File might collect personal data.

Continue Dismiss

Problem ANOTHER HAMILTON CYCLE.

Weźmy cykl Hamiltona $c$. Oznaczmy dwa kolejne wierzchołki jako $1$ i $2$. Rozważmy teraz ścieżki Hamiltona nie zawierające krawędzi $(1,2)$ rozpoczynające się w $1$, które nazwiemy kandydatami. Dwie ścieżki kandydujące, które różnią się $|V|-2$ krawędziami uważamy za sąsiednie. Odpowiada to kolejności od (a) do (f) w animacji Problem ANOTHER HAMILTON CYCLE.

Ile sąsiadów może mieć ścieżka kandydująca? Załóżmy, że ścieżka prowadzi od $1$ do $x\ne 2$. Wtedy możemy otrzymać dwóch sąsiadów, poprzez przedłużenie ścieżki z $x$ na dwa możliwe sposoby (graf jest kubiczny) stosownie usuwając zbędną krawędź w dokładnie jeden sposób. Kandydat z animacji w części (b) ma właśnie dwóch sąsiadów otrzymanych w powyższy sposób.

Jeśli natomiast ścieżka prowadzi od $1$ do $2$ to ma tylko jednego sąsiada, gdyż krawędzi $(1,2)$ użyć nie wolno. W tym momencie łatwo zauważyć, że istnieje parzysta liczba ścieżek Hamiltona o końcach 1 i 2. Dzieje się tak dlatego, że każda taka ścieżka ma jednego sąsiada, a wszystkie inne po dwóch. Każda z takich ścieżek po dodaniu krawędzi $(1,2)$ zmienia się w cykl Hamiltona co kończy dowód, że drugi cykl Hamiltona zawsze istnieje.

Load video

Local File

Local File might collect personal data.

Continue Dismiss

Klasy problemów funkcyjnych.

Podobnie jak i w poprzednim przypadku, na podstawie dowodu nie umiemy skonstruować algorytmu wielomianowego dla ANOTHER HAMILTON CYCLE dla grafów kubicznych.

Animacja Klasy problemów funkcyjnych podsumowuje poznane klasy problemów funkcyjnych.

Złożoność zliczania

W drugiej części tego modułu zajmiemy się tematem podobnym do problemów funkcyjnych. Będziemy się zastanawiać nad złożonością obliczeniową obliczania liczby rozwiązań lub innymi słowy zliczaniem. Oto pierwszy przykład:

Przykład 2.1 [Problem $\mathrm{\#}\text{SAT}$]

Wejście: formuła logiczna $\varphi$ jak dla problemu SAT.
Wyjście: liczba różnych wartościowań spełniających $\varphi$.

Oczywiście rozwiązanie $\mathrm{\#}\text{SAT}$ daje nam rozwiązanie decyzyjnej wersji SAT. Inne przykłady "zliczających" wersji problemów NP-zupełnych to $\mathrm{\#}$HAMILTONIAN PATH, w którym pytamy o liczbę różnych cykli Hamiltona w grafie, czy $\mathrm{\#}$CLIQUE, w którym pytamy o liczbę różnych klik rozmiaru przynajmniej $K$. We wszystkich tych przypadkach nie mamy nadziei, aby wersje zliczające miały rozwiązania wielomianowe.

Istnieją problemy, dla których zliczanie liczby rozwiązań ma algorytm wielomianowy, np. liczba różnych drzew rozpinających w grafie lub liczba ścieżek Eulera. Pomimo tego, pewne problemy wskazują, że zliczanie liczby rozwiązań jest trudniejsze niż obliczanie samego rozwiązania. Nawet gdyby P=NP to nie wiemy jak rozwiązać $\mathrm{\#}\text{SAT}$ w czasie wielomianowym.

Skojarzenie w grafie dwudzielnym.

Na większą trudność wskazuje również przykład problemu MATCHING dotyczący idealnych skojarzeń w grafach dwudzielnych. W tym przypadku obliczenie rozwiązania (czyli wersja funkcyjna) jest wielomianowa, a mimo tego $\mathrm{\#}$MATCHING jest trudny i ciągle nie znamy rozwiązania wielomianowego dla niego.

Problem znajdowania idealnego skojarzenia w grafie dwudzielnym jest związany z wyznacznikami macierzy (animacja Skojarzenie w grafie dwudzielnym).

Oznaczmy przez $G=(A,B,E)$ graf dwudzielny pokazany w animacji. $A=\{a_1,a_2,a_3,a_4\}$, natomiast $B=\{b_1,b_2,b_3,b_4\}$. Macierz sąsiedztwa grafu $M^G$ również została przedstawiona w animacji. $M^G[i,j]$ równe jest 1, gdy krawędź od $a_i$ do $b_j$ istnieje lub 0 w przeciwnym wypadku. Wyznacznik $M^G$ wynosi:

det $M^G=\sum _{\pi }\sigma (\pi )\prod _{i=1}^n{M}^G[i,\pi (i)]$

gdzie sumowanie odbywa się po wszystkich permutacjach a tym samym skojarzeniach idealnych grafu $G$. Wyznacznik można policzyć szybko dzięki czynnikowi $\sigma (\pi )$ stanowiącego znak permutacji. Istnieje bardzo podobne wyrażenie zwane permanentem obliczane dla macierzy, które jest pozbawione tego czynnika:

perm $M^G=\sum _{\pi }\prod _{i=1}^n{M}^G[i,\pi (i)]$

Permanent macierzy to dokładnie liczba skojarzeń idealnych stosownego grafu dwudzielnego. Na wskutek tej odpowiedniości problem zliczania idealnych skojarzeń w grafie dwudzielnym nosi nazwę PERMANENT.

Istnieje także powiązanie pomiędzy skojarzeniami a pokryciem rozłącznymi cyklami grafu $G^{\prime }$ również przedstawionym w animacji. W grafie skierowanym $G^{\prime }$ o $n$ wierzchołkach krawędź od $i$ do $j$ występuje, gdy w grafie $G$ wierzchołek $a_i$ jest połączony z $b_j$. Graf $G^{\prime }$ może mieć pętle. Idealne skojarzenie dla $G$ odpowiada jednoznacznie pokryciu rozłącznymi cyklami grafu $G^{\prime }$. Dlatego też, wartość permanentu jest jednocześnie liczbą różnych pokryć cyklami dla $G^{\prime }$. Dla przedstawionego przykładu wszystkie te trzy wartości wynoszą 1.

Klasa $\mathrm{\#}\text{P}$ i twierdzenie Valianta

Badanie problemów polegających na zliczaniu przez Valianta w latach 70 przyniosło skutek w postaci zdefiniowania klasy $\mathrm{\#}\text{P}$ (czytamy "hasz P"). Jest on laureatem nagrody Knutha z roku 1997. Oznaczmy przez $R$ wielomianowo zrównoważoną i rozstrzygalną relację binarną na słowach. Problem zliczania związany z $R$ polega na obliczeniu dla danego $x$ liczby takich $y$, że $R(x,y)$ jest spełnione. Obliczony wynik musi być przedstawiony w postaci liczby binarnej. Klasa $\mathrm{\#}\text{P}$ składa się z wszystkich takich problemów związanych z relacjami $R$.

Jeśli $R$ jest relacją sprawdzającą, czy $y$ jest spełniającym wartościowaniem dla $x$ to otrzymujemy $\mathrm{\#}\text{SAT}$. Gdy natomiast $R$ jest zdefiniowana tak, że $R(x,y)$ zachodzi, gdy $y$ jest idealnym skojarzeniem dla grafu dwudzielnego $x$ to otrzymujemy problem PERMANENT. Podobnie dla $\mathrm{\#}$HAMILTONIAN PATH. Wszystko to przykłady problemów $\mathrm{\#}\text{P}$-zupełnych.

Aby mówić o zupełności musimy wprowadzić stosowną redukcję. Podobnie jak w przypadku problemów funkcyjnych redukcja pomiędzy problemami $A$ i $B$ składa się z dwóch funkcji $R$ i $S$ obliczanych w pamięci logarytmicznej. Jeśli $x$ jest instancją problemu $A$ to $R(x)$ jest instancją problemu $B$. Jeśli $N$ jest odpowiedzią dla $R(x)$ to $S(N)$ jest odpowiedzią dla $x$.

Okazuje się, że wygodnie jest posługiwać się mocniejszą redukcją oszczędną (ang. parsimonious wprowadzoną, co ciekawe przez Simona). Charakteryzuje się ona tym, że $S$ jest identycznością, tzn. $R$ przekształca instancje tak, że zachowuje liczbę rozwiązań.

Większość redukcji przeprowadzanych pomiędzy problemami decyzyjnymi z klasy NP jest oszczędna lub może zostać nimi zastąpiona. Poniższe ćwiczenie wprowadza pierwszy problem zupełny dla wprowadzonej klasy:

Ćwiczenie 2.2

Udowodnij, że problem $\mathrm{\#}\text{SAT}$ jest $\mathrm{\#}\text{P}$-zupełny.

Wskazówka

Wzoruj się na twierdzeniu Cooka.

Rozwiązanie

Musimy pokazać, że każdy problem $L$ z klasy $\mathrm{\#}\text{P}$ redukuje się do $\mathrm{\#}\text{SAT}$. W tym celu przeprowadzamy dowód analogiczny do twierdzenia Cooka. Dla języka $L$ istnieje stosowna wielomianowo zrównoważona i rozstrzygalna relacja $R_L$. Twierdzenie Cooka dostarcza nam funkcję $R$ na słowach, obliczalną w pamięci logarytmicznej, która wprowadza odpowiedniość pomiędzy obliczeniem akceptującym $x\in L$ przez maszynę niedeterministyczną $M$ a wartościowaniem spełniającym formułę $R(x)$. Nasza redukcja jest oszczędna, bowiem każde obliczenie akceptujące $x\in L$ przez $M$ odpowiada $y$ takiemu, że $R(x,y)$ i jednocześnie spełniającemu wartościowaniu formuły $R(x)$. W ten sposób $R$ jest poszukiwaną przez nas funkcją redukującą wersję zliczającą $L$ do $\mathrm{\#}\text{SAT}$.

Jednak problem $\mathrm{\#}\text{P}$-zupełny, który jest najbardziej interesujący, to opisany już PERMANENT. Mimo wielomianowości problemu MATCHING okazuje się on tak trudny jak cała wprowadzona klasa:

Twierdzenie 2.3 [twierdzenie Valianta]

Problem PERMANENT jest $\mathrm{\#}\text{P}$-zupełny.

Load video

Local File

Local File might collect personal data.

Continue Dismiss

Dowód twierdzenia Valianta (1).

Load video

Local File

Local File might collect personal data.

Continue Dismiss

Dowód twierdzenia Valianta (2).

Dowód

Zasadnicza część dowodu to redukcja $\mathrm{\#}\text{SAT}$ do problemu PERMANENT MOD N. Jednak gdy potrafimy obliczyć PERMANENT dokładnie, to potrafimy także obliczyć jego resztę modulo $N$, więc ostatecznie możemy zredukować $\mathrm{\#}\text{SAT}$ do PERMANENT, co dowodzi $\mathrm{\#}\text{P}$-zupełności tego ostatniego.

Naszą redukcję oprzemy na równoważności pomiędzy permanentem macierzy a liczbą pokryć rozłącznymi cyklami stowarzyszonego grafu $G$, omówionej przy okazji definicji permanentu.

Redukcję rozpoczniemy od formuły 3SAT i będziemy konstruować nasz graf $G$. Dla każdej zmiennej z formuły $\varphi$ będzie on zawierał element wyboru decydujący o wyborze wartościowania dla zmiennej, przedstawiony w animacji Dowód twierdzenia Valianta (1) w części (a).

Graf przedstawiony w animacji w części (a) posiada dokładnie dwa możliwe pokrycia cyklami. Każde z nich zawiera dokładnie jedną z krawędzi bocznych i krawędź środkową. Naszą interpretacją będzie stosowne wartościowanie tej zmiennej w formule $\varphi$.

Dla każdej z klauzul formuły $\varphi$ do grafu $G$ wstawiamy element przedstawiony w animacji w części (b). Łatwo zauważyć, że dla tego grafu:

• nie istnieje pokrycie cyklami zawierające 3 zewnętrzne krawędzie,
• każdy inny podzbiór (w tym pusty) zewnętrznych krawędzi jest osiągany przez dokładnie jedno pokrycie cyklami.

W ten sposób możemy symulować 7 poprawnych (spełniających) wartościowań klauzuli o trzech zmiennych i 1 niepoprawne. Teraz musimy tylko połączyć rozłączne jak na razie elementy skojarzone ze zmiennymi i klauzulami. Stosowny element musi działać jak xor na odpowiedniej krawędzi z podgrafu skojarzonego ze zmienną (w zależności od obecności negacji w klauzuli przy zmiennej) i jednej z trzech krawędzi na obwodzie podgrafu skojarzonego z klauzulą.

To ten element jest najbardziej enigmatyczny w całym dowodzie, gdyż pamiętamy, że obliczanie pojedynczego skojarzenia idealnego (a tym samym rozłącznego pokrycia cyklami) może być rozwiązane w czasie wielomianowym, natomiast wartościowanie formuły 3SAT jest NP-zupełne!

Element xor został przedstawiony w animacji w formie macierzy w części (a), w formie grafu w części (b) i w formie skrótowej w części (c). Wierzchołek $g$ w części (b) odpowiada reszcie grafu i będzie służył do dowodu. Element w kształcie diamentu w części (c) odpowiada grafowi z części (b) bez wierzchołka $g$ (animacja Dowód twierdzenia Valianta (2)).

Na chwilę rozszerzyliśmy problem PERMANENT na macierze o wartościach innych niż 0-1. Jest to problem równoważny obliczaniu uogólnionego pokrycia cyklami, w którym waga pokrycia to iloczyn wag tworzących pokrycie i poszukujemy nie liczby pokryć, a sumy wag wszystkich różnych pokryć rozłącznych.

Oto podsumowanie prostych własności, które będą nam potrzebne w dalszej części dowodu dotyczące wagi pokryć cyklami grafu z części (b). Można je sprawdzić również obliczając permanent stosownej macierzy:

• suma wag pokryć zawierających krawędzie $(d,g)$ i $(g,a)$ wynosi 4,
• suma wag pokryć zawierających krawędzie $(a,g)$ i $(g,d)$ wynosi 4,
• suma wag pokryć zawierających pętlę $g$ wynosi 0,
• suma wag pokryć zawierających krawędzie $(d,g)$ i $(g,d)$ wynosi 0,
• suma wag pokryć zawierających krawędzie $(g,a)$ i $(a,g)$ wynosi 0.

Na podstawie tych własności możemy stwierdzić, że element w kształcie diamentu zachowuje się jak xor jeśli chodzi o sumę wag pokryć. Załóżmy, że krawędzie które chcemy połączyć takim elementem to $(1,1^{\prime })$ oraz $(2,2^{\prime })$. Otóż jeśli krawędź $(1,1^{\prime })$ należy do pokrycia, a $(2,2^{\prime })$ nie, to stosowne pokrycie jest przemnażane przez 4. Podobnie dzieje się dla dualnej sytuacji. Gdy natomiast żadna z krawędzi nie należy do pokrycia lub należą obie lub wystąpi jeszcze inna sytuacja to stosowne pokrycie wnosi wagę 0.

Teraz dokonujemy opisanych połączeń przy pomocy elementu xor. Zauważmy, że każde spełniające wartościowanie formuły $\varphi$ odpowiada takiemu pokryciu cyklami, w którym w każdym elemencie xor jest wnoszona waga 4 do iloczynu, czyli każde spełniające wartościowanie formuły $\varphi$ odpowiada wadze $4^m$ dla pokrycia cyklami, gdzie $m$ to suma liczby wystąpień wszystkich literałów (czyli liczba elementów xor). Jeśli zatem policzymy permanent, czyli wagę wszystkich pokryć cyklami, to otrzymamy wartość $4^{m}s$, gdzie $s$ to liczba różnych wartościowań spełniających formułę $\varphi$.

Teraz musimy sobie poradzić z wprowadzonymi wagami różnymi od 0 i 1. Na poniższej animacji (Dowód twierdzenia Valianta (3)) w części (a) przedstawiamy element zastępujący wagę 2, a w części (b) wagę 3.

Jest proste do sprawdzenia, że każde pokrycie, które miało zastąpioną krawędź, będzie teraz wnosić wagę 2 (analogicznie 3) ze względu na dwa (analogicznie trzy) możliwe pokrycia cyklami przedstawionych fragmentów. W części (c) pokazano jak uzyskać wagę $2^n$ nie używając wykładniczej wielkości grafu.

Pozostaje nam pozbycie się wag $-1$ i w tym celu odwołujemy się do problemu PERMANENT MOD N wspomnianym na początku dowodu. Gdy bowiem obliczamy PERMANENT MOD N z wagami $-1$, to odpowiada to obliczeniu PERMANENT z wagą $N-1$. Ustalamy zatem $N=2^n+1$ gdzie $n$ jest odpowiednio dużą liczbą całkowitą, która jest większa od maksymalnej wartości permanentu pozostałej części grafu (np. $n=8m$). Zastępujemy $-1$ przez $2^n$ i liczymy wartość PERMANENT a następnie bierzemy wynik modulo $N$. Jest on równy $4^{m}s$ stąd obliczamy liczbę wszystkich wartościowań spełniających formułę $\varphi$.

Load video

Local File

Local File might collect personal data.

Continue Dismiss

Dowód twierdzenia Valianta (3).

Oczywiście każdy problem z klasy $\mathrm{\#}\text{P}$ może zostać rozwiązany w pamięci wielomianowej, poprzez prosty algorytm zliczający (oczywiście wykładniczy). Zliczanie nie jest zatem silniejsze niż klasa PSPACE.

Klasa $\oplus \text{P}$

Ciekawą klasą powiązaną z tematem zliczania jest klasa $\oplus \text{P}$ (czytamy "parzystość P"). Odpowiada ona obliczaniu ostatniego bitu wyniku dla problemów z klasy $\mathrm{\#}\text{P}$. Przeanalizujmy poniższe problemy:

Przykład 2.4 [Problem $\oplus \text{SAT}$]

Wejście: formuła logiczna $\varphi$ jak dla problemu SAT.
Wyjście: czy liczba różnych wartościowań spełniających $\varphi$ jest nieparzysta?

Przykład 2.5 [Problem $\oplus \text{HAMILTON CYCLE}$]

Wejście: graf nieskierowany $G$
Wyjście: czy liczba różnych cykli Hamiltona dla $G$ jest nieparzysta?

Możemy zdefiniować ogólnie klasę $\oplus \text{P}$ jako ogół tych języków $L$ dla których istnieje maszyna niedeterministyczna działająca w czasie wielomianowym, dla której $x\in L$ wtedy i tylko wtedy, gdy liczba ścieżek akceptujących $x$ przez $M$ jest nieparzysta. W języku relacji, powiemy, że $L$ należy do $\oplus \text{P}$, gdy istnieje wielomianowo zrównoważona i rozstrzygalna relacja $R_L$ taka, że $x\in L$ wtedy i tylko wtedy, gdy ilość $y$ takich, że $R_L(x,y)$ jest nieparzysta.

Zarówno $\oplus \text{SAT}$ jak i $\oplus$HAMILTON CYCLE okazują się problemami $\oplus \text{P}$-zupełnymi (zupełność definiujemy przy pomocy redukcji oszczędnych w naturalny sposób). Z łatwością można stwierdzić, że należą do klasy $\oplus \text{P}$, natomiast redukcje oszczędne omawiane przy okazji wersji zliczających tych problemów są wystarczające.

Moc klasy $\oplus \text{P}$ wydaje się być słabsza ze względu na fakt, iż $\mathrm{\#}$MATCHING, czyli PERMANENT MOD 2 jest problemem o złożoności wielomianowej. Dzieje się tak dlatego, iż w tym wypadku obliczanie wyznacznika i permanentu daje ten sam wynik.

Ćwiczenia dodatkowe

Ćwiczenie 3.1

Udowodnij, że FSAT jest FNP-zupełny.

Wskazówka

Skorzystaj z faktu, że SAT jest problemem NP-zupełnym.

Rozwiązanie

Dla porządku należy najpierw zauważyć, że FSAT należy do FNP. Następnie chcemy pokazać, że każdy problem z klasy FNP redukuje się do FSAT poprzez wprowadzoną redukcję pomiędzy problemami funkcyjnymi. Weźmy zatem dowolny problem $FL$ należący do FNP i skojarzoną z nim wielomianowo zrównoważoną i rozstrzygalną relację $R_L$. Według konwencji poprzez $L$ oznaczamy problem z klasy NP skojarzony z $R_L$.

Potrzebujemy znaleźć funkcje $R$ i $S$ obliczalne w pamięci logarytmicznej, spełniające warunki określone w definicji redukcji. Wiemy jednak, że SAT jest problemem zupełnym dla klasy NP. Zatem istnieje redukcja wielomianowa z problemu $L$ do SAT. Teraz należy powtórzyć rozumowanie przeprowadzone w twierdzeniu Cooka dowodzące istnienia takiej redukcji. Problem $L$ jest akceptowany przez niedeterministyczną maszynę Turinga $M$ działającą w czasie wielomianowym, która dla podanego $x$ zgaduje $y$ takie, że $R_L(x,y)$. W dowodzie twierdzenia Cooka konstruujemy potrzebną nam funkcję $R$ na słowach, dla której zachodzi $x\in L\iff R(x)\in SAT$. Jest ona obliczana w pamięci logarytmicznej. To pierwsza z potrzebnych nam funkcji. Dodatkowo, w dowodzie twierdzenia Cooka pokazujemy, iż na podstawie poprawnego wartościowania dla formuły kodowanej przez $R(x)$ możemy odtworzyć obliczenie akceptujące $x$ dla maszyny $M$. Tym samym otrzymujemy funkcję $S$ obliczaną w pamięci logarytmicznej.

Ćwiczenie 3.2

Udowodnij, że klasa $\oplus \text{P}$ jest zamknięta na dopełnienie.

Wskazówka

Przeanalizuj dopełnienie problemu $\oplus \text{SAT}$.

Rozwiązanie

Dopełnienie problemu $\oplus \text{SAT}$ to problem polegający na stwierdzeniu, czy liczba spełniających wartościowań jest nieparzysta. Zredukujmy ten problem do $\oplus \text{SAT}$ w prosty sposób zmieniając liczbę spełniających wartościowań o 1. Dodajemy nową zmienną $z$ oraz klauzule postaci $z\vee \mathrm{\neg }{x}_i$ gdzie $x_i$ przebiega kolejne zmienne występujące w formule. Dowolne wartościowanie spełniające poprzednią formułę spełnia również formułę po modyfikacji, gdy przyjmiemy $z=0$. Gdy natomiast ustawimy $z=1$ to otrzymamy nowe wartościowanie, co kończy redukcję dopełnienia $\oplus \text{SAT}$ do $\oplus \text{SAT}$. Teraz wystarczy zauważyć, że $\oplus \text{SAT}$ jest zupełny dla $\oplus \text{P}$, i dzięki opisanej redukcji również dla co-$\oplus \text{P}$. Ponieważ obie klasy są zamknięte na redukcje, to powoduje, że $\oplus \text{P}$=co-$\oplus \text{P}$, czyli, że $\oplus \text{P}$ jest zamknięta na dopełnienie.