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

Wprowadzenie

Dotychczasowa analiza Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \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 Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \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 Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} -zupełnych. Odkrycie takiego schematu pociągałoby za sobą istnienie schematów dla wszystkich problemów z klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} .

Okazuje się, że pytanie o taki schemat jest równoważne pytaniu Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{P} =? \cc{NP}} . Jeżeli Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{P} \neq \cc{NP}} , to nie może istnieć schemat aproksymacji dla żadnego problemu Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} -zupełnego. Sercem dowodu tego faktu jest twierdzenie Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{PCP}} , które przedstawimy. Twierdzenie to stało się istotnym kamieniem milowym w badaniach nad aproksymacją optymalizacyjnych problemów Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{NP}} -zupełnych. Pozwoliło nie tylko rozwiązać pytania dotyczące klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \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 Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{NP}} z użyciem świadka. Klasa $NP$ to języki $L$, które mogą być przedstawione w postaci:

Parser nie mógł rozpoznać (nieznana funkcja „\defset”): {\displaystyle \displaystyle L = \{ \defset{x} : {\exists_y (\braq{x,y}) \in R} \}} ,

gdzie relacja $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 Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \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 $p$ i $q$, jeżeli dla słowa wejściowego $x$ odczytuje co najwyżej Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \displaystyle \mathcal{O}{ p(|\size{x}|) }} bitów losowych i co najwyżej Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \displaystyle \mathcal{O}{ q(|\size{x}|) }} bitów świadka. Będziemy o nim wtedy mówić, że jest Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle (\braq{p,q})} -ograniczonym weryfikatorem.

Najciekawszymi ograniczeniami są $\log n$ na liczbę bitów losowych i $1$ na liczbę bitów świadka. Języki rozpoznawane w czasie wielomianowym przez takie weryfikatory tworzą klasę Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{PCP}(\log n,1) } .

<flash>file=ZO-9-1.swf|width=350|height=250</flash>

<div.thumbcaption>Rys.9.1. Weryfikator.

Definicja 2.2

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

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

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

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{NP} = \cc{PCP}(0, \text{poly}(n) )\text{.} }

Możemy teraz sformułować długo zapowiadane twierdzenie Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{PCP}} :

Twierdzenie 2.3

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{NP} = \cc{PCP}(\log n, 1) }

Dowód

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

[Niedeterministyczny symulator weryfikatora]
1. Wybierz niedeterministycznie świadka $y$ o rozmiarze wielomianowym.
2. Dla każdego ciągu bitów $b$ długości $c\log n$ zasymuluj działanie weryfikatora na słowie wejściowym przy świadku $y$ i ciągu bitów losowych $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.

Ćwiczenie 2.5

{{{3}}}

Ćwiczenie 2.6

{{{3}}}

Twierdzenie Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{PCP}} a problem MAX$3$SAT

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

Twierdzenie 3.1

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

• $\text{opt}(\psi )=m$, gdy $\varphi \in$ SAT,
• $\text{opt}(\psi )<ϵm$, gdy $\varphi \notin$ SAT.

Dowód

Dowód będzie się opierał o twierdzenie Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{PCP}} .

Ponieważ Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{NP} = \cc{PCP}(\log n,1) } , to niech $V$ będzie weryfikatorem wykorzystującym $c\log n$ bitów losowych i $d$ bitów świadka dla formuły $\varphi$ problemu $SAT$ zapisanej na $n$ bitach. Dla każdego słowa $r$ długości $c\log n$ jako ciągu bitów losowych, $V$ czyta co najwyżej $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 $d{n}^c$. Dla każdego z tych bitów wprowadzamy osobną zmienną. Zbiór tak powstałych zmiennych nazywamy $B$, a na problem weryfikacji będziemy patrzeć jak na znalezienie wartościowania dla tych zmiennych.

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

