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

{{{3}}}

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 [Problem TSP:]

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

Ćwiczenie

{{{3}}}

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 Uzupelnic EX:FSAT|).

Twierdzenie [Uzupelnij]

{{{3}}}

Dowód [Uzupelnij]

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 [Uzupelnij]

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:

Przykład [Uzupelnij]

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 wierzchołek 1 jest nieszczęśliwy, a 4 jest szczęśliwy:

{1cm}

[width=10cm]{ZO-12-1-rys.jpg}
Problem HAPPYNET

{1cm}

Ł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

{{{3}}}

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} {istnieje wierzchołek nieszczęśliwy $v$} {S(v):=-S(v)}

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 [Uzupelnij]

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

{{{3}}}

Wskazówka

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

Rozwiązanie

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) na poniższym rysunku:

{1cm}

[width=10cm]{ZO-12-2-rys.jpg}
Problem ANOTHER HAMILTON CYCLE

{1cm}

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 rysunku (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.

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

Poniższy rysunek podsumowuje poznane klasy problemów funkcyjnych:

{1cm}

[width=10cm]{ZO-12-3-rys.jpg}
Klasy problemów funkcyjnych

{1cm}

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 [Uzupelnij]

Problem Parser nie mógł rozpoznać (błąd składni): {\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ć (błąd składni): {\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ć (błąd składni): {\displaystyle \\textsc{SAT}} } w czasie wielomianowym.

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:

{1cm}

[width=10cm]{ZO-12-4-rys.jpg}
Skojarzenie w grafie dwudzielnym

{1cm}

Oznaczmy przez $G=(A,B,E)$ graf dwudzielny pokazany na rysunku. $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 na rysunku. $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 na rysunku. 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ć (błąd składni): {\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ć (błąd składni): {\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ć (błąd składni): {\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ć (błąd składni): {\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ć (błąd składni): {\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

{{{3}}}

Wskazówka

Wzoruj się na twierdzeniu Cooka.

Rozwiązanie

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

Jednak problem Parser nie mógł rozpoznać (błąd składni): {\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 [Uzupelnij]

(twierdzenie Valianta): Problem PERMANENT jest Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\textsc{P}} -zupełny.

Dowód [Uzupelnij]

{{{3}}}

Oczywiście każdy problem z klasy {Parser nie mógł rozpoznać (błąd składni): {\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ć (błąd składni): {\displaystyle \\textsc{P}} . Przeanalizujmy poniższe problemy:

Przykład [Uzupelnij]

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 [Uzupelnij]

Problem $\oplus$ 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.