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

Wprowadzenie

Dotychczasowa analiza $\mathrm {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 $\mathrm {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 $\mathrm {MAXSNP}$-zupełnych. Odkrycie takiego schematu pociągałoby za sobą istnienie schematów dla wszystkich problemów z klasy $\mathrm {MAXSNP}$.

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

$L=\{{x}:{\exists _{y}({\mathit {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 $\mathrm {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 ${\mathcal {O}}{p(|{\mathit {x}}|)}$ bitów losowych i co najwyżej ${\mathcal {O}}{q(|{\mathit {x}}|)}$ bitów świadka. Będziemy o nim wtedy mówić, że jest $({\mathit {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ę $\mathrm {PCP} (\log n,1)$.

Rys.9.1. Weryfikator.

Definicja 2.2

Język $L$ należy do $\mathrm {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 $|{\mathit {x}}|$ bez względu na odczytane bity losowe i świadka. Podczas działania odczytuje co najwyżej $c\log |{\mathit {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 Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle V} akceptuje z prawdopodobieństwem Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 1} .
• Jeżeli słowo Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle x \notin L} , to dla każdego świadka Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle y} Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle V} odrzuca z prawdopodobieństwem większym od Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \frac{1}{2}} .

Klasy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \mathrm{PCP}(p,q)} definiuje się analogicznie. Charakteryzację klasy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \mathrm{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ć (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \mathrm{NP} = \mathrm{PCP}(0, \text{poly}(n) )\text{.} }

Możemy teraz sformułować długo zapowiadane twierdzenie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \mathrm{PCP}} :

Twierdzenie 2.3

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \mathrm{NP} = \mathrm{PCP}(\log n, 1) }

Dowód

Dowód jednej części tego twierdzenia jest prosty. Żeby pokazać zawieranie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \mathrm{PCP}(\log n,1) \subseteq NP} , wystarczy przeanalizować następującą niedeterministyczną maszynę Turinga:

[Niedeterministyczny symulator weryfikatora]
1. Wybierz niedeterministycznie świadka Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 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

Pseudoweryfikator dla SAT.

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

Wskazówka

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

Rozwiązanie

Użyjemy $\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 $3$ bitów świadka, aby poznać wartościowanie pojedynczej klauzuli $3$SAT. 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ż $1-{\frac {1}{m}}$.

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

Ćwiczenie 2.6

Charakteryzacje $\mathrm {P}$ i $\mathrm {NP}$ poprzez $\mathrm {PCP}$.

Uzasadnij poniższe równości:

• $\mathrm {P} =\mathrm {PCP} (0,0)=\mathrm {PCP} (\log n,0)=\mathrm {PCP} (0,\log n)$,
• $\mathrm {NP} =\mathrm {PCP} (\log n,1)=\mathrm {PCP} (\log n,{\text{poly}}(n))$.

Wskazówka

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

Rozwiązanie

Równość $P=\mathrm {PCP} (0,0)$ jest oczywista, gdyż weryfikator bez dostępu do bitów losowych i świadka zachowuje się jak zwykła maszyna deterministyczna. Zawierania $\mathrm {PCP} (\log n,0)\supseteq \mathrm {PCP} (0,0)\subseteq \mathrm {PCP} (0,\log n)$ też nie wymagają komentarza. Działanie weryfikatora z ${\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 ${\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 ${\mathcal {O}}{\log n}$ bitów świadka też można dokonać w czasie wykładniczym od ${\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ść $\mathrm {NP} =\mathrm {PCP} (\log n,1)$ jest treścią twierdzenia $\mathrm {PCP}$. Natomiast jeżeli przyjrzymy się bliżej przedstawionemu dowodowi, że $\mathrm {PCP} (\log n,1)\subseteq \mathrm {NP}$, to zobaczymy, że to samo rozumowanie jest słuszne dla weryfikatora $({\mathit {\log n,{\text{poly}}(n)}})$-ograniczonego.

Twierdzenie $\mathrm {PCP}$ a problem MAX$3$SAT

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

Twierdzenie 3.1

Istnieje stała $0<\epsilon <1$ taka, że dla każdej instancji $\phi$ 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 $\phi \in$ SAT,
• ${\text{opt}}(\psi )<\epsilon m$, gdy $\phi \notin$ SAT.

Dowód

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

Ponieważ $\mathrm {NP} =\mathrm {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 $\phi$ 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 $dn^{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 $\phi$ jest spełnialna, to istnieje wartościowanie, przy którym wszystkie funkcje dają wynik pozytywny, a jeżeli $\phi$ 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 $\phi$ 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 $\phi$ 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 $\phi$ 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 $\mathrm {P} \neq \mathrm {NP}$, to istnieje stała $0<\epsilon <1$ taka, że nie jest możliwa $\epsilon$-aproksymacja problemu MAX$3$SAT. Nie istnieje zatem też PTAS dla tego problemu.

Wniosek ten ma kluczowe znaczenie dla klasy $\mathrm {MAXSNP}$ i pokazuje, że rzeczywiście twierdzenie $\mathrm {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 $\mathrm {PCP}$. W ten sposób jeszcze mocniej potwierdzimy związki twiedzenia $\mathrm {PCP}$ z teorią algorytmów aproksymacyjnych.

Dowód

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

Skonstruujemy $({\mathit {\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 $\mathrm {NP}$, pozostawiamy jako ćwiczenie.

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

[Weryfikator dla SAT]
1. Wczytaj formułę logiczną $\phi$.
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 $\phi$, jeżeli wszystkie sprawdzenia wypadły pozytywnie.
  W przeciwnym przypadku odrzuć formułę $\phi$.

Stałą $k$ dobieramy tak, żeby $\epsilon ^{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 $\phi$ jest spełnialna, to wszystkie klauzule $\psi$ mogą być jednocześnie spełnione i wartościowanie realizujące optimum jest świadkiem gwarantującym zaakceptowanie $\phi$. Z kolei jeżeli $\phi$ nie jest spełnialna, to losowo wybrana klauzula jest wartościowana pozytywnie z prawdopodobieństwem mniejszym od $\epsilon$. W związku z tym dokonanie $k$ sprawdzeń gwarantuje, że formuła $\phi$ zostanie zaakceptowana z prawdopodobieństwem mniejszym od ${\frac {1}{2}}$.

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

Ćwiczenie 3.4

Weryfikatory dla innych języków.

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

Wskazówka

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

Rozwiązanie

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

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

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

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

Ćwiczenie 3.6

PTAS dla problemów $\mathrm {MAXSNP}$-trudnych.

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

Wskazówka

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

Rozwiązanie

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

Inne problemy $\mathrm {MAXSNP}$-zupełne

Pokazaliśmy, że dla żadnego z problemów $\mathrm {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ą $\mathrm {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ą $\mathrm {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 $\mathrm {NP}$-zupełny. Zredukujemy problem $3$SAT. Jeżeli w formule $\phi$ jakaś zmienna $x$ występuje wielokrotnie w formule, powiedzmy $k$ razy, to możemy stworzyć $k$ nowych zmiennych: $x_{1},x_{2},\ldots ,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:

$({\mathit {x_{1}\vee \neg x_{2}}})\wedge ({\mathit {x_{2}\vee \neg x_{3}}})\wedge \ldots \wedge ({\mathit {x_{k-1}\vee \neg x_{k}}})\wedge ({\mathit {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},\ldots ,x_{k}$.

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

Definicja 4.1

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

$|{\mathit {E(S,V\setminus S)}}|>\min(|{\mathit {S}}|,|{\mathit {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},\ldots ,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 $({\mathit {2d+1}})$OCCUR MAX$3$SAT.

Twierdzenie 4.2

$({\mathit {2d+1}})$OCCUR MAX$3$SAT jest $\mathrm {MAXSNP}$-zupełny.

Dowód

Redukcja przebiega tak jak poprzednio. Dla zmiennej $x$ występującej $k$ razy w formule $\phi$ tworzymy $k$ zmiennych $x_{1},x_{2},\ldots ,x_{k}$ dla nowej formuły $\psi$. Następnie przepisujemy wszystkie klauzule z $\phi$ 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 $V_{x}={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 $({\mathit {x_{i}\vee \neg x_{j}}})$ i $({\mathit {\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},\ldots ,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 $\min(|{\mathit {S}}|,|{\mathit {V_{x}\setminus S}}|)+1$ klauzul jest niespełnionych.

Zauważmy, że skonstruowana formuła $\psi$ jest formułą problemu $({\mathit {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 $\phi$.

Pokażemy teraz, że każde rozwiązanie optymalne dla formuły $\psi$ musi być zgodne na zmiennych $x_{1},x_{2},\ldots ,x_{k}$. Weźmy zatem jakieś rozwiązanie optymalne, które przyporządkowuje różne wartości zmiennym $x_{1},x_{2},\ldots ,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 $|{\mathit {S}}|$ klauzulach z formuły $\phi$, które po tej zamianie mogłyby przestać być spełnione. Stracilibyśmy zatem najwyżej $|{\mathit {S}}|$ spełnionych klauzul. Z drugiej jednak strony zyskalibyśmy $|{\mathit {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 $\phi$ 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 $({\mathit {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},\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 $\psi$ jest dokładnie równa liczbie niespełnionych klauzul przy wartościowaniu wyznaczonym dla formuły $\phi$. Współczynnik $\beta$ wynosi zatem $1$.

Pokazaliśmy L-redukcję $\mathrm {MAXSNP}$-zupełnego problemu MAX$3$SAT do $({\mathit {2d+1}})$OCCUR MAX$3$SAT, co pozwala nam stwierdzić, że ten drugi problem również jest $\mathrm {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 $\mathrm {MAXSNP}$-zupełny. Skorzystamy z tego faktu, nie przedstawiając szczegółowego dowodu.

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

Lemat 4.3

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

Dowód

Przypomnijmy, że już pokazaliśmy, że problemy $k$-NODE COVER i $k$-INDEPENDENT SET należą do klasy $\mathrm {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 $\mathrm {MAXSNP}$-zupełny. Znamy już L-redukcję $k$-NODE COVER do $k$-INDEPENDENT SET. Pozwala nam to stwierdzić $\mathrm {MAXSNP}$-zupełność problemu $4$-INDEPENDENT SET.

Wniosek 4.4

Problemy NODE COVER i INDEPENDENT SET są $\mathrm {MAXSNP}$-trudne.

Lemat 4.5

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

Dowód

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

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

Skonstruowana formuła ma $|{\mathit {V}}|+|{\mathit {E}}|$ klauzul. Możemy tę liczbę ograniczyć przez $3|{\mathit {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 ${\frac {|{\mathit {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

MAX CUT jest $\mathrm {MAXSNP}$-zupełny.

Wskazówka

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

Rozwiązanie

Przedstawiona wsześniej redukcja problemu NAE$3$SAT do MAX CUT jest L-redukcją. Przypomnijmy, że polegała ona na zmodyfikowaniu formuły $\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 $\phi$ zawierającej $m$ klauzul wynosi co najmniej ${\frac {3}{4}}m$. Żeby to uzasadnić, wystarczy zauważyć, że NAE$3$-spełnialność jest przykładem funkcji logicznej $3$-argumentowej, w której tylko $2$ z $8$ wartościowań zmiennych dają wynik negatywny. Możemy zatem użyć rozumowania przestawionego przy algorytmie aproksymacyjnym dla problemu MAX$k$FSAT, żeby uzasadnić, iż optimum wynosi co najmniej ${\frac {3}{4}}m$.

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

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

Ćwiczenie 4.7

$({\mathit {2d+1}})$OCCUR MAX NAE$3$SAT jest $\mathrm {MAXSNP}$-zupełny.

Wskazówka

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

Rozwiązanie

Przedstawimy konstrukcję podobną do dowodu, że $({\mathit {2d+1}})$OCCUR MAX$3$SAT jest $\mathrm {MAXSNP}$-zupełny. Do redukcji użyjemy oczywiście tym razem problemu MAX NAE$3$SAT. 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 $x_{1},x_{2},\ldots ,x_{k}$ tworzymy $k$-elementowy ekspander $F_{x}$ o stopniu $d$ etykietowany tymi zmiennymi. Dla każdej krawędzi $x_{i}x_{j}$ w $F_{x}$ tworzymy nową zmienną $y_{x,i,j}$, a do formuły dodajemy klauzule:

$({\mathit {x_{i}\vee \neg x_{j}\vee y_{x,i,j}}})\wedge ({\mathit {\neg x_{i}\vee x_{j}\vee y_{x,i,j}}}){\text{.}}$

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

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

Problem INDEPENDENT SET

Wiemy już, że problem INDEPENDENT SET jest $\mathrm {MAXSNP}$-trudny, gdyż jego zawężenia są zupełne dla tej klasy. Oznacza to, że o ile $\mathrm {P} \neq \mathrm {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 $\mathrm {PCP}$. Wiedziano, że problem INDEPENDENT SET albo można aproksymować dowolnie dobrze, albo w ogóle. Dopiero twierdzenie $\mathrm {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 $G=({\mathit {V_{G},E_{G}}})$ i $H=({\mathit {V_{H},E_{H}}})$ {grafem iloczynowym} $G\times H$ oznaczamy graf o wierzchołkach $V_{G}\times V_{H}$ i krawędziach:

• $({\mathit {a,x}})({\mathit {b,y}})$ dla $ab\in E_{G}$ i dowolnych $x$ i $y$.
• $({\mathit {a,x}})({\mathit {a,y}})$ dla $xy\in E_{H}$.

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 $G=({\mathit {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 $I^{2}=\{{({\mathit {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:

• $I_{1}=\{{x}:{\exists _{y}({\mathit {x,y}})\in I}\}$,
• $I_{2}^{x}=\{{y}:{({\mathit {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 ${\mathcal {A}}$ jest $a$-aproksymacyjnym algorytmem dla problemu INDEPENDENT SET. Niech $k$ będzie rozmiarem maksymalnego zbioru niezależnego w grafie $G$. Jeżeli wykonamy algorytm ${\mathcal {A}}$ na grafie $G^{2}$, to otrzymamy zbiór niezależny rozmiaru $ak^{2}$. Poprzedni lemat zapewnia, że w czasie wielomianowym możemy z tego rozwiązania uzyskać pewien zbiór niezależny rozmiaru ${\sqrt {ak^{2}}}$. Tym samym stworzyliśmy nowy algorytm, który jest ${\sqrt {a}}$-aproksymacyjny.

Skorzystamy teraz z tego, że dla $0<a\leq 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 ${\mathcal {A}}$ dla grafu $G^{2^{n}}$, dla odpowiednio dużego $n$. Jeżeli chcemy osiągnąć $({\mathit {1-\epsilon }})$-aproksymację, to otrzymamy następujące oszacowanie na $n$:

${\begin{aligned}1-\epsilon &\leq {\sqrt[{2^{n}}]{a}}\\({\mathit {1-epsilon}})^{2^{n}}&\leq a\\2^{n}&\geq \log _{1-\epsilon }a\\n&\geq \log _{2}(\log _{1-\epsilon }a){\text{.}}\end{aligned}}$

Ćwiczenie 5.5

Algorytm zachłanny dla problemu INDEPENDENT SET.

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

Algorytm zachłanny.
Dopóki w grafie są wierzchołki:
1. Wybierz wierzchołek $v$ o najmniejszym stopniu.
2. Dodaj $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 $G_{k}$, dla $k\in \mathbb {N}$, w którym wierzchołki możemy podzielić na trzy grupy:

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

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

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

Oznacza to, że na grafie $G_{k}$ rozwiązanie algorytmu zachłannego jest ${\frac {k}{2}}$ razy gorsze od optymalnego. Dobierając odpowiednią wartość $k>2a$, możemy udowodnić, że algorytm zachłanny nie jest $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 $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 $\mathrm {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 ${\mathcal {O}}{p(n)}$ bitów losowych i ${\mathcal {O}}{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 $\mathrm {PCP} (p,q)$ odpowiada teraz $\mathrm {PCP} _{1,{\frac {1}{2}}}(p,q)$. Dość łatwo można uzyskać równość $\mathrm {PCP} _{1,{\frac {1}{2}}}(\log n,1)=\mathrm {PCP} _{1,a}(\log n,1)$ dla każdej stałej $0<a<1$. Działanie weryfikatora klasy $\mathrm {PCP} _{1,a}(\log n,1)$ można powtórzyć $k$ razy, otrzymując weryfikator klasy $\mathrm {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ść $\mathrm {PCP} _{1,{\frac {1}{2}}}(\log n,1)=\mathrm {PCP} _{1,{\frac {1}{n}}}(\log ^{2}n,\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

$\mathrm {NP} =\mathrm {PCP} _{1,{\frac {1}{n}}}(\log n,\log n)$.

Dowód

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

Aby pokazać, że $\mathrm {NP} =\mathrm {PCP} _{1,{\frac {1}{2}}}(\log n,1)\subseteq \mathrm {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 $F=({\mathit {V,E}})$ jest ekspanderem o $n^{c}$ wierzchołkach i $S\subseteq V$ jest podzbiorem wierzchołków takim, że $|{\mathit {S}}|<{\frac {|{\mathit {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 ${\mathcal {O}}{\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 ${\mathcal {O}}{\log n}$ bitów.

Niech $V$ będzie $({\mathit {\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 $\mathrm {PCP} _{1,{\frac {1}{n}}}(\log n,\log n)$ dla języka $L$.

Algorytm 6.4 [Weryfikator klasy $\mathrm {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 ${\mathcal {O}}{\log n}$ bitów losowych do ustalenia ścieżki $P$, a podczas wszystkich symulacji weryfikatora $V$ używane jest w sumie ${\mathcal {O}}{\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

Niepewny weryfikator.

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

$\mathrm {NP} =\mathrm {PCP} _{1-\epsilon ,{\frac {1}{2}}}(\log n,1){\text{.}}$

Wskazówka

Użyj charakteryzacji $\mathrm {NP}$ z twierdzenia $\mathrm {PCP}$.

Rozwiązanie

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

Żeby uzasadnić drugie zawieranie, wystarczy przypomnieć dowód, że $\mathrm {PCP} _{1,{\frac {1}{2}}}(\log n,{\text{poly}}(n))\subseteq \mathrm {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 $({\mathit {1-\epsilon }})k$ ze wszystkich $k$ testów wypadnie pozytywnie.

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

$\mathrm {NP} =\mathrm {PCP} _{c,s}(\log n,1){\text{.}}$

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 $\mathrm {P} \neq \mathrm {NP}$, to dla problemu CLIQUE nie istnieje algorytm $\alpha$-aproksymacyjny, gdzie $\alpha (n)={\frac {1}{n^{\epsilon }}}$ dla pewnego $0<\epsilon <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 $\mathrm {PCP}$. Z tą różnicą, że tym razem wykorzystamy weryfikator klasy $\mathrm {PCP} _{1,{\frac {1}{n}}}(\log n,\log n)$. Gdybyśmy wykorzystali charakteryzację $\mathrm {NP} =\mathrm {PCP} _{1,{\frac {1}{2}}}(\log n,1)$, uzyskalibyśmy podobny rezultat mówiący o tym, że nie istnieje algorytm $\epsilon$-aproksymacyjny dla problemu CLIQUE.

Twierdzenie 7.1

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

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

Dowód

Niech $V$ będzie weryfikatorem klasy $\mathrm {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 $G=({\mathit {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łę $\phi$ 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}\neq 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 $\phi$ 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 $\phi$ nie jest spełnialna, a $C$ jest kliką w grafie $G$, to musi zachodzić $|{\mathit {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 $|{\mathit {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łę $\phi$.

Zatem przy świadku $y$ prawdopodobieństwo zaakceptowania formuły $\phi$ 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 $\phi$ 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 $\phi$ musi być mniejszy od $n^{c-1}$.

Wniosek 7.2

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

Dowód

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

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

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

$({\mathit {\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 $\phi$ nie jest spełnialna to rozmiar każdego rozwiązania jest mniejszy od $n^{c-1}$.

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

Wniosek 7.3

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