Jako zbiór zmiennych wybieramy $B$. Dla każdego słowa $r$ tworzymy funkcję logiczną $f_r$, która odpowiada obliczeniu $V$ na $\varphi$ przy ciągu losowym $r$. Przy ustalonym $r$ znamy algorytm $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 $B$. Każda z funkcji $f_r$ odwołuje się do co najwyżej $d$ zmiennych. Funkcję $f_r$ możemy zatem skonstruować w czasie wielomianowym, ponieważ mamy gwarancję, że $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 $\varphi$ jest spełnialna, to istnieje świadek taki, że weryfikator $V$ akceptuje słowo dla każdego ciągu losowego $r$. Zatem przy wartościowaniu zmiennych odpowiadającemu temu świadkowi wszystkie funkcje $f_r$ dają wynik pozytywny. Jeżeli natomiast $\varphi$ nie jest spełnialna, to dla każdego świadka (a więc przy każdym naborze zmiennych $B$), dla co najmniej połowy możliwych ciągów $r$ wartość $f_r$ jest negatywna.

Możemy teraz wykorzystać L-redukcję problemu MAX$d$FSAT do MAX$3$SAT. Jeżeli wszystkie funkcje są jednocześnie spełnialne (a więc kiedy istnieje świadek gwarantujący akceptację $V$), to redukcja tworzy formułę MAX$3$SAT, 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$3$SAT musi pozostać niespełniona. Wystarczy przypomnieć, że liczba klauzul odpowiadających bramkom wyjściowym była liniowa względem ilości wszystkich innych bramek.

Wniosek 3.2

O ile Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{P} \neq \cc{NP}} , to istnieje stała $0<ϵ<1$ taka, że nie jest możliwa $ϵ$-aproksymacja problemu MAX$3$SAT. Nie istnieje zatem też PTAS dla tego problemu.

Wniosek ten ma kluczowe znaczenie dla klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} i pokazuje, że rzeczywiście twierdzenie Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \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 Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{PCP}} . W ten sposób jeszcze mocniej potwierdzimy związki twiedzenia Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{PCP}} z teorią algorytmów aproksymacyjnych.

Dowód

Chcemy pokazać, że o ile istnieje stała $ϵ$ taka, jak w poprzednim twierdzeniu, to można skonstruować odpowiedni weryfikator dla każdego języka z Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{NP}} .

Skonstruujemy Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \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 Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{NP}} , pozostawiamy jako ćwiczenie.

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

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

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

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

Ćwiczenie 3.4

{{{3}}}

Ćwiczenie 3.6

{{{3}}}

Inne problemy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} -zupełne

Pokazaliśmy, że dla żadnego z problemów Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \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ą Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \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ą Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} -trudne.

$k$OCCUR MAX$l$SAT

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

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

Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \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})\text{.} }

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 $x_1,x_2,\dots ,x_k$.

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

Definicja 4.1

Graf Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle G=(\braq{V,E})} nazywamy {ekspanderem}, jeśli wszystkie jego wierzchołki mają ten sam stopień i dla dowolnego niepustego podzbioru $S⊊V$ zachodzi:

Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \displaystyle |\size{ E(S,V\setminus S) }| > \min(|\size{S}|,|\size{V\setminus S}|) } ,

gdzie $E(A,B)$ jest zbiorem krawędzi o jednym końcu w $A$, a drugim w $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 $x_1,x_2,\dots ,x_k$.

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

Twierdzenie 4.2

Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle (\braq{2d+1})} OCCUR MAX$3$SAT jest Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} -zupełny.

Dowód

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

Potem konstruujemy $k$-elementowy ekspander $F_x$ o stopniu wierzchołków $d$. Etykietujemy wierzchołki grafu $F_x$ zmiennymi Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle \displaystyle V_x=\set{x_1,x_2,\ldots,x_k}} . Dla każdej krawędzi $x_i{x}_j$ w grafie $F_x$ dodajemy do formuły $\psi$ klauzule Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle (\braq{x_i \vee \neg x_j})} i Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle (\braq{\neg x_i \vee x_j})} .

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

Zauważmy, że skonstruowana formuła $\psi$ jest formułą problemu Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle (\braq{2d+1})} OCCUR MAX$3$SAT. Każda ze zmiennych występuje dokładnie w $2d$ klauzulach odpowiadających krawędziom ekspandera i w jednej klazuli pochodzącej z formuły $\varphi$.

