Złożoność obliczeniowa/Wykład 9: Twierdzenie PCP i nieaproksymowalność

From Studia Informatyczne

Spis treści

Wprowadzenie

Dotychczasowa analiza \displaystyle \cc{NP}-zupełnych problemów optymalizacyjnych pokazała dużą rozpiętość, jeżeli chodzi o możliwości ich aproksymacji. Z jednej strony poznaliśmy problemy, jak problem plecakowy, które można aproksymować z dowolnie dobrą dokładnością. Z drugiej strony spotkaliśmy problemy, jak problem komiwojażera, gdzie w ogólnym przypadku niemożliwa jest żadna aproksymacja.

Ciekawą klasą leżącą gdzieś pomiędzy tymi dwoma skrajnościami jest klasa \displaystyle \cc{MAXSNP}, gdzie problemy mają algorytmy ze stałą aproksymacji, ale nie wiemy jeszcze nic o schematach dla problemów z tej klasy. Dla wielu konkretnych problemów takie schematy istnieją, ale szczególnie interesujący byłby schemat, dla któregoś z problemów \displaystyle \cc{MAXSNP}-zupełnych. Odkrycie takiego schematu pociągałoby za sobą istnienie schematów dla wszystkich problemów z klasy \displaystyle \cc{MAXSNP}.

Okazuje się, że pytanie o taki schemat jest równoważne pytaniu \displaystyle \cc{P}  =? \cc{NP}. Jeżeli \displaystyle \cc{P} \neq \cc{NP}, to nie może istnieć schemat aproksymacji dla żadnego problemu \displaystyle \cc{MAXSNP}-zupełnego. Sercem dowodu tego faktu jest twierdzenie \displaystyle \cc{PCP}, które przedstawimy. Twierdzenie to stało się istotnym kamieniem milowym w badaniach nad aproksymacją optymalizacyjnych problemów \displaystyle \cc{NP}-zupełnych. Pozwoliło nie tylko rozwiązać pytania dotyczące klasy \displaystyle \cc{MAXSNP}, ale także wykazać wiele ograniczeń na możliwości aproksymowania rozwiązań różnych konkretnych problemów.

Po przedstawieniu tego fascynującego twierdzenia pokażemy różne, niestety negatywne wnioski, jakie z niego wynikają dla teorii algorytmów aproksymacyjnych.

Weryfikatory

Żeby móc w ogóle wyrazić twierdzenie potrzebujemy całkiem nowego pojęcia, które teraz wprowadzimy.

Przypomnijmy definicję klasy \displaystyle \cc{NP} z użyciem świadka. Klasa \displaystyle NP to języki \displaystyle L, które mogą być przedstawione w postaci:

\displaystyle L = \{ \defset{x} : {\exists_y (\braq{x,y}) \in R} \} ,

gdzie relacja \displaystyle R jest wielomianowo zrównoważona.

Ta definicja jest dość sztywna i trudno za jej pomocą uchwycić jakieś własności problemów optymalizacyjnych. Dlatego wprowadza się definicję systemu \displaystyle \cc{PCP}, co od angielskiego probabilistically checkable proof oznacza dowód weryfikowalny propabilistycznie.

W definicji tej pozwala się maszynie rozpoznającej język na korzystanie z bitów losowych (dostępnych na osobnej taśmie), ale wymaga się ograniczenia w korzystaniu z dostępnego świadka.

Definicja 2.1

Weryfikatorem nazywamy deterministyczną maszynę Turinga, która oprócz taśmy roboczej ma dostęp do taśmy z ciągiem bitów losowych oraz taśmy, na której jest zapisany świadek. Obliczenie weryfikatora musi zawsze się kończyć i akceptować lub odrzucać słowo wejściowe. Weryfikator jest ograniczony przez funkcje naturalne \displaystyle p i \displaystyle q, jeżeli dla słowa wejściowego \displaystyle x odczytuje co najwyżej \displaystyle \mathcal{O}{ p(|\size{x}|) } bitów losowych i co najwyżej \displaystyle \mathcal{O}{ q(|\size{x}|) } bitów świadka. Będziemy o nim wtedy mówić, że jest \displaystyle (\braq{p,q})-ograniczonym weryfikatorem.

Najciekawszymi ograniczeniami są \displaystyle \log n na liczbę bitów losowych i \displaystyle 1 na liczbę bitów świadka. Języki rozpoznawane w czasie wielomianowym przez takie weryfikatory tworzą klasę \displaystyle  \cc{PCP}(\log n,1).



Rys.9.1. Weryfikator.

Definicja 2.2

Język \displaystyle L należy do \displaystyle  \cc{PCP}(\log n, 1), jeżeli istnieje weryfikator \displaystyle V oraz stałe \displaystyle c i \displaystyle d takie, że dla wejścia \displaystyle x \displaystyle V działa w czasie wielomianowym od \displaystyle |\size{x}| bez względu na odczytane bity losowe i świadka. Podczas działania odczytuje co najwyżej \displaystyle c\log|\size{x}| bitów losowych i co najwyżej \displaystyle d bitów świadka.

  • Jeżeli słowo \displaystyle x \in L, to istnieje taki świadek \displaystyle y, że \displaystyle V akceptuje z prawdopodobieństwem \displaystyle 1.
  • Jeżeli słowo \displaystyle x \notin L, to dla każdego świadka \displaystyle y \displaystyle V odrzuca z prawdopodobieństwem większym od \displaystyle \frac{1}{2}.

Klasy \displaystyle  \cc{PCP}(p,q) definiuje się analogicznie. Charakteryzację klasy \displaystyle \cc{NP}, którą przypomnieliśmy na samym początku, możemy teraz wyrazić używając nowej terminologii równaniem:

\displaystyle \cc{NP} =  \cc{PCP}(0, \textnormal{poly}(n) )\textnormal{.}

Możemy teraz sformułować długo zapowiadane twierdzenie \displaystyle \cc{PCP}:

Twierdzenie 2.3

\displaystyle \cc{NP} =  \cc{PCP}(\log n, 1)

Dowód

Dowód jednej części tego twierdzenia jest prosty. Żeby pokazać zawieranie \displaystyle  \cc{PCP}(\log n,1)  \subseteq NP, wystarczy przeanalizować następującą niedeterministyczną maszynę Turinga:

[Niedeterministyczny symulator weryfikatora]
1. Wybierz niedeterministycznie świadka \displaystyle y o rozmiarze wielomianowym.
2. Dla każdego ciągu bitów \displaystyle b długości \displaystyle c \log n zasymuluj działanie weryfikatora na słowie wejściowym przy świadku \displaystyle y i ciągu bitów losowych \displaystyle b.
3. Zaakceptuj słowo, jeżeli wszystkie symulacje weryfikatora zakończyły się akceptująco.

Dowód drugiego zawierania używa bardzo zaawansowanych technik i niestety zdecydowanie wykracza poza zakres tego kursu.

image:End_of_proof.gif

Ćwiczenie 2.5

Pseudoweryfikator dla SAT.

Pokaż \displaystyle (\braq{\log n, 1})-ograniczony weryfikator dla języka \displaystyle 3SAT, który akceptuje niespełnialne formuły z prawdopodobieństwem nie większym niż \displaystyle 1 - \frac{1}{m}, gdzie \displaystyle m jest liczbą klauzul.

Wskazówka

Użyj bitów losowych do sprawdzenia losowej klauzuli.

Rozwiązanie

Użyjemy \displaystyle \log m bitów losowych do wyznaczenia klauzuli, której wartościowanie sprawdzimy. Bity świadka potraktujemy jako wartościowanie, które powinno spełniać wszystkie klauzule. Po wyznaczeniu numeru klauzuli potrzebujemy dostępu do co najwyżej \displaystyle 3 bitów świadka, aby poznać wartościowanie pojedynczej klauzuli \displaystyle 3SAT. Weryfikator akceptuje formułę, jeżeli klauzula jest spełniona.

Jeżeli świadek opisuje wartościowanie spełniające wszystkie klauzule, to skonstruowany weryfikator przy takim świadku zawsze zaakceptuje formułę spełnialną. Dla formuły niespełnialnej każdy świadek pozostawia którąś z klauzul niespełnioną, więc prawdopodobieństwo akceptacji jest nie większe niż \displaystyle 1 - \frac{1}{m}.

