Wyjątkowe domysły dotyczące gier

Nierozwiązany problem w informatyce :

Czy hipoteza Unique Games jest prawdziwa?

(więcej nierozwiązanych problemów w informatyce)

W teorii złożoności obliczeniowej hipoteza gier unikalnych (często określana jako UGC ) to hipoteza postawiona przez Subhasha Khota w 2002 r. Hipoteza postuluje, że problem określenia przybliżonej wartości pewnego rodzaju gry, znanej jako gra unikatowa , ma NP-trudną złożoność obliczeniową . Ma szerokie zastosowanie w teorii aproksymacji twardości . Jeśli hipoteza gier unikalnych jest prawdziwa i P ≠ NP, to dla wielu ważnych problemów nie tylko niemożliwe jest uzyskanie dokładnego rozwiązania w czas wielomianowy (jak postulowano w problemie P versus NP ), ale także niemożliwe jest uzyskanie dobrego przybliżenia czasu wielomianowego. Problemy, dla których taki wynik nieprzybliżenia byłby spełniony, obejmują problemy spełnienia ograniczeń , które pojawiają się w wielu różnych dyscyplinach.

Przypuszczenie jest niezwykłe, ponieważ świat akademicki wydaje się mniej więcej równo podzielony co do tego, czy jest prawdziwy, czy nie.

preparaty

Przypuszczenie o unikalnych grach można sformułować na wiele równoważnych sposobów.

Unikalna okładka etykiety

Poniższe sformułowanie jedynej hipotezy gier jest często używane w twardości aproksymacji . Hipoteza postuluje NP-twardość następującego problemu obietnicy znanego jako okładka etykiety z ograniczeniami unikalnymi . Dla każdej krawędzi kolory na dwóch wierzchołkach są ograniczone do określonych uporządkowanych par. Unikalne ograniczenia oznaczają, że dla każdej krawędzi żadna z uporządkowanych par nie ma tego samego koloru dla tego samego węzła.

Oznacza to, że przypadek okładki etykiety z unikalnymi ograniczeniami na alfabet o rozmiarze k można przedstawić jako graf skierowany wraz ze zbiorem permutacji π _e : [ k ] → [ k ], po jednej dla każdej krawędzi e grafu. Przypisanie do egzemplarza okładki etykiety nadaje każdemu wierzchołkowi G wartość ze zbioru [ k ] = {1, 2, ... k}, często nazywaną „kolorami”.

• 

  Przykład unikalnej okładki etykiety. Czterem wierzchołkom można przypisać kolory czerwony, niebieski i zielony, spełniając jednocześnie ograniczenia na każdej krawędzi.

• 

  Rozwiązanie dla unikalnej instancji okładki etykiety.

Takie przypadki są silnie ograniczone w tym sensie, że kolor wierzchołka jednoznacznie definiuje kolory jego sąsiadów, a zatem dla całego połączonego komponentu. Tak więc, jeśli instancja wejściowa dopuszcza prawidłowe przypisanie, to takie przypisanie można skutecznie znaleźć, iterując po wszystkich kolorach pojedynczego węzła. W szczególności problem decydowania, czy dana instancja dopuszcza satysfakcjonujące przypisanie, można rozwiązać w czasie wielomianowym.

• 

  Przykład unikalnej okładki etykiety, która nie pozwala na satysfakcjonujące przypisanie.

• 

  Przypisanie, które spełnia wszystkie krawędzie z wyjątkiem grubej krawędzi. Zatem ta instancja ma wartość 3/4.

Wartość unikatowego wystąpienia okładki etykiety to ułamek ograniczeń, które można spełnić przez dowolne przypisanie. W przypadku spełniających przypadków ta wartość wynosi 1 i jest łatwa do znalezienia. Z drugiej strony wydaje się, że bardzo trudno jest określić wartość gry niesatysfakcjonującej, nawet w przybliżeniu. Przypuszczenie o unikalnych grach formalizuje tę trudność.

Bardziej formalnie, problem ( c , s )-gap label-cover z ograniczeniami unikalnymi to następujący problem obietnicy ( L _tak , L _nie ):

• L _tak = { G : Jakieś zadanie spełnia co najmniej c -ułamek ograniczeń w G }
• L _nie = { G : Każde przypisanie spełnia co najwyżej s -ułamek ograniczeń w G }

gdzie G jest przykładem problemu okładki etykiety z ograniczeniami unikalnymi.

Hipoteza o unikalnych grach mówi, że dla każdej wystarczająco małej pary stałych ε , δ > 0 istnieje stała k taka, że ​​(1 − δ , ε )-przerwa problem okładki etykiety z unikalnymi ograniczeniami na alfabet o rozmiarze k jest NP -twarde _