Pokażemy teraz, że każde rozwiązanie optymalne dla formuły $\psi$ musi być zgodne na zmiennych $x_1,x_2,\dots ,x_k$. Weźmy zatem jakieś rozwiązanie optymalne, które przyporządkowuje różne wartości zmiennym $x_1,x_2,\dots ,x_k$. Niech $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 $S$? Zmienne te występują w Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \displaystyle |\size{S}|} klauzulach z formuły $\varphi$, które po tej zamianie mogłyby przestać być spełnione. Stracilibyśmy zatem najwyżej Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \displaystyle |\size{S}|} spełnionych klauzul. Z drugiej jednak strony zyskalibyśmy Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \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 $\varphi$ było $m$ klauzul, to było co najwyżej $3m$ wystąpień zmiennych, a w formule $\psi$ w związku z tym jest co najwyżej Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle (\braq{2d+1})3m} klauzul. Przypomnijmy, że optimum dla problemu MAX$3$SAT wynosi co najmniej $\frac{m}{2}$ i możemy w związku z tym ustalić współczynnik $\alpha$ dla L-redukcji na $(2d+1)6$.

Postaramy się teraz ustalić współczynnik $\beta$, aby zakończyć dowód. Możemy założyć, że w rozwiązaniu dla formuły $\psi$ każda grupa zmiennych $x_1,x_2,\dots ,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 $\psi$ jest dokładnie równa liczbie niespełnionych klauzul przy wartościowaniu wyznaczonym dla formuły $\varphi$. Współczynnik $\beta$ wynosi zatem $1$.

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

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 $3$OCCUR MAX$3$SAT jest Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} -zupełny. Skorzystamy z tego faktu, nie przedstawiając szczegółowego dowodu.

Wykorzystamy teraz problem $3$OCCUR MAX$3$SAT do pokazania Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} -zupełności kilku problemów.

Lemat 4.3

Problemy $4$-NODE COVER i $4$-INDEPENDENT SET są Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} -zupełne.

Dowód

Przypomnijmy, że już pokazaliśmy, że problemy $k$-NODE COVER i $k$-INDEPENDENT SET należą do klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} . Teraz wystarczy przypomnieć sobie zwykłą redukcję problemu $3$SAT 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 $3$OCCUR MAX$3$SAT stworzy graf, w którym stopień wierzchołka będzie ograniczony przez $4$.

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

Uzasadniliśmy, że problem $4$-NODE COVER jest Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} -zupełny. Znamy już L-redukcję $k$-NODE COVER do $k$-INDEPENDENT SET. Pozwala nam to stwierdzić Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} -zupełność problemu $4$-INDEPENDENT SET.

Wniosek 4.4

Problemy NODE COVER i INDEPENDENT SET są Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} -trudne.

Lemat 4.5

Problemy $5$OCCUR MAX$2$SAT i MAX NAE$3$SAT są Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} -zupełne.

Dowód

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

• Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle (\braq{x})} dla każdego wierzchołka $x\in V$.
• Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle (\braq{\neg x \vee \neg y})} dla każdej krawędzi $xy\in E$.

Skonstruowana formuła ma Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \displaystyle |\size{V}| + |\size{E}|} klauzul. Możemy tę liczbę ograniczyć przez Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \displaystyle 3|\size{V}|} . Z kolei, przypominając analizę L-redukcji $k$-INDEPENDENT SET do $k$-NODE COVER, możemy stwierdzić, że rozmiar maksymalnego zbioru niezależnego wynosi co najmniej Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \displaystyle \frac{|\size{V}|}{5}} . Zatem współczynnik $\alpha$ L-redukcji ustalamy na $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 $5$OCCUR MAX$2$SAT 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 $\beta =1$.

L-redukcja problemu MAX$2$SAT do MAX NAE$3$SAT przebiega w bardzo łatwy sposób. Do każdej klauzuli dopisujemy wystąpienie nowej zmiennej $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 $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 $\alpha =1$ i $\beta =1$.

Ćwiczenie 4.6

{{{3}}}

Ćwiczenie 4.7

{{{3}}}

Problem INDEPENDENT SET