Skonstruowanemu weryfikatorowi oczywiście daleko do weryfikatora klasy \displaystyle  \cc{PCP}(\log n,1), którego istnienie dla problemu \displaystyle 3SAT gwarantuje twierdzenie \displaystyle \cc{PCP}. Obniżenie progu błędnej akceptacji z \displaystyle 1 - \frac{1}{m} do \displaystyle \frac{1}{2} jest naprawdę nie lada wyczynem.

Ćwiczenie 2.6

Charakteryzacje \displaystyle \cc{P} i \displaystyle \cc{NP} poprzez \displaystyle \cc{PCP}.

Uzasadnij poniższe równości:

  • \displaystyle \cc{P} =  \cc{PCP}(0,0)  =  \cc{PCP}(\log n, 0)  =  \cc{PCP}(0,\log n),
  • \displaystyle \cc{NP} =  \cc{PCP}(\log n, 1)  =  \cc{PCP}(\log n, \textnormal{poly}(n) ).

Wskazówka

Użyj przeglądania wyczerpującego, aby uzasadnić równości z punktu pierwszego. Przyjrzyj się raz jeszcze dowodowi, że \displaystyle  \cc{PCP}(\log n, 1)  \subseteq NP.

Rozwiązanie

Równość \displaystyle P =  \cc{PCP}(0,0) jest oczywista, gdyż weryfikator bez dostępu do bitów losowych i świadka zachowuje się jak zwykła maszyna deterministyczna. Zawierania \displaystyle  \cc{PCP}(\log n,0)  \supseteq  \cc{PCP}(0,0)  \subseteq  \cc{PCP}(0,\log n) też nie wymagają komentarza. Działanie weryfikatora z \displaystyle \mathcal{O}{\log n} bitami losowymi można zasymulować na deterministycznej maszynie, przeglądając wszystkie ciągi odpowiedniej długości. Czas będzie wykładniczy od \displaystyle \mathcal{O}{\log n}, czyli wielomianowy od rozmiaru wejścia. Akceptacji należy dokonać, jeżeli wszystkie ciągi losowe prowadzą do akceptacji.

Zasymulowania weryfikatora z dostępem do \displaystyle \mathcal{O}{\log n} bitów świadka też można dokonać w czasie wykładniczym od \displaystyle \mathcal{O}{\log n} na maszynie deterministycznej. Chociaż świadek może mieć długość wielomianową, to nie trzeba ustalać wartości wszystkich jego bitów jednocześnie. Ponieważ odczyty są deterministyczne (mogą co prawda zależeć od poprzednich odczytów, ale nie ma to większego znaczenia), to dla symulacji nie jest istotne, jakie były wartości nieodczytanych bitów. Słowo należy zaakceptować, jeżeli którykolwiek ze sprawdzonych świadków zapewnia akceptację.

Równość \displaystyle \cc{NP} =  \cc{PCP}(\log n,1) jest treścią twierdzenia \displaystyle \cc{PCP}. Natomiast jeżeli przyjrzymy się bliżej przedstawionemu dowodowi, że \displaystyle  \cc{PCP}(\log n, 1)  \subseteq \cc{NP}, to zobaczymy, że to samo rozumowanie jest słuszne dla weryfikatora \displaystyle (\braq{\log n, \textnormal{poly}(n) })-ograniczonego.

Twierdzenie \displaystyle \cc{PCP} a problem MAX\displaystyle 3SAT

Wprowadzona terminologia \displaystyle \cc{PCP} miała pozwolić na analizę złożoności problemów optymalizacyjnych. Przedstawimy teraz twierdzenie równoważne twierdzeniu \displaystyle \cc{PCP}, które pokazuje, że o ile \displaystyle \cc{P} \neq \cc{NP}, to nie ma wielomianowego schematu aproksymacji dla problemu MAX\displaystyle 3SAT. Wspomniane twierdzenie brzmi:

Twierdzenie 3.1

Istnieje stała \displaystyle 0 < \epsilon < 1 taka, że dla każdej instancji \displaystyle \phi problemu SAT można skonstruować instancję \displaystyle \psi problemu MAX\displaystyle 3SAT o \displaystyle m klauzulach i następujących własnościach:

  • \displaystyle \textnormal{opt} (\psi)  = m, gdy \displaystyle \phi \in SAT,
  • \displaystyle \textnormal{opt} (\psi)  < \epsilon m, gdy \displaystyle \phi \notin SAT.

Dowód

Dowód będzie się opierał o twierdzenie \displaystyle \cc{PCP}.

Ponieważ \displaystyle \cc{NP} =  \cc{PCP}(\log n,1), to niech \displaystyle V będzie weryfikatorem wykorzystującym \displaystyle c\log n bitów losowych i \displaystyle d bitów świadka dla formuły \displaystyle \phi problemu \displaystyle SAT zapisanej na \displaystyle n bitach. Dla każdego słowa \displaystyle r długości \displaystyle c\log n jako ciągu bitów losowych, \displaystyle V czyta co najwyżej \displaystyle d bitów świadka. W związku z tym liczbę różnych bitów świadka, które są czytane przy jakimkolwiek ciągu losowym, można ograniczyć przez \displaystyle dn^c. Dla każdego z tych bitów wprowadzamy osobną zmienną. Zbiór tak powstałych zmiennych nazywamy \displaystyle B, a na problem weryfikacji będziemy patrzeć jak na znalezienie wartościowania dla tych zmiennych.

Skonstruujemy teraz taką instancję problemu MAX\displaystyle dFSAT, że jeśli \displaystyle \phi jest spełnialna, to istnieje wartościowanie, przy którym wszystkie funkcje dają wynik pozytywny, a jeżeli \displaystyle \phi nie jest spełnialna, to co najwyżej połowa funkcji może jednocześnie dać wynik pozytywny.

Jako zbiór zmiennych wybieramy \displaystyle B. Dla każdego słowa \displaystyle r tworzymy funkcję logiczną \displaystyle f_r, która odpowiada obliczeniu \displaystyle V na \displaystyle \phi przy ciągu losowym \displaystyle r. Przy ustalonym \displaystyle r znamy algorytm \displaystyle V, zawartość taśmy wejściowej i taśmy z ciągiem losowym. Odwołania do świadka tłumaczymy na odwołania do zmiennych z \displaystyle B. Każda z funkcji \displaystyle f_r odwołuje się do co najwyżej \displaystyle d zmiennych. Funkcję \displaystyle f_r możemy zatem skonstruować w czasie wielomianowym, ponieważ mamy gwarancję, że \displaystyle V działa w czasie wielomianowym.

Możemy zatem skonstruować taką instancję w czasie wielomianowym. Pozostaje zatem pokazać własności rozwiązania optymalnego dla tej instancji. Jeżeli \displaystyle \phi jest spełnialna, to istnieje świadek taki, że weryfikator \displaystyle V akceptuje słowo dla każdego ciągu losowego \displaystyle r. Zatem przy wartościowaniu zmiennych odpowiadającemu temu świadkowi wszystkie funkcje \displaystyle f_r dają wynik pozytywny. Jeżeli natomiast \displaystyle \phi nie jest spełnialna, to dla każdego świadka (a więc przy każdym naborze zmiennych \displaystyle B), dla co najmniej połowy możliwych ciągów \displaystyle r wartość \displaystyle f_r jest negatywna.

Możemy teraz wykorzystać L-redukcję problemu MAX\displaystyle dFSAT do MAX\displaystyle 3SAT. Jeżeli wszystkie funkcje są jednocześnie spełnialne (a więc kiedy istnieje świadek gwarantujący akceptację \displaystyle V), to redukcja tworzy formułę MAX\displaystyle 3SAT, w której wszystkie klauzule są jednocześnie spełnialne.

Jeżeli natomiast przynajmniej połowa funkcji jest niespełniona, to również stała frakcja klauzul w fromule MAX\displaystyle 3SAT musi pozostać niespełniona. Wystarczy przypomnieć, że liczba klauzul odpowiadających bramkom wyjściowym była liniowa względem ilości wszystkich innych bramek.

image:End_of_proof.gif

Wniosek 3.2

O ile \displaystyle \cc{P} \neq \cc{NP}, to istnieje stała \displaystyle 0 < \epsilon < 1 taka, że nie jest możliwa \displaystyle \epsilon-aproksymacja problemu MAX\displaystyle 3SAT. Nie istnieje zatem też PTAS dla tego problemu.

Wniosek ten ma kluczowe znaczenie dla klasy \displaystyle \cc{MAXSNP} i pokazuje, że rzeczywiście twierdzenie \displaystyle \cc{PCP} jest ważnym narzędziem w badaniu aproksymacji.

