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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Wprowadzenie

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

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

,

gdzie relacja 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 , 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 i , jeżeli dla słowa wejściowego odczytuje co najwyżej bitów losowych i co najwyżej bitów świadka. Będziemy o nim wtedy mówić, że jest -ograniczonym weryfikatorem.

Najciekawszymi ograniczeniami są na liczbę bitów losowych i na liczbę bitów świadka. Języki rozpoznawane w czasie wielomianowym przez takie weryfikatory tworzą klasę .

Rys.9.1. Weryfikator.

Definicja 2.2

Język należy do , jeżeli istnieje weryfikator oraz stałe i takie, że dla wejścia działa w czasie wielomianowym od bez względu na odczytane bity losowe i świadka. Podczas działania odczytuje co najwyżej bitów losowych i co najwyżej bitów świadka.

  • Jeżeli słowo , to istnieje taki świadek , że akceptuje z prawdopodobieństwem .
  • Jeżeli słowo , to dla każdego świadka odrzuca z prawdopodobieństwem większym od .

Klasy definiuje się analogicznie. Charakteryzację klasy , którą przypomnieliśmy na samym początku, możemy teraz wyrazić używając nowej terminologii równaniem:

Możemy teraz sformułować długo zapowiadane twierdzenie :

Twierdzenie 2.3

Dowód

Dowód jednej części tego twierdzenia jest prosty. Żeby pokazać zawieranie , wystarczy przeanalizować następującą niedeterministyczną maszynę Turinga:

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

End of proof.gif

Ćwiczenie 2.5

Pseudoweryfikator dla SAT.

Pokaż -ograniczony weryfikator dla języka SAT, który akceptuje niespełnialne formuły z prawdopodobieństwem nie większym niż , gdzie jest liczbą klauzul.

Wskazówka
Rozwiązanie


Ćwiczenie 2.6

Charakteryzacje i poprzez .

Uzasadnij poniższe równości:

  • ,
  • .
Wskazówka
Rozwiązanie

Twierdzenie a problem MAXSAT

Wprowadzona terminologia miała pozwolić na analizę złożoności problemów optymalizacyjnych. Przedstawimy teraz twierdzenie równoważne twierdzeniu , które pokazuje, że o ile , to nie ma wielomianowego schematu aproksymacji dla problemu MAXSAT. Wspomniane twierdzenie brzmi:

Twierdzenie 3.1

Istnieje stała taka, że dla każdej instancji problemu SAT można skonstruować instancję problemu MAXSAT o klauzulach i następujących własnościach:

  • , gdy SAT,
  • , gdy SAT.

Dowód

Dowód będzie się opierał o twierdzenie .

Ponieważ , to niech będzie weryfikatorem wykorzystującym bitów losowych i bitów świadka dla formuły problemu zapisanej na bitach. Dla każdego słowa długości jako ciągu bitów losowych, czyta co najwyżej 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 . Dla każdego z tych bitów wprowadzamy osobną zmienną. Zbiór tak powstałych zmiennych nazywamy , a na problem weryfikacji będziemy patrzeć jak na znalezienie wartościowania dla tych zmiennych.

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

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

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

End of proof.gif

Wniosek 3.2

O ile , to istnieje stała taka, że nie jest możliwa -aproksymacja problemu MAXSAT. Nie istnieje zatem też PTAS dla tego problemu.

Wniosek ten ma kluczowe znaczenie dla klasy i pokazuje, że rzeczywiście twierdzenie 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 . W ten sposób jeszcze mocniej potwierdzimy związki twiedzenia 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 .

Skonstruujemy -ograniczony weryfikator dla języka SAT. Dowód, że pociąga to za sobą istnienie takich weryfikatorów dla innych języków w , pozostawiamy jako ćwiczenie.

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

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

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

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

End of proof.gif

Ćwiczenie 3.4

Weryfikatory dla innych języków.

Pokaż, że jeżeli istnieje -ograniczony weryfikator dla języka SAT, to można skonstruować -ograniczony weryfikator dla dowolnego języka z klasy .

Wskazówka
Rozwiązanie


Ćwiczenie 3.6

PTAS dla problemów -trudnych.

Pokaż, że o ile , to dla żadnego z problemów -trudnych (w sensie L-redukcji) nie istnieje algorytm PTAS.

Wskazówka
Rozwiązanie

