Całkowicie klasyczny przypadek (MIP)
Jeśli weryfikator jest klasyczny i nie ma wcześniejszego splątania między dowodami, twoja klasa zawiera BPP∪NP i jest zawarta w MA .
To banalne, że BPP jest dolną granicą. Aby pokazać, że klasa zawiera NP, weź pod uwagę standardowy dwustronny, dowodzący, interaktywny system próbny z 3-kolorowością z doskonałym kompletnością i błędem 1–1 / poli. Jeśli chcesz zredukować błąd dźwięku do stałej, połącz to z twierdzeniem PCP.
Jeśli chodzi o górną granicę, obowiązuje następująca silniejsza instrukcja: MIP z zastrzeżeniem, że łączna długość wiadomości od weryfikatora do każdego dowodu wynosi O (log n ) jest równa MA. Wynika to z faktu, że strategię każdego przysłowia można opisać ciągiem wielomianu.
Co ciekawe, kolejna górna granica istnieje, gdy system ma doskonałą kompletność. Mianowicie, wielozadaniowe interaktywne systemy proof z doskonałą kompletnością z O (log n ) całkowitą komunikacją rozpoznają co najwyżej P NP [log] , i jest to możliwe nawet wtedy, gdy dopuszczamy nieograniczony błąd głośności. Aby udowodnić to w przypadku dwóch dowodzenie, niech x s być połączeniem wszystkich odpowiedzi udzielonych przez pierwszy Prover kiedy połączeniem do pierwszego Prover wszystkich pytań jest s i definiują y t analogicznie dla drugiego Prover. Zostać zaakceptowane przez weryfikatora z pewnością, zmienne te x s i r Tmusi spełniać pewne ograniczenia i pamiętać, że jest to 2CSP. Istnieje co najwyżej poli ( n ) wybór krotek ( s , t , x s , y t ) i dla każdego wyboru możemy użyć wyroczni NP, aby sprawdzić, czy weryfikator odrzuca tę krotkę. Dlatego za pomocą wyroczni NP możemy wymienić wszystkie ograniczenia na zmiennych x s i y tw czasie wielomianowym. Na koniec ponownie używamy wyroczni NP, aby sprawdzić, czy istnieje przypisanie do tych zmiennych, które spełnia wszystkie ograniczenia. Chociaż algorytm ten wykorzystuje wielomianowo NP oracle wiele razy, wszystkie zapytania oprócz ostatniego można wykonać równolegle, a zatem można je przekonwertować na algorytm P NP [log] . Przypadek więcej niż dwóch dowodów jest analogiczny.
Ta górna granica implikuje, że chociaż każdy system MA może zostać przekształcony w jeden z doskonałą kompletnością, nie możemy mieć nadziei na wielozadaniowy interaktywny system proof z doskonałą kompletnością z komunikacją O (log n ), chyba że MA unlessP NP [log] . Nie wiem, jak mało prawdopodobne jest włączenie MA⊆P NP [log] , ale po prostu zauważam, że Zoologia Złożoności stwierdza, że istnieje wyrocznia, w stosunku do której BPP⊈ P NP (a zatem wyraźnie MA⊈P NP [log] ).
(W przypadku pojedynczego przysłowia Twierdzenie 2 Goldreicha i Håstada [GH98] sugeruje, że IP o całkowitej długości komunikatu O (log n ) bitów jest równy BPP.)
Dodał . Konieczna i wystarczająca charakterystyka jest następująca.
Aby wyjaśnić tę charakterystykę, potrzebujemy wariantu pojęcia redukowalności Karpa (redukcja wielokrotna w czasie wielomianowym). W przypadku dwóch problemów decyzyjnych A i B , powiedzmy, że A jest FP BPP- redukowalne do B (wiem, to okropna nazwa), gdy istnieje deterministyczna maszyna Turinga M z wielomianowym czasem z dostępem do wyroczni BPP, która odwzorowuje tak- instancje do instancji typu „tak” i instancji typu „bez instancji”, w których zezwalamy na „wyrozumiały” dostęp do wyroczni (co oznacza, że Mmoże wykonać zapytanie do wyroczni BPP dotyczące instancji, która nie spełnia obietnicy problemu BPP, w którym to przypadku wyrocznia zwraca dowolnie tak lub nie). Następnie można udowodnić, że następujące warunki dla problemu A są równoważne.
(i) A ma wielozadaniowy interaktywny system proof z komunikacją O (log n ) i dwustronnym błędem ograniczonym.
(ii) A ma dwustronny, interaktywny system proof proof z komunikacją O (log n ), wykładniczo małym błędem kompletności i stałym błędem dźwiękowym.
(iii) A oznacza FP BPP, która może rozwiązać problem NP.
(Pomysł dowodu: Implikacja (ii) ⇒ (i) jest trywialna. Implikacja (i) ⇒ (iii) można uzyskać w podobny sposób jak powyższy dowód w przypadku błędu jednostronnego. Implikacja (iii) ⇒ (ii ) wynika z twierdzenia PCP, ponieważ klasa problemów spełniających warunek (ii) jest zamknięta w ramach FP BPP - redukowalność.)
Klasyczny weryfikator z uwikłanymi dowodami (MIP *)
Następnie rozważ przypadek z klasycznym weryfikatorem i splątanymi dowodami. W takim przypadku klasa z ograniczonym błędem ponownie zawiera BPP∪NP.
Kempe, Kobayashi, Matsumoto, Toner i Vidick [KKMTV11] pokazuje, że każdy problem w NP ma interaktywny dowód próbny z trzema dowodami, z doskonałym błędem kompletności i poprawności 1–1 / poli, gdzie całkowita długość wiadomości wynosi O ( log n ) bitów, a solidność trzyma się przed zaplątanymi dowodami. Dlatego MIP * o całkowitej długości komunikatu O (log n ) bitach i ograniczonym błędzie zawiera NP. Późniejszy wynik Ito, Kobayashiego i Matsumoto [IKM09] (bezwstydna wtyczka) zmniejsza liczbę testerów z trzech do dwóch. Przypadek ciągłej solidności jest otwarty na szczycie mojej wiedzy.
Nie wiadomo, czy MIP * z całkowitą długością komunikatu O (log n ) bitów jest zawarty w klasie R rozstrzygalnych problemów, czy nie, i to pytanie jest równoważne z tym, czy MIP * ⊆R (inny otwarty problem) przez argument dopełniający.
Bibliografia
[GH98] Oded Goldreich i Johan Håstad. O złożoności interaktywnych dowodów z ograniczoną komunikacją. Information Processing Letters , 67 (4): 205–214, sierpień 1998. http://dx.doi.org/10.1016/S0020-0190%2898%2900116-1
[IKM09] Tsuyoshi Ito, Hirotada Kobayashi i Keiji Matsumoto. Orularyzacja i dwie rundy jedna runda interaktywne dowody przeciwko nielokalnym strategiom. Postępowanie: dwudziesty czwarty roczne IEEE Conference on Computational Complexity (KKK 2009) , 217-228, lipca 2009. http://dx.doi.org/10.1109/CCC.2009.22
[KKMTV11] Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner i Thomas Vidick. Gry uwikłane są trudne do przybliżenia. SIAM Journal on Computing , 40 (3): 848–877, 2011. http://dx.doi.org/10.1137/090751293