Teraz pokażemy, że przy wykorzystaniu właśnie udowodnionego twierdzenia można dość łatwo udowodnić twierdzenie \displaystyle \cc{PCP}. W ten sposób jeszcze mocniej potwierdzimy związki twiedzenia \displaystyle \cc{PCP} z teorią algorytmów aproksymacyjnych.

Dowód

Chcemy pokazać, że o ile istnieje stała \displaystyle \epsilon taka, jak w poprzednim twierdzeniu, to można skonstruować odpowiedni weryfikator dla każdego języka z \displaystyle \cc{NP}.

Skonstruujemy \displaystyle (\braq{\log n, 1})-ograniczony weryfikator dla języka SAT. Dowód, że pociąga to za sobą istnienie takich weryfikatorów dla innych języków w \displaystyle \cc{NP}, pozostawiamy jako ćwiczenie.

Weryfikator będzie działał w następujący sposób:

[Weryfikator dla SAT]
1. Wczytaj formułę logiczną \displaystyle \phi.
2. Skonstruuj instancję \displaystyle \psi problemu MAX\displaystyle 3SAT, taką jak w poprzednim twierdzeniu.
3. Potraktuj świadka jako wartościowanie zmiennych występujących w \displaystyle \psi.
4. Użyj bitów losowych do wyznaczenia \displaystyle k klauzul, których wartość zostanie sprawdzona.
5. Zaakceptuj \displaystyle \phi, jeżeli wszystkie sprawdzenia wypadły pozytywnie.
W przeciwnym przypadku odrzuć formułę \displaystyle \phi.

Stałą \displaystyle k dobieramy tak, żeby \displaystyle \epsilon^k < \frac{1}{2}. Zauważmy, że nowy weryfikator korzysta z \displaystyle k \log m bitów losowych do wyznaczenia numerów sprawdzanych klauzul i \displaystyle 3k bitów świadka. Jeżeli \displaystyle \phi jest spełnialna, to wszystkie klauzule \displaystyle \psi mogą być jednocześnie spełnione i wartościowanie realizujące optimum jest świadkiem gwarantującym zaakceptowanie \displaystyle \phi. Z kolei jeżeli \displaystyle \phi nie jest spełnialna, to losowo wybrana klauzula jest wartościowana pozytywnie z prawdopodobieństwem mniejszym od \displaystyle \epsilon. W związku z tym dokonanie \displaystyle k sprawdzeń gwarantuje, że formuła \displaystyle \phi zostanie zaakceptowana z prawdopodobieństwem mniejszym od \displaystyle \frac{1}{2}.

Dowiedliśmy zatem, że skonstruowany weryfikator rozpoznaje język SAT.

image:End_of_proof.gif

Ćwiczenie 3.4

Weryfikatory dla innych języków.

Pokaż, że jeżeli istnieje \displaystyle (\braq{\log n, 1})-ograniczony weryfikator dla języka SAT, to można skonstruować \displaystyle (\braq{\log n, 1})-ograniczony weryfikator dla dowolnego języka z klasy \displaystyle \cc{NP}.

Wskazówka

Skorzystaj z tego, że SAT jest \displaystyle \cc{NP}-zupełny.

Rozwiązanie

Niech \displaystyle V będzie weryfikatorem dla SAT, a \displaystyle L językiem z klasy \displaystyle \cc{NP}. Możemy skonstruować weryfikator dla języka \displaystyle L w bardzo prosty sposób:

[Weryfikator dla \displaystyle L]
1. Wczytaj słowo \displaystyle x.
2. Użyj redukcji logarytmicznej problemu \displaystyle L do SAT. Otrzymasz formułę \displaystyle \phi.
3. Użyj weryfikatora \displaystyle V na formule \displaystyle \phi.
4. Zaakceptuj słowo \displaystyle x, jeżeli \displaystyle V zaakceptował \displaystyle \phi.

Skonstruowany weryfikator działa w czasie wielomianowym, używając dokładnie tylu samu bitów losowych i bitów świadka co \displaystyle V. Są to wielkości \displaystyle (\braq{\log n, 1})-ograniczone od rozmiaru \displaystyle \phi. Ten z kolei jest wielomianowy od \displaystyle |\size{x}|, więc są one też \displaystyle (\braq{\log n, 1})-ograniczone względem \displaystyle |\size{x}|.

Jeżeli \displaystyle x \in L, to \displaystyle \phi \in SAT i istnieje świadek gwarantujący akceptację. Jeżeli natomiast \displaystyle c \notin L, to \displaystyle \phi \notin SAT i dla żadnego świadka prawdopodobieństwo akceptacji nie przekracza \displaystyle \frac{1}{2}.

Ćwiczenie 3.6

PTAS dla problemów \displaystyle \cc{MAXSNP}-trudnych.

Pokaż, że o ile \displaystyle \cc{P} \neq \cc{NP}, to dla żadnego z problemów \displaystyle \cc{MAXSNP}-trudnych (w sensie L-redukcji) nie istnieje algorytm PTAS.

Wskazówka

Wiesz już, że korzystając z twierdzenia \displaystyle \cc{PCP}, można dowieść, że dla problemu MAX\displaystyle 3SAT nie istnieje PTAS.

Rozwiązanie

Udowodniliśmy, że dla problemu MAX\displaystyle 3SAT nie może istnieć algorytm PTAS, o ile \displaystyle \cc{P} \neq \cc{NP}. Gdyby dla jakiegoś problemu \displaystyle \cc{MAXSNP}-trudnego \displaystyle A istniał PTAS, to korzystając z tego, że wielomianowe schematy aproksymacji przenoszą się przez L-redukcje i tego, że MAX\displaystyle 3SAT L-redukuje się do \displaystyle A, otrzymalibyśmy taki schemat dla problemu MAX\displaystyle 3SAT.

Inne problemy \displaystyle \cc{MAXSNP}-zupełne

Pokazaliśmy, że dla żadnego z problemów \displaystyle \cc{MAXSNP}-trudnych nie może istnieć wielomianowy schemat aproksymacji. Nie znamy jednak jeszcze zbyt wielu takich problemów. Pokażemy teraz o kilku problemach, że są \displaystyle \cc{MAXSNP}-zupełne. Pozwoli nam to nie tylko stwierdzić, że nie ma dla nich algorytmów PTAS, ale także da nam narzędzia do stwierdzenia o wielu innych problemach, że są \displaystyle \cc{MAXSNP}-trudne.

\displaystyle kOCCUR MAX\displaystyle lSAT

Pewną bazową rodziną problemów będą problemy \displaystyle kOCCUR MAX\displaystyle lSAT. Są to wersje problemu MAX\displaystyle lSAT, w których liczba wszystkich wystąpień każdej pojedynczej zmiennej jest ograniczona przez \displaystyle k.

Bardzo łatwo można dowieść, że problem \displaystyle 3OCCUR \displaystyle 3SAT jest \displaystyle \cc{NP}-zupełny. Zredukujemy problem \displaystyle 3SAT. Jeżeli w formule \displaystyle \phi jakaś zmienna \displaystyle x występuje wielokrotnie w formule, powiedzmy \displaystyle k razy, to możemy stworzyć \displaystyle k nowych zmiennych: \displaystyle x_1,x_2,\ldots,x_k. Każde wystąpienie zmiennej \displaystyle x zamienić na wystąpienie innej zmiennej \displaystyle x_i, a następnie dodać gadżet, który zapewni, że każda ze zmiennych \displaystyle x_i musi być wartościowana tak samo. Takim gadżetem może być ciąg klauzul:

\displaystyle (\braq{x_1 \vee \neg x_2}) \wedge (\braq{x_2 \vee \neg x_3}) \wedge \ldots \wedge (\braq{x_{k-1} \vee \neg x_k}) \wedge (\braq{x_k \vee \neg x_1})\textnormal{.}

Okazuje się jednak, że użycie tego konkretnego gadżetu nie zapewnia L-redukcji. Wartościowanie nowych zmiennych w optymalnym rozwiązaniu problemu maksymalizacji spełnialności wcale nie musi być zgodne na zmiennych \displaystyle x_1,x_2,\ldots,x_k.

Żeby skonstruować lepszy gadżet, użyjemy specjalnych grafów-ekspanderów.

Definicja 4.1

Graf \displaystyle G=(\braq{V,E}) nazywamy {ekspanderem}, jeśli wszystkie jego wierzchołki mają ten sam stopień i dla dowolnego niepustego podzbioru \displaystyle S \subsetneq V zachodzi:

\displaystyle |\size{ E(S,V\setminus S) }| >  \min(|\size{S}|,|\size{V\setminus S}|) ,

gdzie \displaystyle  E(A,B) jest zbiorem krawędzi o jednym końcu w \displaystyle A, a drugim w \displaystyle B.

Ekspandery mają bardzo interesujące zastosowania w kilku dziedzinach współczesnej matematyki i informatyki. My wykorzystamy ich własności do skonstruowania odpowiedniego gadżetu zapewniającego zgodne wartościowanie zmiennych \displaystyle x_1,x_2,\ldots,x_k.

Przypuśćmy, że znamy algorytm, który dla zadanej liczby \displaystyle n wygeneruje ekspander o \displaystyle n wierzchołkach, z których każdy ma stopień \displaystyle d, gdzie \displaystyle d jest pewną stałą. Używając tego algorytmu, pokażemy L-redukcję problemu MAX\displaystyle 3SAT do \displaystyle (\braq{2d+1})OCCUR MAX\displaystyle 3SAT.

Twierdzenie 4.2

\displaystyle (\braq{2d+1})OCCUR MAX\displaystyle 3SAT jest \displaystyle \cc{MAXSNP}-zupełny.

Dowód

Redukcja przebiega tak jak poprzednio. Dla zmiennej \displaystyle x występującej \displaystyle k razy w formule \displaystyle \phi tworzymy \displaystyle k zmiennych \displaystyle x_1,x_2,\ldots,x_k dla nowej formuły \displaystyle \psi. Następnie przepisujemy wszystkie klauzule z \displaystyle \phi do \displaystyle \psi, zamieniając każde wystąpienie \displaystyle x na inną ze zmiennych \displaystyle x_i.

Potem konstruujemy \displaystyle k-elementowy ekspander \displaystyle F_x o stopniu wierzchołków \displaystyle d. Etykietujemy wierzchołki grafu \displaystyle F_x zmiennymi \displaystyle V_x=\set{x_1,x_2,\ldots,x_k}. Dla każdej krawędzi \displaystyle x_ix_j w grafie \displaystyle F_x dodajemy do formuły \displaystyle \psi klauzule \displaystyle (\braq{x_i \vee \neg x_j}) i \displaystyle (\braq{\neg x_i \vee x_j}).

Do formuły \displaystyle \psi dodaliśmy \displaystyle \frac{kd}{2} nowych klauzul. Zauważmy, że jeżeli wartościowanie zmiennych \displaystyle x_1,x_2,\ldots,x_k jest zgodne, to wszystkie dodane klauzule są spełnione. Jeżeli natomiast zbiór \displaystyle S \subseteq V_x jest wartościowany odwrotnie niż \displaystyle V_x \setminus S, to własności ekspanedera gwarantują, że co najmniej \displaystyle  \min(|\size{S}|,|\size{V_x\setminus S}|) +1 klauzul jest niespełnionych.

Zauważmy, że skonstruowana formuła \displaystyle \psi jest formułą problemu \displaystyle (\braq{2d+1})OCCUR MAX\displaystyle 3SAT. Każda ze zmiennych występuje dokładnie w \displaystyle 2d klauzulach odpowiadających krawędziom ekspandera i w jednej klazuli pochodzącej z formuły \displaystyle \phi.

Pokażemy teraz, że każde rozwiązanie optymalne dla formuły \displaystyle \psi musi być zgodne na zmiennych \displaystyle x_1,x_2,\ldots,x_k. Weźmy zatem jakieś rozwiązanie optymalne, które przyporządkowuje różne wartości zmiennym \displaystyle x_1,x_2,\ldots,x_k. Niech \displaystyle S będzie mniejszym z podzbiorów, który jest wartościowany zgodnie. Zastanówmy się co by się stało, gdybyśmy odwrócili wartościowanie zmiennych z \displaystyle S? Zmienne te występują w \displaystyle |\size{S}| klauzulach z formuły \displaystyle \phi, które po tej zamianie mogłyby przestać być spełnione. Stracilibyśmy zatem najwyżej \displaystyle |\size{S}| spełnionych klauzul. Z drugiej jednak strony zyskalibyśmy \displaystyle |\size{S}|+1 spełnionych klauzul opisujących krawędzie ekspandera. Zatem nowe rozwiązanie spełniałoby co najmniej jedną kaluzulę więcej niż poprzednie, przecząc optymalności.

Jeżeli w formule \displaystyle \phi było \displaystyle m klauzul, to było co najwyżej \displaystyle 3m wystąpień zmiennych, a w formule \displaystyle \psi w związku z tym jest co najwyżej \displaystyle (\braq{2d+1})3m klauzul. Przypomnijmy, że optimum dla problemu MAX\displaystyle 3SAT wynosi co najmniej \displaystyle \frac{m}{2} i możemy w związku z tym ustalić współczynnik \displaystyle \alpha dla L-redukcji na \displaystyle (2d+1)6.

Postaramy się teraz ustalić współczynnik \displaystyle \beta, aby zakończyć dowód. Możemy założyć, że w rozwiązaniu dla formuły \displaystyle \psi każda grupa zmiennych \displaystyle x_1,x_2,\ldots,x_k jest zgodnie wartościowana. Gdyby było przeciwnie, to na podstawie przeprowadzonego rozumowania można by takie rozwiązanie łatwo poprawić. Ta "poprawka" może być realizowana przez funkcję przeprowadzającą rozwiązania. Łatwo zauważyć, że w tej sytuacji ilość niespełnionych klauzul w formule \displaystyle \psi jest dokładnie równa liczbie niespełnionych klauzul przy wartościowaniu wyznaczonym dla formuły \displaystyle \phi. Współczynnik \displaystyle \beta wynosi zatem \displaystyle 1.

Pokazaliśmy L-redukcję \displaystyle \cc{MAXSNP}-zupełnego problemu MAX\displaystyle 3SAT do \displaystyle (\braq{2d+1})OCCUR MAX\displaystyle 3SAT, co pozwala nam stwierdzić, że ten drugi problem również jest \displaystyle \cc{MAXSNP}-zupełny.

image:End_of_proof.gif

Siła właśnie udowodnionego twierdzenia zależy od tego, jakie ekspandery potrafimy generować. Można bardzo łatwo udowodnić metodami propabilistycznymi, że prawie każdy graf, w którym wszystkie wierzchołki mają ten sam stopień, jest ekspanderem. Dowód taki jednak nie daje żadnej efektywnej metody konstruowania ekspanderów.

Do działania zdefiniowanej L-redukcji jest potrzebny algorytm generowania dowolnie dużych ekspanderów o ustalonym stopniu wierzchołków. Są znane algorytmy, które realizują to zadanie, ale ich opis wykracza poza zakres tego kursu.

Podobnymi metodami, korzystając z grafów o właściwościach bardzo podobnych do ekspanderów, można pokazać, że już problem \displaystyle 3OCCUR MAX\displaystyle 3SAT jest \displaystyle \cc{MAXSNP}-zupełny. Skorzystamy z tego faktu, nie przedstawiając szczegółowego dowodu.

Wykorzystamy teraz problem \displaystyle 3OCCUR MAX\displaystyle 3SAT do pokazania \displaystyle \cc{MAXSNP}-zupełności kilku problemów.

Lemat 4.3

Problemy \displaystyle 4-NODE COVER i \displaystyle 4-INDEPENDENT SET są \displaystyle \cc{MAXSNP}-zupełne.

Dowód

Przypomnijmy, że już pokazaliśmy, że problemy \displaystyle k-NODE COVER i \displaystyle k-INDEPENDENT SET należą do klasy \displaystyle \cc{MAXSNP}. Teraz wystarczy przypomnieć sobie zwykłą redukcję problemu \displaystyle 3SAT do NODE COVER, która tworzy trójkąt dla każdej klauzuli i łączy krawędziami przeciwne literały. Ta redukcja w przypadku formuły \displaystyle 3OCCUR MAX\displaystyle 3SAT stworzy graf, w którym stopień wierzchołka będzie ograniczony przez \displaystyle 4.

Łatwo uzasadnić, że ta redukcja jest L-redukcją, gdyż przynajmniej połowa z \displaystyle m klauzul jest spełnialna, a rozmiar minimalnego pokrycia wierzchołkowego jest ograniczony przez liczbę wierzchołków równą \displaystyle 3m. Współczynnik \displaystyle \beta jak zwykle wynosi \displaystyle 1.

