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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 jak dla problemu SAT.
Wyjście: wartościowanie spełniające 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
Rozwiązanie

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 .
Wyjście: optymalna trasa komiwojażera dla lub "NIE", gdy nie istnieje.

Ćwiczenie 1.4

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

Wskazówka
Rozwiązanie

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 należy do NP to istnieje relacja , taka że wtedy i tylko wtedy gdy istnieje taki, że . Poprzez oznaczamy problem funkcyjny polegający na obliczeniu na podstawie wartości takiej, że 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 FPFNP 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 redukuje się do jeśli istnieją funkcje na słowach oraz obliczalne w pamięci logarytmicznej takie, że jeśli jest instancją dla problemu to jest instancją dla problemu . Oraz jeśli jest dopuszczalnym rozwiązaniem dla to jest dopuszczalnym rozwiązaniem dla . 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 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

.

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ę.

End of proof.gif

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 (relacja występująca w definicji problemu funkcyjnego) spełnia warunek, iż dla każdego istnieje przynajmniej jedno takie, że .

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
Wyjście: rozkład 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 z wagami całkowitymi
Wyjście: wartościowanie takie, że każdy wierzchołek jest szczęśliwy, tzn.:

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
Rozwiązanie

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 i jego cykl Hamiltona
Wyjście: cykl Hamiltona dla różny od

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
Rozwiązanie

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 ]

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

Oczywiście rozwiązanie daje nam rozwiązanie decyzyjnej wersji SAT. Inne przykłady "zliczających" wersji problemów NP-zupełnych to HAMILTONIAN PATH, w którym pytamy o liczbę różnych cykli Hamiltona w grafie, czy CLIQUE, w którym pytamy o liczbę różnych klik rozmiaru przynajmniej . 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ć 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 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 graf dwudzielny pokazany w animacji. , natomiast . Macierz sąsiedztwa grafu również została przedstawiona w animacji. równe jest 1, gdy krawędź od do istnieje lub 0 w przeciwnym wypadku. Wyznacznik wynosi:


det


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


perm


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 również przedstawionym w animacji. W grafie skierowanym o wierzchołkach krawędź od do występuje, gdy w grafie wierzchołek jest połączony z . Graf może mieć pętle. Idealne skojarzenie dla odpowiada jednoznacznie pokryciu rozłącznymi cyklami grafu . Dlatego też, wartość permanentu jest jednocześnie liczbą różnych pokryć cyklami dla . Dla przedstawionego przykładu wszystkie te trzy wartości wynoszą 1.

Klasa i twierdzenie Valianta

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

Jeśli jest relacją sprawdzającą, czy jest spełniającym wartościowaniem dla to otrzymujemy . Gdy natomiast jest zdefiniowana tak, że zachodzi, gdy jest idealnym skojarzeniem dla grafu dwudzielnego to otrzymujemy problem PERMANENT. Podobnie dla HAMILTONIAN PATH. Wszystko to przykłady problemów -zupełnych.

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

Okazuje się, że wygodnie jest posługiwać się mocniejszą redukcją oszczędną (ang. parsimonious wprowadzoną, co ciekawe przez Simona). Charakteryzuje się ona tym, że jest identycznością, tzn. 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 jest -zupełny.

Wskazówka
Rozwiązanie

Jednak problem -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 -zupełny.

Dowód

Zasadnicza część dowodu to redukcja do problemu PERMANENT MOD N. Jednak gdy potrafimy obliczyć PERMANENT dokładnie, to potrafimy także obliczyć jego resztę modulo , więc ostatecznie możemy zredukować do PERMANENT, co dowodzi -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 , omówionej przy okazji definicji permanentu.

Redukcję rozpoczniemy od formuły 3SAT i będziemy konstruować nasz graf . Dla każdej zmiennej z formuły 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 .

Dla każdej z klauzul formuły do grafu 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 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 (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 i wynosi 4,
  • suma wag pokryć zawierających krawędzie i wynosi 4,
  • suma wag pokryć zawierających pętlę wynosi 0,
  • suma wag pokryć zawierających krawędzie i wynosi 0,
  • suma wag pokryć zawierających krawędzie i 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 oraz . Otóż jeśli krawędź należy do pokrycia, a 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 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 odpowiada wadze dla pokrycia cyklami, gdzie 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ść , gdzie to liczba różnych wartościowań spełniających formułę .

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ę nie używając wykładniczej wielkości grafu.

Pozostaje nam pozbycie się wag 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 , to odpowiada to obliczeniu PERMANENT z wagą . Ustalamy zatem gdzie jest odpowiednio dużą liczbą całkowitą, która jest większa od maksymalnej wartości permanentu pozostałej części grafu (np. ). Zastępujemy przez i liczymy wartość PERMANENT a następnie bierzemy wynik modulo . Jest on równy stąd obliczamy liczbę wszystkich wartościowań spełniających formułę .

End of proof.gif

Oczywiście każdy problem z klasy 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

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

Przykład 2.4 [Problem ]

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

Przykład 2.5 [Problem ]

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

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

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

Moc klasy wydaje się być słabsza ze względu na fakt, iż 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
Rozwiązanie

Ćwiczenie 3.2

Udowodnij, że klasa jest zamknięta na dopełnienie.

Wskazówka
Rozwiązanie

Testy końcowe