Wiemy już, że problem INDEPENDENT SET jest Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} -trudny, gdyż jego zawężenia są zupełne dla tej klasy. Oznacza to, że o ile Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \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 Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{PCP}} . Wiedziano, że problem INDEPENDENT SET albo można aproksymować dowolnie dobrze, albo w ogóle. Dopiero twierdzenie Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \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 Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle G=(\braq{V_G,E_G})} i Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle H=(\braq{V_H,E_H})} {grafem iloczynowym} $G\times H$ oznaczamy graf o wierzchołkach $V_G\times V_H$ i krawędziach:

• Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle (\braq{a,x})(\braq{b,y})} dla $ab\in E_G$ i dowolnych $x$ i $y$.
• Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle (\braq{a,x})(\braq{a,y})} dla $xy\in E_H$.

<flash>file=ZO-9-3.swf|width=300|height=300</flash>

<div.thumbcaption>Rys.9.2. Graf iloczynowy

Przykład 5.2

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

Lemat 5.3

W grafie Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle G=(\braq{V,E})} istnieje zbiór niezależny rozmiaru $k$ wtedy i tylko wtedy, gdy w $G^2$ istnieje zbiór niezależny rozmiaru $k^2$.

Dowód

Jeżeli $I\subseteq V$ jest zbiorem niezależnym rozmiaru $k$ w $G$, to zbiór Parser nie mógł rozpoznać (nieznana funkcja „\defset”): {\displaystyle \displaystyle I^2 = \defset \{ {(\braq{x,y})} : {x \in I \wedge y \in I} \}} jest zbiorem niezależnym rozmiaru $k^2$ w grafie $G^2$.

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

• Parser nie mógł rozpoznać (nieznana funkcja „\defset”): {\displaystyle \displaystyle I_1 = \defset \{ {x} : {\exists_y (\braq{x,y}) \in I } \}} ,
• Parser nie mógł rozpoznać (nieznana funkcja „\defset”): {\displaystyle \displaystyle I_2^x = \defset \{ {y} : {(\braq{x,y}) \in I} \}} dla każdego $x\in I_1$,

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

Twierdzenie 5.4

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

Dowód

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

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

Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle \begin{align} 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)\text{.} \end{align}}

Ćwiczenie 5.5

{{{3}}}

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 $1$, a prawdopodobieństwo zaakceptowania słowa spoza języka przy żadnym świadku nie przekraczało $\frac{1}{2}$. Spróbujemy się teraz przyjrzeć sytuacji, w której stałe $1$ i $\frac{1}{2}$ mogą się zmieniać.

Definicja 6.1

Język $L$ należy do klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{PCP}_{c,s}(p,q) } , jeżeli istnieje weryfikator $V$, który dla wejścia $x$ długości $n$ bitów działa w czasie wielomianowym od $n$, korzysta z ${𝒪}p(n)$ bitów losowych i ${𝒪}q(n)$ bitów świadka oraz:

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

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

Szczególnie interesującym wydaje się ograniczenie błędnej akceptacji w sposób odwrotnie proporcjonalny do rozmiaru wejścia. Równość Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \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 $\log n$ razy, wykorzystując $\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

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{NP} = \cc{PCP}_{1,\frac{1}{n}}(\log n, \log n) } .

Dowód

Przypomnijmy, że pokazaliśmy, że Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{NP} = \cc{PCP}(\log n, \text{poly}(n) ) } i w związku z tym zawieranie Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{PCP}_{1,\frac{1}{n}}(\log n, \log n) \subseteq \cc{NP}} nie wymaga dalszego komentarza.

Aby pokazać, że Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \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:

Twierdzenie 6.3

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

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

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

Zauważmy, że aby opisać ścieżkę losową długości $k\log n$ w ekspanderze potrzeba ${𝒪}\log n$ bitów -- $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 ${𝒪}\log n$ bitów.

Niech $V$ będzie Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle (\braq{\log n,1})} -ograniczonym weryfikatorem dla języka $L$. $V$ używa podczas obliczenia co najwyżej $c\log n$ bitów losowych i $d$ bitów świadka.

Skonstruujemy weryfikator $W$ klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{PCP}_{1,\frac{1}{n}}(\log n, \log n) } dla języka $L$.

Algorytm 6.4 [Weryfikator klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{PCP}_{1,\frac{1}{n}}(\log n, \log n) } ]