Uzasadniliśmy, że problem \displaystyle 4-NODE COVER jest \displaystyle \cc{MAXSNP}-zupełny. Znamy już L-redukcję \displaystyle k-NODE COVER do \displaystyle k-INDEPENDENT SET. Pozwala nam to stwierdzić \displaystyle \cc{MAXSNP}-zupełność problemu \displaystyle 4-INDEPENDENT SET.

image:End_of_proof.gif

Wniosek 4.4

Problemy NODE COVER i INDEPENDENT SET są \displaystyle \cc{MAXSNP}-trudne.

Lemat 4.5

Problemy \displaystyle 5OCCUR MAX\displaystyle 2SAT i MAX NAE\displaystyle 3SAT są \displaystyle \cc{MAXSNP}-zupełne.

Dowód

Żeby pokazać \displaystyle \cc{MAXSNP}-zupełność problemu \displaystyle 5OCCUR MAX\displaystyle 2SAT, skonstruujemy L-redukcję problemu \displaystyle 4-INDEPENDENT SET. Mając dany graf \displaystyle G=(\braq{V,E}), konstruujemy formułę, tworząc następujące klauzule:

  • \displaystyle (\braq{x}) dla każdego wierzchołka \displaystyle x \in V.
  • \displaystyle (\braq{\neg x \vee \neg y}) dla każdej krawędzi \displaystyle xy \in E.

Skonstruowana formuła ma \displaystyle |\size{V}| + |\size{E}| klauzul. Możemy tę liczbę ograniczyć przez \displaystyle 3|\size{V}|. Z kolei, przypominając analizę L-redukcji \displaystyle k-INDEPENDENT SET do \displaystyle k-NODE COVER, możemy stwierdzić, że rozmiar maksymalnego zbioru niezależnego wynosi co najmniej \displaystyle \frac{|\size{V}|}{5}. Zatem współczynnik \displaystyle \alpha L-redukcji ustalamy na \displaystyle 15.

Możemy założyć, że znalezione rozwiązanie wartościuje pozytywnie wszystkie klauzule odpowiadające krawędziom. Jeżeli tak nie jest, to można je zmodyfikować, falsyfikując którąkolwiek zmienną w nim występującą i nie pogorszy to wyniku. Stracimy co najwyżej jedną spełnioną klauzulę, ale na pewno zyskamy co najmniej jedną.

W związku z tym każde rozwiązanie \displaystyle 5OCCUR MAX\displaystyle 2SAT wyznacza zbiór niezależny wierzchołków, które są wartościowane pozytywnie. Odległość od rozwiązania optymalnego jest w obu przypadkach taka sama i w związku z tym możemy ustalić współczynnik \displaystyle \beta = 1.

L-redukcja problemu MAX\displaystyle 2SAT do MAX NAE\displaystyle 3SAT przebiega w bardzo łatwy sposób. Do każdej klauzuli dopisujemy wystąpienie nowej zmiennej \displaystyle x. Wystarczy zauważyć, że jeżeli jakieś wartościowanie zmiennych NAE-spełnia daną formułę, to wartościowanie do niego odwrotne również. Możemy zatem założyć, że zmienna \displaystyle x zawsze jest wartościowana negatywnie. Maksymalna liczba klauzul spełnialnych jednocześnie, jak i spełnionych przy konkretnym wartościowaniu jest zatem taka sama w obu problemach i możemy ustalić współczynniki \displaystyle \alpha=1 i \displaystyle \beta=1.

image:End_of_proof.gif

Ćwiczenie 4.6

MAX CUT jest \displaystyle \cc{MAXSNP}-zupełny.

Wskazówka

Przypomnij sobie redukcję problemu NAE\displaystyle 3SAT do MAX CUT.

Rozwiązanie

Przedstawiona wsześniej redukcja problemu NAE\displaystyle 3SAT do MAX CUT jest L-redukcją. Przypomnijmy, że polegała ona na zmodyfikowaniu formuły \displaystyle \phi tak, żeby żadna klauzula nie zawierała jednocześnie literału i jego zaprzeczenia oraz aby żadne dwie klauzule nie miały dwóch wspólnych literałów. Następnie należało stworzyć wierzchołek dla każdego literału i połączyć krawędziami literały przeciwne, a każdą klauzulę przedstawić jako trójkąt.

Optimum dla formuły \displaystyle \phi zawierającej \displaystyle m klauzul wynosi co najmniej \displaystyle \frac{3}{4}m. Żeby to uzasadnić, wystarczy zauważyć, że NAE\displaystyle 3-spełnialność jest przykładem funkcji logicznej \displaystyle 3-argumentowej, w której tylko \displaystyle 2 z \displaystyle 8 wartościowań zmiennych dają wynik negatywny. Możemy zatem użyć rozumowania przestawionego przy algorytmie aproksymacyjnym dla problemu MAX\displaystyle kFSAT, żeby uzasadnić, iż optimum wynosi co najmniej \displaystyle \frac{3}{4}m.

Liczba wszystkich krawędzi w skonstruowanym grafie wynosi co najwyżej \displaystyle 18m. Modyfikacje formuły mogą zwiększyć liczbę klauzul do \displaystyle 3m. W \displaystyle 3m klauzulach występuje co najwyżej \displaystyle 9m zmiennych tworzących po jednej krawędzi. Jednocześnie \displaystyle 3m klauzul daje \displaystyle 9m następnych krawędzi. W związku z tym współczynnik \displaystyle \alpha L-redukcji ustalamy na \displaystyle 24.

Różnica pomiędzy \displaystyle n+2m a liczbą krawędzi w znalezionym przekroju odpowiada dokładnie liczbie niespełnionych klauzul w formule \displaystyle \phi. W związku z tym współczynnik \displaystyle \beta wynosi jak zwykle \displaystyle 1.

Ćwiczenie 4.7

\displaystyle (\braq{2d+1})OCCUR MAX NAE\displaystyle 3SAT jest \displaystyle \cc{MAXSNP}-zupełny.

Wskazówka

Przeprowadź L-redukcję problemu MAX NAE\displaystyle 3SAT w podobny sposób, jak zredukowaliśmy MAX\displaystyle 3SAT do \displaystyle (\braq{2d+1})OCCUR MAX\displaystyle 3SAT.

Rozwiązanie

Przedstawimy konstrukcję podobną do dowodu, że \displaystyle (\braq{2d+1})OCCUR MAX\displaystyle 3SAT jest \displaystyle \cc{MAXSNP}-zupełny. Do redukcji użyjemy oczywiście tym razem problemu MAX NAE\displaystyle 3SAT. Wielokrotne wystąpienia tej samej zmiennej tak samo zamienimy na nowe zmienne, natomiast konstrukcja gadżetu wymuszającego zgodne wartościowanie na tych zmiennych przebiega w następujący sposób. Dla zmiennych \displaystyle x_1,x_2,\ldots,x_k tworzymy \displaystyle k-elementowy ekspander \displaystyle F_x o stopniu \displaystyle d etykietowany tymi zmiennymi. Dla każdej krawędzi \displaystyle x_ix_j w \displaystyle F_x tworzymy nową zmienną \displaystyle y_{x,i,j}, a do formuły dodajemy klauzule:

\displaystyle (\braq{x_i \vee \neg x_j \vee y_{x,i,j}}) \wedge (\braq{\neg x_i \vee x_j \vee y_{x,i,j}})\textnormal{.}

Każda zmienna w skonstruowanej formule występuje co najwyżej \displaystyle 2d+1 razy. Własności ekspandera, tak jak poprzednio, zapewniają, że możemy rozważać tylko rozwiązania wartościujące zmienne \displaystyle x_1,x_2,\ldots,x_k zgodnie.

Powtarzając zatem to samo rozumowanie, udowodnimy \displaystyle \cc{MAXSNP}-zupełność problemu \displaystyle (\braq{2d+1})OCCUR NAE\displaystyle 3SAT.

Problem INDEPENDENT SET

Wiemy już, że problem INDEPENDENT SET jest \displaystyle \cc{MAXSNP}-trudny, gdyż jego zawężenia są zupełne dla tej klasy. Oznacza to, że o ile \displaystyle \cc{P} \neq \cc{NP}, to nie ma algorytmu PTAS dla INDEPENDENT SET. Udowodnimy teraz, że nie jest możliwa również aproksymacja ze stałą. Pokażemy, że jeżeli istniałby jakikolwiek algorytm ze stałą aproksymacji, to można by to wykorzystać do stworzenia algorytmu PTAS.