Inne problemy -zupełne

Pokazaliśmy, że dla żadnego z problemów -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ą -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ą -trudne.

OCCUR MAXSAT

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

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

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 .

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

Definicja 4.1

Graf nazywamy {ekspanderem}, jeśli wszystkie jego wierzchołki mają ten sam stopień i dla dowolnego niepustego podzbioru zachodzi:

,

gdzie jest zbiorem krawędzi o jednym końcu w , a drugim w .

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 .

Przypuśćmy, że znamy algorytm, który dla zadanej liczby wygeneruje ekspander o wierzchołkach, z których każdy ma stopień , gdzie jest pewną stałą. Używając tego algorytmu, pokażemy L-redukcję problemu MAXSAT do OCCUR MAXSAT.

Twierdzenie 4.2

OCCUR MAXSAT jest -zupełny.

Dowód

Redukcja przebiega tak jak poprzednio. Dla zmiennej występującej razy w formule tworzymy zmiennych dla nowej formuły . Następnie przepisujemy wszystkie klauzule z do , zamieniając każde wystąpienie na inną ze zmiennych .

Potem konstruujemy -elementowy ekspander o stopniu wierzchołków . Etykietujemy wierzchołki grafu zmiennymi . Dla każdej krawędzi w grafie dodajemy do formuły klauzule i .

Do formuły dodaliśmy nowych klauzul. Zauważmy, że jeżeli wartościowanie zmiennych jest zgodne, to wszystkie dodane klauzule są spełnione. Jeżeli natomiast zbiór jest wartościowany odwrotnie niż , to własności ekspanedera gwarantują, że co najmniej klauzul jest niespełnionych.

Zauważmy, że skonstruowana formuła jest formułą problemu OCCUR MAXSAT. Każda ze zmiennych występuje dokładnie w klauzulach odpowiadających krawędziom ekspandera i w jednej klazuli pochodzącej z formuły .

Pokażemy teraz, że każde rozwiązanie optymalne dla formuły musi być zgodne na zmiennych . Weźmy zatem jakieś rozwiązanie optymalne, które przyporządkowuje różne wartości zmiennym . Niech 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 ? Zmienne te występują w klauzulach z formuły , które po tej zamianie mogłyby przestać być spełnione. Stracilibyśmy zatem najwyżej spełnionych klauzul. Z drugiej jednak strony zyskalibyśmy 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 było klauzul, to było co najwyżej wystąpień zmiennych, a w formule w związku z tym jest co najwyżej klauzul. Przypomnijmy, że optimum dla problemu MAXSAT wynosi co najmniej i możemy w związku z tym ustalić współczynnik dla L-redukcji na .

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

Pokazaliśmy L-redukcję -zupełnego problemu MAXSAT do OCCUR MAXSAT, co pozwala nam stwierdzić, że ten drugi problem również jest -zupełny.

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 OCCUR MAXSAT jest -zupełny. Skorzystamy z tego faktu, nie przedstawiając szczegółowego dowodu.

Wykorzystamy teraz problem OCCUR MAXSAT do pokazania -zupełności kilku problemów.

Lemat 4.3

Problemy -NODE COVER i -INDEPENDENT SET są -zupełne.

Dowód

Przypomnijmy, że już pokazaliśmy, że problemy -NODE COVER i -INDEPENDENT SET należą do klasy . Teraz wystarczy przypomnieć sobie zwykłą redukcję problemu 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 OCCUR MAXSAT stworzy graf, w którym stopień wierzchołka będzie ograniczony przez .

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

Uzasadniliśmy, że problem -NODE COVER jest -zupełny. Znamy już L-redukcję -NODE COVER do -INDEPENDENT SET. Pozwala nam to stwierdzić -zupełność problemu -INDEPENDENT SET.

End of proof.gif

Wniosek 4.4

Problemy NODE COVER i INDEPENDENT SET są -trudne.

Lemat 4.5

Problemy OCCUR MAXSAT i MAX NAESAT są -zupełne.

Dowód

Żeby pokazać -zupełność problemu OCCUR MAXSAT, skonstruujemy L-redukcję problemu -INDEPENDENT SET. Mając dany graf , konstruujemy formułę, tworząc następujące klauzule:

  • dla każdego wierzchołka .
  • dla każdej krawędzi .

