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:

<flash>file=ZO-12-1.swf|width=300|height=300</flash>

<div.thumbcaption>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

<flashwrap>file=ZO-12-2.swf|size=small</flashwrap>

<div.thumbcaption>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.

<flashwrap>file=ZO-12-3.swf|size=small</flashwrap>

<div.thumbcaption>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 Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \#\textsc{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 Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \#\textsc{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ć Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \#\textsc{SAT}} w czasie wielomianowym.

<flashwrap>file=ZO-12-4.swf|size=small</flashwrap>

<div.thumbcaption>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 Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \#\textsc{P}} i twierdzenie Valianta

Badanie problemów polegających na zliczaniu przez Valianta w latach 70 przyniosło skutek w postaci zdefiniowania klasy Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \#\textsc{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 Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \#\textsc{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 Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \#\textsc{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 Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \#\textsc{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 Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \#\textsc{SAT}} jest Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \#\textsc{P}} -zupełny.

Wskazówka

Wzoruj się na twierdzeniu Cooka.

Rozwiązanie

Musimy pokazać, że każdy problem $L$ z klasy Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \#\textsc{P}} redukuje się do Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \#\textsc{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 Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \#\textsc{SAT}} .

Jednak problem Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \#\textsc{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 Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \#\textsc{P}} -zupełny.

<flashwrap>file=ZO-12-5.swf|size=small</flashwrap>

<div.thumbcaption>Dowód twierdzenia Valianta (1).

<flashwrap>file=ZO-12-6.swf|size=small</flashwrap>

<div.thumbcaption>Dowód twierdzenia Valianta (2).

Dowód

{{{3}}}

Oczywiście każdy problem z klasy Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \#\textsc{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 Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \oplus\textsc{P}}

Ciekawą klasą powiązaną z tematem zliczania jest klasa Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \oplus\textsc{P}} (czytamy "parzystość P"). Odpowiada ona obliczaniu ostatniego bitu wyniku dla problemów z klasy Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \#\textsc{P}} . Przeanalizujmy poniższe problemy:

Przykład 2.4 [Problem Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \oplus\textsc{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 Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \oplus\textsc{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ę Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \oplus\textsc{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 Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \oplus\textsc{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 Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \oplus\textsc{SAT}} jak i $\oplus$HAMILTON CYCLE okazują się problemami Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \oplus\textsc{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 Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \oplus\textsc{P}} , natomiast redukcje oszczędne omawiane przy okazji wersji zliczających tych problemów są wystarczające.

Moc klasy Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \oplus\textsc{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 Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \oplus\textsc{P}} jest zamknięta na dopełnienie.

Wskazówka

Przeanalizuj dopełnienie problemu Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \oplus\textsc{SAT}} .

Rozwiązanie

Dopełnienie problemu Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \oplus\textsc{SAT}} to problem polegający na stwierdzeniu, czy liczba spełniających wartościowań jest nieparzysta. Zredukujmy ten problem do Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \oplus\textsc{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 Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \oplus\textsc{SAT}} do Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \oplus\textsc{SAT}} . Teraz wystarczy zauważyć, że Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \oplus\textsc{SAT}} jest zupełny dla Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \oplus\textsc{P}} , i dzięki opisanej redukcji również dla co-Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \oplus\textsc{P}} . Ponieważ obie klasy są zamknięte na redukcje, to powoduje, że Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \oplus\textsc{P}} =co-Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \oplus\textsc{P}} , czyli, że Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \oplus\textsc{P}} jest zamknięta na dopełnienie.