Co ciekawe, fakt ten był znany na długo przed pojawieniem się twierdzenia \displaystyle \cc{PCP}. Wiedziano, że problem INDEPENDENT SET albo można aproksymować dowolnie dobrze, albo w ogóle. Dopiero twierdzenie \displaystyle \cc{PCP} rozwiało wątpliowści, która z tych możliwości jest prawdziwa.

Żeby udowodnić zapowiedziane twierdzenie, będziemy chcieli przyjrzeć się następującej konstrukcji:

Definicja 5.1

Dla dwóch grafów \displaystyle G=(\braq{V_G,E_G}) i \displaystyle H=(\braq{V_H,E_H}) {grafem iloczynowym} \displaystyle G \times H oznaczamy graf o wierzchołkach \displaystyle V_G \times V_H i krawędziach:

  • \displaystyle (\braq{a,x})(\braq{b,y}) dla \displaystyle ab \in E_G i dowolnych \displaystyle x i \displaystyle y.
  • \displaystyle (\braq{a,x})(\braq{a,y}) dla \displaystyle xy \in E_H.


Rys.9.2. Graf iloczynowy

Przykład 5.2

Konstrukcja odpowiada "włożeniu" grafu \displaystyle H w każdy wierzchołek grafu \displaystyle G. Nam będzie potrzebna tylko konstrukcja \displaystyle G^2 = G \times G.

Lemat 5.3

W grafie \displaystyle G=(\braq{V,E}) istnieje zbiór niezależny rozmiaru \displaystyle k wtedy i tylko wtedy, gdy w \displaystyle G^2 istnieje zbiór niezależny rozmiaru \displaystyle k^2.

Dowód

Jeżeli \displaystyle I \subseteq V jest zbiorem niezależnym rozmiaru \displaystyle k w \displaystyle G, to zbiór \displaystyle I^2 = \defset \{ {(\braq{x,y})} : {x \in I \wedge y \in I} \} jest zbiorem niezależnym rozmiaru \displaystyle k^2 w grafie \displaystyle G^2.

Jeżeli natomiast \displaystyle I \subseteq V^2 jest zbiorem niezależnym rozmiaru \displaystyle k^2 w \displaystyle G^2, to każdy ze zbiorów:

  • \displaystyle I_1 = \defset \{ {x} : {\exists_y (\braq{x,y}) \in I } \},
  • \displaystyle I_2^x = \defset \{ {y} : {(\braq{x,y}) \in I} \} dla każdego \displaystyle x \in I_1,

musi być zbiorem niezależnym w \displaystyle G. Jeżeli rozmiar każdego z tych zbiorów byłby mniejszy od \displaystyle k, to rozmiar \displaystyle I byłby mniejszy od \displaystyle k^2. Zatem któryś z tych zbiorów musi mieć rozmiar większy lub równy \displaystyle k.

image:End_of_proof.gif

Twierdzenie 5.4

Jeżeli istnieje algorytm \displaystyle a-aproksymacyjny dla problemu INDEPENDENT SET, to istnieje algorytm PTAS dla tego problemu.

Dowód

Załóżmy, że \displaystyle \mathcal{A} jest \displaystyle a-aproksymacyjnym algorytmem dla problemu INDEPENDENT SET. Niech \displaystyle k będzie rozmiarem maksymalnego zbioru niezależnego w grafie \displaystyle G. Jeżeli wykonamy algorytm \displaystyle \mathcal{A} na grafie \displaystyle G^2, to otrzymamy zbiór niezależny rozmiaru \displaystyle ak^2. Poprzedni lemat zapewnia, że w czasie wielomianowym możemy z tego rozwiązania uzyskać pewien zbiór niezależny rozmiaru \displaystyle \sqrt{ak^2}. Tym samym stworzyliśmy nowy algorytm, który jest \displaystyle \sqrt{a}-aproksymacyjny.

Skorzystamy teraz z tego, że dla \displaystyle 0 < a \leq 1 ciąg \displaystyle \sqrt[2^n]{a} ma granicę w nieskończoności równą \displaystyle 1. Schemat PTAS powstaje w związku z tym przez zastosowanie algorytmu \displaystyle \mathcal{A} dla grafu \displaystyle G^{2^n}, dla odpowiednio dużego \displaystyle n. Jeżeli chcemy osiągnąć \displaystyle (\braq{1-\epsilon})-aproksymację, to otrzymamy następujące oszacowanie na \displaystyle n:

\displaystyle \aligned 1-\epsilon &\leq  \sqrt[2^n]{a} \\ (\braq{1-epsilon})^{2^n} &\leq  a \\ 2^n &\geq  \log_{1-\epsilon}a \\ n &\geq  \log_2(\log_{1-\epsilon}a)\textnormal{.} \endaligned
image:End_of_proof.gif

Ćwiczenie 5.5

Algorytm zachłanny dla problemu INDEPENDENT SET.

Pokazaliśmy, że o ile \displaystyle \cc{P} \neq \cc{NP}, to nie ma algorytmu \displaystyle a-aproksymacyjnego dla INDEPENDENT SET. Pokaż, że algorytm zachłanny nie jest algorytmem \displaystyle a-aproksymacyjnym.

Algorytm zachłanny.
Dopóki w grafie są wierzchołki:
1. Wybierz wierzchołek \displaystyle v o najmniejszym stopniu.
2. Dodaj \displaystyle v do zbioru niezależnego i usuń go z grafu wraz ze wszystkimi sąsiadami.

Wskazówka

Użyj dodatkowych wierzchołków podnoszących stopień w rozwiązaniu optymalnym, żeby zmylić algorytm zachłanny.

Rozwiązanie

Przeanalizujmy graf \displaystyle G_k, dla \displaystyle k \in \naturals, w którym wierzchołki możemy podzielić na trzy grupy:

  • \displaystyle A - grupa \displaystyle k wierzchołków. Każdy z nich jest połączony z \displaystyle k wierzchołkami z grupy \displaystyle B.
  • \displaystyle B - grupa \displaystyle k^2 wierzchołków. Każdy jest połączony z jednym wierzchołkiem z grupy \displaystyle A i z \displaystyle k wierzcholkami z grupy \displaystyle C.
  • \displaystyle C - grupa \displaystyle k wierzchołków połączonych ze wszystkimi wierzchołkami w \displaystyle B.

Algorytm zachłanny będzie wybierał wierzchołki z \displaystyle A, gdyż mają one najniższy stopień. Jednocześnie będzie systematycznie usuwał całą grupę \displaystyle B. Na koniec doda wszystkie wierzchołki z grupy \displaystyle C. Skonstruuje w ten sposób zbiór niezależny o rozmiarze \displaystyle 2k.

Tymczasem rozwiązanie optymalne ma \displaystyle k^2 wierzchołków. Wystarczy wybrać całą grupę \displaystyle B.

Oznacza to, że na grafie \displaystyle G_k rozwiązanie algorytmu zachłannego jest \displaystyle \frac{k}{2} razy gorsze od optymalnego. Dobierając odpowiednią wartość \displaystyle k > 2a, możemy udowodnić, że algorytm zachłanny nie jest \displaystyle a-aproksymacyjny.

Pewniejsze weryfikatory

Przedstawimy teraz pewne uogólnienie definicji języków rozpoznawanych przez weryfikatory. To wzbogacenie pozwoli nam w następnej części pokazać bardzo ciekawe ograniczenie możliwości aproksymacji.

W definicji języka rozpoznawanego przez ograniczony weryfikator wymagaliśmy, aby prawdopodobieństwo zaakceptowania słowa z języka przy odpowiednim świadku wynosiło \displaystyle 1, a prawdopodobieństwo zaakceptowania słowa spoza języka przy żadnym świadku nie przekraczało \displaystyle \frac{1}{2}. Spróbujemy się teraz przyjrzeć sytuacji, w której stałe \displaystyle 1 i \displaystyle \frac{1}{2} mogą się zmieniać.

Definicja 6.1

Język \displaystyle L należy do klasy \displaystyle  \cc{PCP}_{c,s}(p,q), jeżeli istnieje weryfikator \displaystyle V, który dla wejścia \displaystyle x długości \displaystyle n bitów działa w czasie wielomianowym od \displaystyle n, korzysta z \displaystyle \mathcal{O}{ p(n) } bitów losowych i \displaystyle \mathcal{O}{ q(n) } bitów świadka oraz:

  • Dla \displaystyle x \in L istnieje świadek \displaystyle y taki, że \displaystyle V akceptuje z prawdopodobieństwem większym lub równym \displaystyle c.
  • Dla \displaystyle x \notin L, dla każdego świadka \displaystyle y, \displaystyle V akceptuje z prawdopodobieństwem mniejszym od \displaystyle s.