Skonstruowana formuła ma klauzul. Możemy tę liczbę ograniczyć przez . Z kolei, przypominając analizę L-redukcji -INDEPENDENT SET do -NODE COVER, możemy stwierdzić, że rozmiar maksymalnego zbioru niezależnego wynosi co najmniej . Zatem współczynnik L-redukcji ustalamy na .

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 OCCUR MAXSAT 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 .

L-redukcja problemu MAXSAT do MAX NAESAT przebiega w bardzo łatwy sposób. Do każdej klauzuli dopisujemy wystąpienie nowej zmiennej . 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 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 i .

End of proof.gif

Ćwiczenie 4.6

MAX CUT jest -zupełny.

Wskazówka
Rozwiązanie


Ćwiczenie 4.7

OCCUR MAX NAESAT jest -zupełny.

Wskazówka
Rozwiązanie

Problem INDEPENDENT SET

Wiemy już, że problem INDEPENDENT SET jest -trudny, gdyż jego zawężenia są zupełne dla tej klasy. Oznacza to, że o ile , 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 . Wiedziano, że problem INDEPENDENT SET albo można aproksymować dowolnie dobrze, albo w ogóle. Dopiero twierdzenie 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 i {grafem iloczynowym} oznaczamy graf o wierzchołkach i krawędziach:

  • dla i dowolnych i .
  • dla .
Rys.9.2. Graf iloczynowy

Przykład 5.2

Konstrukcja odpowiada "włożeniu" grafu w każdy wierzchołek grafu . Nam będzie potrzebna tylko konstrukcja .

Lemat 5.3

W grafie istnieje zbiór niezależny rozmiaru wtedy i tylko wtedy, gdy w istnieje zbiór niezależny rozmiaru .

Dowód

Jeżeli jest zbiorem niezależnym rozmiaru w , to zbiór jest zbiorem niezależnym rozmiaru w grafie .

Jeżeli natomiast jest zbiorem niezależnym rozmiaru w , to każdy ze zbiorów:

  • ,
  • dla każdego ,

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

End of proof.gif

Twierdzenie 5.4

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

Dowód

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

Skorzystamy teraz z tego, że dla ciąg ma granicę w nieskończoności równą . Schemat PTAS powstaje w związku z tym przez zastosowanie algorytmu dla grafu , dla odpowiednio dużego . Jeżeli chcemy osiągnąć -aproksymację, to otrzymamy następujące oszacowanie na :

End of proof.gif

Ćwiczenie 5.5

Algorytm zachłanny dla problemu INDEPENDENT SET.

Pokazaliśmy, że o ile , to nie ma algorytmu -aproksymacyjnego dla INDEPENDENT SET. Pokaż, że algorytm zachłanny nie jest algorytmem -aproksymacyjnym.

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

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

Definicja 6.1

Język należy do klasy , jeżeli istnieje weryfikator , który dla wejścia długości bitów działa w czasie wielomianowym od , korzysta z bitów losowych i bitów świadka oraz:

  • Dla istnieje świadek taki, że akceptuje z prawdopodobieństwem większym lub równym .
  • Dla , dla każdego świadka , akceptuje z prawdopodobieństwem mniejszym od .

Zauważmy, że wcześniejsza definicja odpowiada teraz . Dość łatwo można uzyskać równość dla każdej stałej . Działanie weryfikatora klasy można powtórzyć razy, otrzymując weryfikator klasy . Dlatego naprawdę ciekawe rezultaty otrzymamy dopiero, kiedy dopuścimy, aby i mogły zależeć od .

Szczególnie interesującym wydaje się ograniczenie błędnej akceptacji w sposób odwrotnie proporcjonalny do rozmiaru wejścia. Równość otrzymujemy tą samą metodą. Możemy przecież powtórzyć działanie weryfikatora razy, wykorzystując 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

.

Dowód

Przypomnijmy, że pokazaliśmy, że i w związku z tym zawieranie nie wymaga dalszego komentarza.

Aby pokazać, że , 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:

End of proof.gif

Twierdzenie 6.3

Jeżeli graf jest ekspanderem o wierzchołkach i jest podzbiorem wierzchołków takim, że , to istnieje stała taka, że prawdopodobieństwo następującego zdarzenia:

"Wszystkie wierzchołki losowej ścieżki długości należą do ",

jest mniejsze od .

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