---

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

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

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

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

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

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

Jeżeli natomiast $x\notin L$, to dla każdego świadka $y$ prawdopodobieństwo akceptacji przez weryfikator $V$ jest mniejsze od $\frac{1}{2}$. Oznaczmy przez $S$ wierzchołki $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 $P$ w całości znajduje się w $S$ jest mniejsze od $\frac{1}{n}$. Jeżeli ścieżka $P$ wyjdzie poza zbiór $S$, to weryfikator $W$ odrzuci słowo. W związku z tym prawdopodobieństwo błędnej akceptacji jest mniejsze od $\frac{1}{n}$.

Ćwiczenie 6.5

{{{3}}}

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 Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{P} \neq \cc{NP}} , to dla problemu CLIQUE nie istnieje algorytm $\alpha$-aproksymacyjny, gdzie $\alpha (n)=\frac{1}{n^{ϵ}}$ dla pewnego $0<ϵ<1$.

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

Dowód będzie w swojej konstrukcji przypominał dowód nieaproksymowalności MAX$3$SAT w oparciu o twierdzenie Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{PCP}} . Z tą różnicą, że tym razem wykorzystamy weryfikator klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{PCP}_{1,\frac{1}{n}}(\log n, \log n) } . Gdybyśmy wykorzystali charakteryzację Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \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 $ϵ$-aproksymacyjny dla problemu CLIQUE.

Twierdzenie 7.1

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

• $\text{opt}(G)\ge n^c$, gdy $\varphi \in$ SAT,
• $\text{opt}(G)<n^{c-1}$, gdy $\varphi \notin$ SAT.

Dowód

Niech $V$ będzie weryfikatorem klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{PCP}_{1,\frac{1}{n}}(\log n, \log n) } dla języka SAT. $V$ podczas działania używa co najwyżej $c\log n$ bitów losowych i $d\log n$ bitów świadka.

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

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

Dwa wierzchołki $v_{r_1,b_1}$ i $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 $b_1$ i $b_2$. Zauważmy, że jeżeli $r_1=r_2$ i $b_1\ne b_2$, to nie może być krawędzi łączącej $v_{r_1,b_1}$ z $v_{r_2,b_2}$, gdyż pierwszy bit rozróżniający $b_1$ i $b_2$ jest odczytywany przez $V$ z tej samej pozycji.

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

Jeżeli natomiast formuła $\varphi$ nie jest spełnialna, a $C$ jest kliką w grafie $G$, to musi zachodzić Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \displaystyle |\size{C}| < n^{c-1}} . Gdyby było przeciwnie, to zauważmy, że klika $C$ generuje pewnego świadka $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 Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \displaystyle |\size{C}| \geq n^{c-1}} , to wierzchołki $C$ odpowiadają $n^{c-1}$ różnym ciągom losowym $r$ i przy każdym z nich weryfikator $V$ akceptuje formułę $\varphi$.

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

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

Wniosek 7.2

Istnieje stała $0<ϵ<1$ taka, że o ile Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{P} \neq \cc{NP}} , to nie istnieje algorytm $\frac{1}{n^{ϵ}}$-aproksymacyjny dla problemu CLIQUE.

Dowód

Ustalmy $ϵ=\frac{1}{c}$ dla stałej $c$ z poprzedniego twierdzenia. Niech ${𝒜}$ będzie algorytmem $\frac{1}{n^{ϵ}}$-aproksymacyjnym dla problemu CLIQUE.

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

Jeżeli $\varphi$ jest spełnialna, to $\text{opt}(G)\ge n^c$ i algorytm ${𝒜}$ znajdzie rozwiązanie o rozmiarze większym lub równym:

Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \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}\text{.} }

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

Możemy zatem przy pomocy algorytmu ${𝒜}$ rozstrzygnąć Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{NP}} -zupełny problem SAT, co jest sprzeczne z założeniem Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{P} \neq \cc{NP}} .

Wniosek 7.3

Istnieje stała $0<ϵ<1$ taka, że o ile Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{P} \neq \cc{NP}} , to nie istnieje algorytm $\frac{1}{n^{ϵ}}$-aproksymacyjny dla problemu INDEPENDENT SET.