Zauważmy, że wcześniejsza definicja \displaystyle  \cc{PCP}(p,q) odpowiada teraz \displaystyle  \cc{PCP}_{1,\frac{1}{2}}(p,q). Dość łatwo można uzyskać równość \displaystyle  \cc{PCP}_{1,\frac{1}{2}}(\log n,1)  =  \cc{PCP}_{1,a}(\log n, 1) dla każdej stałej \displaystyle 0 < a < 1. Działanie weryfikatora klasy \displaystyle  \cc{PCP}_{1,a}(\log n, 1) można powtórzyć \displaystyle k razy, otrzymując weryfikator klasy \displaystyle  \cc{PCP}_{1,a^k}(k\log n, k). Dlatego naprawdę ciekawe rezultaty otrzymamy dopiero, kiedy dopuścimy, aby \displaystyle c i \displaystyle s mogły zależeć od \displaystyle n.

Szczególnie interesującym wydaje się ograniczenie błędnej akceptacji w sposób odwrotnie proporcjonalny do rozmiaru wejścia. Równość \displaystyle  \cc{PCP}_{1,\frac{1}{2}}(\log n,1)  =  \cc{PCP}_{1,\frac{1}{n}}(\log^2n,\log n) otrzymujemy tą samą metodą. Możemy przecież powtórzyć działanie weryfikatora \displaystyle \log n razy, wykorzystując \displaystyle \log n razy więcej bitów losowych i bitów świadka.

Okazuje się jednak, że można użyć znacznie mniej bitów losowych. Mówi o tym następujące twierdzenie:

Twierdzenie 6.2

\displaystyle \cc{NP} =  \cc{PCP}_{1,\frac{1}{n}}(\log n, \log n).

Dowód

Przypomnijmy, że pokazaliśmy, że \displaystyle \cc{NP} =  \cc{PCP}(\log n, \textnormal{poly}(n) ) i w związku z tym zawieranie \displaystyle  \cc{PCP}_{1,\frac{1}{n}}(\log n, \log n)  \subseteq \cc{NP} nie wymaga dalszego komentarza.

Aby pokazać, że \displaystyle \cc{NP} =  \cc{PCP}_{1,\frac{1}{2}}(\log n, 1)  \subseteq  \cc{PCP}_{1,\frac{1}{n}}(\log n, \log n), odwołamy się jeszcze raz do ekspanderów. Okazuje się, że nadają się one świetnie do zmniejszenia liczby bitów losowych wymaganych przy obliczeniu. Konkretnie skorzystamy z następującej własności, którą pozostawimy bez dowodu:

image:End_of_proof.gif

Twierdzenie 6.3

Jeżeli graf \displaystyle F=(\braq{V,E}) jest ekspanderem o \displaystyle n^c wierzchołkach i \displaystyle S \subseteq V jest podzbiorem wierzchołków takim, że \displaystyle |\size{S}| < \frac{|\size{V}|}{2}, to istnieje stała \displaystyle k taka, że prawdopodobieństwo następującego zdarzenia:

"Wszystkie wierzchołki losowej ścieżki długości \displaystyle  k\log n należą do \displaystyle  S ",

jest mniejsze od \displaystyle \frac{1}{n}.

Zauważmy, że aby opisać ścieżkę losową długości \displaystyle k\log n w ekspanderze potrzeba \displaystyle \mathcal{O}{\log n} bitów -- \displaystyle c\log n bitów opisuje wierzchołek początkowy, a ponieważ wierzchołki ekspandera mają stały stopień, to do opisania każdej kolejnej krawędzi jest potrzebna stała ilość bitów.

To spostrzeżenie jest kluczowe dla dowodu. Pozwala ono opisać ścieżkę, która ma dobre właściwości "przeglądania" grafu przy pomocy \displaystyle \mathcal{O}{\log n} bitów.

Niech \displaystyle V będzie \displaystyle (\braq{\log n,1})-ograniczonym weryfikatorem dla języka \displaystyle L. \displaystyle V używa podczas obliczenia co najwyżej \displaystyle c\log n bitów losowych i \displaystyle d bitów świadka.

Skonstruujemy weryfikator \displaystyle W klasy \displaystyle  \cc{PCP}_{1,\frac{1}{n}}(\log n, \log n) dla języka \displaystyle L.

Algorytm 6.4 [Weryfikator klasy \displaystyle  \cc{PCP}_{1,\frac{1}{n}}(\log n, \log n)]


1. Skonstruuj ekspander \displaystyle F o \displaystyle n^c wierzchołkach.
Każdy wierzchołek jest etykietowany ciągiem \displaystyle c\log n bitów.

2. Używając \displaystyle k\log n bitów losowych, wygeneruj ścieżkę losową \displaystyle P w grafie \displaystyle F.

3. Przechodząc ścieżkę \displaystyle P, dokonaj symulacji weryfikatora \displaystyle V
na ciągu losowym reprezentowanym przez każdy z wierzchołków.

4. Zaakceptuj słowo, jeżeli każda z symulacji weryfikatora \displaystyle V zakończyła się akceptacją.

Podany algorytm weryfikatora działa w czasie wielomianowym od \displaystyle n, używa \displaystyle \mathcal{O}{\log n} bitów losowych do ustalenia ścieżki \displaystyle P, a podczas wszystkich symulacji weryfikatora \displaystyle V używane jest w sumie \displaystyle \mathcal{O}{\log n} bitów świadka.

Jeżeli słowo \displaystyle x \in L, to istnieje świadek \displaystyle y, przy którym prawdopodobieństwo akceptacji weryfikatora \displaystyle V wynosi \displaystyle 1. Dla tego samego świadka weryfikator \displaystyle W także dokona akceptacji z prawdopodobieństwem \displaystyle 1.

Jeżeli natomiast \displaystyle x \notin L, to dla każdego świadka \displaystyle y prawdopodobieństwo akceptacji przez weryfikator \displaystyle V jest mniejsze od \displaystyle \frac{1}{2}. Oznaczmy przez \displaystyle S wierzchołki \displaystyle F, które reprezentują te ciągi bitów losowych, przy których następuje akceptacja. Własności ścieżek losowych w ekspanderach zapewniają, że prawdopodobieństwo, że ścieżka \displaystyle P w całości znajduje się w \displaystyle S jest mniejsze od \displaystyle \frac{1}{n}. Jeżeli ścieżka \displaystyle P wyjdzie poza zbiór \displaystyle S, to weryfikator \displaystyle W odrzuci słowo. W związku z tym prawdopodobieństwo błędnej akceptacji jest mniejsze od \displaystyle \frac{1}{n}.

Ćwiczenie 6.5

Niepewny weryfikator.

Nie analizowaliśmy jeszcze weryfikatorów, dla których prawdopodobieństwo akceptacji słowa należącego do języka jest mniejsze od \displaystyle 1. Pokaż, że dla dowolnego \displaystyle 0 < \epsilon < \frac{1}{2} zachodzi:

\displaystyle \cc{NP} =  \cc{PCP}_{1-\epsilon,\frac{1}{2}}(\log n,1)\textnormal{.}

Wskazówka

Użyj charakteryzacji \displaystyle \cc{NP} z twierdzenia \displaystyle \cc{PCP}.

Rozwiązanie

Zawieranie \displaystyle \cc{NP} \subseteq  \cc{PCP}_{1-\epsilon,\frac{1}{2}}(\log n, 1) jest dość oczywiste. Dla każdego języka \displaystyle L z \displaystyle \cc{NP} istniej weryfikator klasy \displaystyle  \cc{PCP}_{1,\frac{1}{2}}(\log n, 1). Ten sam weryfikator zapewnia przynależność języka \displaystyle L do \displaystyle  \cc{PCP}_{1-\epsilon,\frac{1}{2}}(\log n, 1).

Żeby uzasadnić drugie zawieranie, wystarczy przypomnieć dowód, że \displaystyle  \cc{PCP}_{1,\frac{1}{2}}(\log n, \textnormal{poly}(n) )  \subseteq \cc{NP}. Postępując tak samo jak tam, możemy niedeterministycznie wygenerować świadka, a potem przejrzeć obliczenia przy wszystkich ciągach losowych. Różnica polega na tym, że akceptacji dokonujemy, jeżeli co najmniej \displaystyle (\braq{1-\epsilon})k ze wszystkich \displaystyle k testów wypadnie pozytywnie.