Zamiast wykresów problem okładki etykiety można sformułować w postaci równań liniowych. Załóżmy na przykład, że mamy układ równań liniowych nad liczbami całkowitymi modulo 7:

${\ Displaystyle {\ rozpocząć {wyrównane} x_ {1} i \ odpowiednik 2 \ cdot x_ {2} {\ pmod {7}}, \\ x_ {2} i \ odpowiednik 4 \ cdot x_ {5} {\ pmod {7}},\\&{}\ \ \vdots \\x_{1}&\equiv 2\cdot x_{7}{\pmod {7}}.\end{aligned}}}$

Jest to przykład problemu okładki etykiety z unikalnymi ograniczeniami. Na przykład pierwsze równanie odpowiada permutacji π _{(1, 2)} , gdzie π _{(1, 2)} ( x ₁ ) = 2 x ₂ modulo 7.

Systemy dowodowe z dwoma dowodami

Wyjątkowa gra to szczególny przypadek gry z dwoma dowodami w jednej rundzie (2P1R) . W jednej rundzie gry z dwoma dowodami bierze udział dwóch graczy (znanych również jako dowodzący) i sędzia. Sędzia wysyła każdemu graczowi pytanie wylosowane ze znanego rozkładu prawdopodobieństwa , a każdy z graczy musi wysłać odpowiedź. Odpowiedzi pochodzą z zestawu o stałym rozmiarze. Grę określa predykat, który zależy od zadawanych graczom pytań i udzielanych przez nich odpowiedzi.

Gracze mogą wcześniej ustalić strategię, choć nie mogą się ze sobą komunikować w trakcie gry. Gracze wygrywają, jeśli predykat jest spełniony przez ich pytania i odpowiedzi.

Gra z dwoma dowodami w jednej rundzie nazywana jest grą wyjątkową , jeśli na każde pytanie i każdą odpowiedź pierwszego gracza jest dokładnie jedna odpowiedź drugiego gracza, która skutkuje wygraną graczy i odwrotnie. Wartość gry to maksymalne prawdopodobieństwo wygranej dla graczy przy wszystkich strategiach.

Hipoteza unikalnych gier mówi, że dla każdej wystarczająco małej pary stałych ε , δ > 0 istnieje stała k taka, że ​​następujący problem obietnicy ( L _tak , L _nie ) jest NP-trudny :

• L _tak = { G : wartość G wynosi co najmniej 1 − δ}
• L _nie = { G : wartość G wynosi co najwyżej ε}

gdzie G jest wyjątkową grą, której odpowiedzi pochodzą ze zbioru o rozmiarze k .

Dowody sprawdzalne probabilistycznie

Alternatywnie, hipoteza unikalnych gier postuluje istnienie pewnego typu probabilistycznie sprawdzalnego dowodu dla problemów w NP.

Unikalną grę można postrzegać jako szczególny rodzaj nieadaptacyjnego probabilistycznie sprawdzalnego dowodu o złożoności zapytania 2, gdzie dla każdej pary możliwych zapytań weryfikatora i każdej możliwej odpowiedzi na pierwsze zapytanie istnieje dokładnie jedna możliwa odpowiedź na drugie zapytanie, które sprawia, że ​​weryfikator akceptuje i odwrotnie.

$, że ​​dla$ wystarczająco małej pary stałych istnieje stała taka, że ​​każdy problem w NP ma probabilistycznie sprawdzalny dowód na $K}$ alfabet $przypadkowości$ z $,$ solidnością i $złożonością$${\ Displaystyle O (\ log n)},$ która jest wyjątkową grą.

Znaczenie

Wyniki przybliżenia przy założeniu, że P ≠ NP w porównaniu z UGC

Problem	Poli.-czas ok.	Twardość NP	Twardość UG
Maks. 2 sob	${\ Displaystyle 0,940 \ kropki}$	${\ Displaystyle 0,954 \ kropki + \ varepsilon}$	${\ Displaystyle 0,9439 \ kropki + \ varepsilon}$
Maksymalne cięcie	${\ Displaystyle 0,878... \ kropki}$	${\ Displaystyle {\ tfrac {16} {17}} + \ varepsilon \ około 0,941}$	${\ Displaystyle 0,878 \ kropki + \ varepsilon}$
Minimalne pokrycie wierzchołków	${\ Displaystyle 2}$	${\ Displaystyle {\ sqrt {2}} - \ varepsilon}$	${\ Displaystyle 2- \ varepsilon}$
Zestaw łuku sprzężenia zwrotnego	${\ Displaystyle O (\ log n \ log \ log n)}$	${\ Displaystyle 1,360 \ kropki - \ varepsilon}$	Wszystkie stałe
Maksymalny podgraf acykliczny	${\ Displaystyle {\ tfrac {1} {2}} + \ Omega (1 / {\ sqrt {\ Delta}})}$	${\ Displaystyle {\ tfrac {65} {66}}}$	${\ Displaystyle {\ tfrac {1} {2}} + \ varepsilon}$
Między	${\ Displaystyle {\ tfrac {1} {3}}}$	${\ Displaystyle {\ tfrac {47} {48}}}$	${\ Displaystyle {\ tfrac {1} {3}} + \ varepsilon}$