Niech będzie -ograniczonym weryfikatorem dla języka . używa podczas obliczenia co najwyżej bitów losowych i bitów świadka.

Skonstruujemy weryfikator klasy dla języka .

Algorytm 6.4 [Weryfikator klasy ]


1. Skonstruuj ekspander o wierzchołkach.
Każdy wierzchołek jest etykietowany ciągiem bitów.

2. Używając bitów losowych, wygeneruj ścieżkę losową w grafie .

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

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

Podany algorytm weryfikatora działa w czasie wielomianowym od , używa bitów losowych do ustalenia ścieżki , a podczas wszystkich symulacji weryfikatora używane jest w sumie bitów świadka.

Jeżeli słowo , to istnieje świadek , przy którym prawdopodobieństwo akceptacji weryfikatora wynosi . Dla tego samego świadka weryfikator także dokona akceptacji z prawdopodobieństwem .

Jeżeli natomiast , to dla każdego świadka prawdopodobieństwo akceptacji przez weryfikator jest mniejsze od . Oznaczmy przez wierzchołki , 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 w całości znajduje się w jest mniejsze od . Jeżeli ścieżka wyjdzie poza zbiór , to weryfikator odrzuci słowo. W związku z tym prawdopodobieństwo błędnej akceptacji jest mniejsze od .

Ć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 . Pokaż, że dla dowolnego zachodzi:

Wskazówka
Rozwiązanie

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 , to dla problemu CLIQUE nie istnieje algorytm -aproksymacyjny, gdzie dla pewnego .

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

Dowód będzie w swojej konstrukcji przypominał dowód nieaproksymowalności MAXSAT w oparciu o twierdzenie . Z tą różnicą, że tym razem wykorzystamy weryfikator klasy . Gdybyśmy wykorzystali charakteryzację , uzyskalibyśmy podobny rezultat mówiący o tym, że nie istnieje algorytm -aproksymacyjny dla problemu CLIQUE.

Twierdzenie 7.1

Istnieją stałe i takie, że dla każdej instancji problem SAT można skonstruować graf o wierzchołkach taki, że dla problemu CLIQUE:

  • , gdy SAT,
  • , gdy SAT.

Dowód

Niech będzie weryfikatorem klasy dla języka SAT. podczas działania używa co najwyżej bitów losowych i bitów świadka.

Konstruujemy graf , gdzie wierzchołki odpowiadają parom ciągów bitowych długości i . Takich par jest oczywiście . Wierzchołek reprezentujący ciągi i oznaczamy przez i intuicyjnie będzie on odpowiadał sytuacji, kiedy ciągiem losowym był , a odczytane bity świadka tworzą ciąg .

Wierzchołek jest akceptujący, gdy weryfikator akceptuje formułę przy ciągu bitów losowych równym i odczytach świadka równych .

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

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

Jeżeli natomiast formuła nie jest spełnialna, a jest kliką w grafie , to musi zachodzić . Gdyby było przeciwnie, to zauważmy, że klika generuje pewnego świadka , 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 , to wierzchołki odpowiadają różnym ciągom losowym i przy każdym z nich weryfikator akceptuje formułę .

Zatem przy świadku prawdopodobieństwo zaakceptowania formuły jest większe lub równe . Jest to niemożliwe ze względu na to, że formuła nie jest spełnialna, a ma prawdopodbieństwo błędnej akceptacji mniejsze od .

Zatem rozmiar największej kliki w grafie skonstruowanym dla niespełnialnej formuły musi być mniejszy od .

End of proof.gif

Wniosek 7.2

Istnieje stała taka, że o ile , to nie istnieje algorytm -aproksymacyjny dla problemu CLIQUE.

Dowód

Ustalmy dla stałej z poprzedniego twierdzenia. Niech będzie algorytmem -aproksymacyjnym dla problemu CLIQUE.

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

Jeżeli jest spełnialna, to i algorytm znajdzie rozwiązanie o rozmiarze większym lub równym:

Jeżeli natomiast nie jest spełnialna to rozmiar każdego rozwiązania jest mniejszy od .

Możemy zatem przy pomocy algorytmu rozstrzygnąć -zupełny problem SAT, co jest sprzeczne z założeniem .

End of proof.gif

Wniosek 7.3

Istnieje stała taka, że o ile , to nie istnieje algorytm -aproksymacyjny dla problemu INDEPENDENT SET.

Testy końcowe