To samo rozumowanie pozwala stwierdzić, że dla dowolnych \displaystyle 0 \leq s < c \leq 1 zachodzi:

\displaystyle \cc{NP} =  \cc{PCP}_{c,s}(\log n, 1)\textnormal{.}

Problem CLIQUE

Jest to kontynuacja naszych rozważań dotyczących aproksymacji problemu INDEPENDENT SET. Każdy wynik dotyczący aproksymacji problemu CLIQUE jest jednocześnie wynikiem dla INDEPENDENT SET. Wystarczy przecież zamienić graf na jego dopełnienie, żeby jeden problem zamienił się w drugi. Tylko ze względu na wygodniejsze oznaczenia zdecydowaliśmy się "przenieść" do grafu dopełnieniowego i rozważać problem CLIQUE zamiast INDEPENDENT SET.

Wykorzystamy teraz nowo wprowadzone definicje do pokazania bardzo ciekawego rezultatu. Udowodnimy mianowicie, że o ile \displaystyle \cc{P} \neq \cc{NP}, to dla problemu CLIQUE nie istnieje algorytm \displaystyle \alpha-aproksymacyjny, gdzie \displaystyle \alpha(n) = \frac{1}{n^\epsilon} dla pewnego \displaystyle 0 < \epsilon < 1.

Jest to stwierdzenie mocniejsze niż wyniki pokazane wcześniej, gdyż podaje pewne asymptotyczne ograniczenie możliwości tworzenia algorytmów \displaystyle \alpha-aproksymacyjnych.

Dowód będzie w swojej konstrukcji przypominał dowód nieaproksymowalności MAX\displaystyle 3SAT w oparciu o twierdzenie \displaystyle \cc{PCP}. Z tą różnicą, że tym razem wykorzystamy weryfikator klasy \displaystyle  \cc{PCP}_{1,\frac{1}{n}}(\log n, \log n). Gdybyśmy wykorzystali charakteryzację \displaystyle \cc{NP} =  \cc{PCP}_{1,\frac{1}{2}}(\log n, 1), uzyskalibyśmy podobny rezultat mówiący o tym, że nie istnieje algorytm \displaystyle \epsilon-aproksymacyjny dla problemu CLIQUE.

Twierdzenie 7.1

Istnieją stałe \displaystyle c i \displaystyle d takie, że dla każdej instancji \displaystyle \phi problem SAT można skonstruować graf \displaystyle G o \displaystyle n^{c+d} wierzchołkach taki, że dla problemu CLIQUE:

  • \displaystyle \textnormal{opt} (G)  \geq n^c, gdy \displaystyle \phi \in SAT,
  • \displaystyle \textnormal{opt} (G)  < n^{c-1}, gdy \displaystyle \phi \notin SAT.

Dowód

Niech \displaystyle V będzie weryfikatorem klasy \displaystyle  \cc{PCP}_{1,\frac{1}{n}}(\log n, \log n) dla języka SAT. \displaystyle V podczas działania używa co najwyżej \displaystyle c\log n bitów losowych i \displaystyle d\log n bitów świadka.

Konstruujemy graf \displaystyle G=(\braq{V,E}), gdzie wierzchołki \displaystyle V odpowiadają parom ciągów bitowych długości \displaystyle c\log n i \displaystyle d\log n. Takich par jest oczywiście \displaystyle n^{c+d}. Wierzchołek reprezentujący ciągi \displaystyle r i \displaystyle b oznaczamy przez \displaystyle v_{r,b} i intuicyjnie będzie on odpowiadał sytuacji, kiedy ciągiem losowym był \displaystyle r, a odczytane bity świadka tworzą ciąg \displaystyle b.

Wierzchołek \displaystyle v_{r,b} jest akceptujący, gdy weryfikator \displaystyle V akceptuje formułę \displaystyle \phi przy ciągu bitów losowych równym \displaystyle r i odczytach świadka równych \displaystyle b.

Dwa wierzchołki \displaystyle v_{r_1,b_1} i \displaystyle v_{r_2,b_2} łączymy krawędzią, gdy oba są akceptujące i bity odczytane z tych samych pozycji świadka są takie same w \displaystyle b_1 i \displaystyle b_2. Zauważmy, że jeżeli \displaystyle r_1 = r_2 i \displaystyle b_1 \neq b_2, to nie może być krawędzi łączącej \displaystyle v_{r_1,b_1} z \displaystyle v_{r_2,b_2}, gdyż pierwszy bit rozróżniający \displaystyle b_1 i \displaystyle b_2 jest odczytywany przez \displaystyle V z tej samej pozycji.

Jeżeli formuła \displaystyle \phi jest spełnialna, to istnieje taki świadek \displaystyle y, przy którym każdy ciąg losowy długości \displaystyle c\log n zapewnia akceptację. Zatem wierzchołki odpowiadające wszystkim możliwym \displaystyle r i odczytom \displaystyle b, takim jak przy świadku \displaystyle y, tworzą klikę. Rozmiar tej kliki to \displaystyle n^c.

Jeżeli natomiast formuła \displaystyle \phi nie jest spełnialna, a \displaystyle C jest kliką w grafie \displaystyle G, to musi zachodzić \displaystyle |\size{C}| < n^{c-1}. Gdyby było przeciwnie, to zauważmy, że klika \displaystyle C generuje pewnego świadka \displaystyle y, który odpowiada odczytom w wierzchołkach kliki (być może bity na nie wszystkich pozycjach są określone, ale nie jest to istotne). Zauważmy dalej, że jeżeli \displaystyle |\size{C}| \geq n^{c-1}, to wierzchołki \displaystyle C odpowiadają \displaystyle n^{c-1} różnym ciągom losowym \displaystyle r i przy każdym z nich weryfikator \displaystyle V akceptuje formułę \displaystyle \phi.

Zatem przy świadku \displaystyle y prawdopodobieństwo zaakceptowania formuły \displaystyle \phi jest większe lub równe \displaystyle \frac{n^{c-1}}{n^c} = \frac{1}{n}. Jest to niemożliwe ze względu na to, że formuła \displaystyle \phi nie jest spełnialna, a \displaystyle V ma prawdopodbieństwo błędnej akceptacji mniejsze od \displaystyle \frac{1}{n}.

Zatem rozmiar największej kliki w grafie \displaystyle G skonstruowanym dla niespełnialnej formuły \displaystyle \phi musi być mniejszy od \displaystyle n^{c-1}.

image:End_of_proof.gif

Wniosek 7.2

Istnieje stała \displaystyle 0 < \epsilon < 1 taka, że o ile \displaystyle \cc{P} \neq \cc{NP}, to nie istnieje algorytm \displaystyle \frac{1}{n^\epsilon}-aproksymacyjny dla problemu CLIQUE.

Dowód

Ustalmy \displaystyle \epsilon = \frac{1}{c} dla stałej \displaystyle c z poprzedniego twierdzenia. Niech \displaystyle \mathcal{A} będzie algorytmem \displaystyle \frac{1}{n^\epsilon}-aproksymacyjnym dla problemu CLIQUE.

Dla dowolnej formuły \displaystyle \phi możemy skonstruować graf \displaystyle G taki jak w poprzednim twierdzeniu.

Jeżeli \displaystyle \phi jest spełnialna, to \displaystyle \textnormal{opt} (G) \geq n^c i algorytm \displaystyle \mathcal{A} znajdzie rozwiązanie o rozmiarze większym lub równym:

\displaystyle (\braq{\frac{1}{n^\frac{1}{c}}}) n^c = \frac{n^c}{n^\frac{1}{c}} = n^{c-\frac{1}{c}} \geq n^{c-1}\textnormal{.}

Jeżeli natomiast \displaystyle \phi nie jest spełnialna to rozmiar każdego rozwiązania jest mniejszy od \displaystyle n^{c-1}.

Możemy zatem przy pomocy algorytmu \displaystyle \mathcal{A} rozstrzygnąć \displaystyle \cc{NP}-zupełny problem SAT, co jest sprzeczne z założeniem \displaystyle \cc{P} \neq \cc{NP}.

image:End_of_proof.gif

Wniosek 7.3

Istnieje stała \displaystyle 0 < \epsilon < 1 taka, że o ile \displaystyle \cc{P} \neq \cc{NP}, to nie istnieje algorytm \displaystyle \frac{1}{n^\epsilon}-aproksymacyjny dla problemu INDEPENDENT SET.

Testy końcowe