Kilka bardzo naturalnych, z natury interesujących stwierdzeń na temat takich rzeczy, jak głosowanie i piany, właśnie wyskoczyło z badania UGC… Nawet jeśli UGC okaże się fałszywe, zainspirowało wiele interesujących badań matematycznych.

— Ryan O’Donnell,

Wyjątkowa hipoteza gier została wprowadzona przez Subhasha Khota w 2002 roku w celu poczynienia postępów w pewnych kwestiach w teorii twardości aproksymacji .

Prawdziwość hipotezy o unikalnych grach implikowałaby optymalność wielu znanych algorytmów aproksymacji (zakładając P ≠ NP). Na przykład współczynnik aproksymacji osiągnięty przez algorytm Goemansa i Williamsona do aproksymacji maksymalnego cięcia na wykresie jest optymalny w obrębie dowolnej stałej addytywnej, przy założeniu hipotezy o unikalnych grach i P ≠ NP.

Lista wyników, z których wynika hipoteza o unikalnych grach, jest pokazana w sąsiedniej tabeli wraz z odpowiednimi najlepszymi wynikami dla słabszego założenia P ≠ NP. Stała lub oznacza, że ​​wynik zachodzi dla każdej $Displaystyle$$\ varepsilon$ w do rozmiaru problemu) ściśle większej lub mniejszej niż do + $} odpowiednio styl wyświetlania c}$ .

Dyskusja i alternatywy

Obecnie nie ma zgody co do prawdziwości przypuszczenia o wyjątkowych grach. Niektóre silniejsze formy przypuszczenia zostały obalone.

Inna postać przypuszczenia postuluje, że rozróżnienie przypadku, gdy wartość unikalnej gry jest co najmniej $1-\ delta}$$displaystyle$ od przypadku, gdy wartość jest co najwyżej niemożliwe. dla algorytmów wielomianowych (ale być może nie NP-trudnych). Ta forma przypuszczenia byłaby nadal przydatna do zastosowań w przybliżeniu twardości.

Stała $NP$ powyższych sformułowaniach przypuszczenia jest konieczna, chyba że P = Jeśli wymóg jednoznaczności zostanie usunięty, odpowiednie stwierdzenie jest prawdziwe na podstawie twierdzenia o równoległych powtórzeniach, nawet gdy ${\ displaystyle \ delta = 0}$ .

Marek Karpiński i Warren Schudy skonstruowali liniowe schematy aproksymacji czasu dla gęstych instancji problemu gier unikalnych.

W 2008 roku Prasad Raghavendra wykazał, że jeśli hipoteza gier unikalnych jest prawdziwa, to dla każdego problemu spełnienia ograniczeń najlepszy współczynnik przybliżenia jest określony przez pewną prostą, półokreśloną instancję programowania , która jest w szczególności wielomianem.

W 2010 roku Prasad Raghavendra i David Steurer zdefiniowali problem rozszerzania małych zbiorów i przypuszczali, że jest on NP-trudny . To przypuszczenie implikuje przypuszczenie o unikalnych grach. Zostało również wykorzystane do udowodnienia dużej twardości wyników aproksymacji dla znalezienia pełnych podgrafów dwudzielnych .

W 2010 roku Sanjeev Arora , Boaz Barak i David Steurer znaleźli algorytm aproksymacji czasu podwykładniczego dla problemu z unikalnymi grami.

W 2012 roku wykazano, że odróżnienie instancji o wartości co najwyżej od instancji o wartości co najmniej ${\ Displaystyle {$$\ tfrac$ jest NP-trudne.

W 2018 roku, po serii artykułów, udowodniono słabszą wersję hipotezy, zwaną hipotezą 2-2 gier. W pewnym sensie dowodzi to „połowy” pierwotnego przypuszczenia. Poprawia to również najlepiej znaną lukę w unikalnej okładce etykiety: NP-trudno jest odróżnić wystąpienia o wartości co najwyżej $wystąpień$ o wartości co najmniej ${\ displaystyle {\ tfrac {1} {2} }}}$ .

Notatki

• Khot, Subhash (2010), „O przypuszczeniach o wyjątkowych grach”, Proc. 25. konferencja IEEE na temat złożoności obliczeniowej (PDF) , s. 99–121, doi : 10.1109/CCC.2010.19 .