Co wiadomo na temat interaktywnych proofów z wieloma dowodami z krótkimi wiadomościami?

14

Beigi, Shor i Watrous mają bardzo ładny artykuł na temat mocy kwantowych dowodów interaktywnych z krótkimi wiadomościami. Rozważają trzy warianty „krótkich wiadomości”, a konkretny, na którym mi zależy, to ich drugi wariant, w którym można wysłać dowolną liczbę wiadomości, ale całkowita długość wiadomości musi być logarytmiczna. W szczególności pokazują, że takie interaktywne systemy dowodowe mają ekspresyjną moc BQP.

Chcę wiedzieć, czy istnieją analogiczne wyniki dla ustawienia wielu przysłów, zarówno dla weryfikatorów klasycznych, jak i kwantowych. Czy znane są jakiekolwiek nietrywialne wyniki złożoności dla interaktywnych dowodów wielozadaniowych, w których całkowita długość wszystkich wiadomości jest ograniczona logarytmicznie do rozmiaru problemu?

Joe Fitzsimons
źródło
5
Jeśli dowódom zezwala się na dzielenie wcześniejszego splątania o dowolnym rozmiarze, to nie wiadomo, że klasa znajduje się w klasie R rozstrzygalnych problemów (nawet gdy weryfikator jest klasyczny). Wykazanie, że twoja klasa jest zawarta w R, jest równoznaczne z pokazaniem, że MIP * znajduje się w R. Jeśli chodzi o dolną granicę, nie sądzę, aby znane było coś lepszego niż odpowiednik single-prover.
Tsuyoshi Ito
@TsuyoshiIto: Nawet w przypadku krótkich klasycznych wiadomości?
Joe Fitzsimons,
1
„Decydowalne” nie zależy od wielkości, więc możesz użyć argumentu wypełniania, aby pokazać równoważność.
Tsuyoshi Ito
1
Ach tak, rozumiem. To miła obserwacja i odpowiada na moje pytanie w zakresie kwantowym. Jednak w przypadku klasycznego przypadku jest on koniecznie zawarty w NEXP. Masz pomysł, czy są tam jakieś wyniki?
Joe Fitzsimons,
Wygląda na to, że coś trzeba przekonwertować na odpowiedź
Suresh Venkat

Odpowiedzi:

11

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

Tsuyoshi Ito
źródło
Świetnie, dzięki Tsuyoshi, właśnie tego szukałem.
Joe Fitzsimons,
4
Tak więc ostatnim otwartym klasycznym problemem jest decyzja, czy ta klasa złożoności jest równa MA.
Peter Shor
@Peter: Tak. Przez jakiś czas zastanawiałem się nad tym problemem, ale nie mam odpowiedzi.
Tsuyoshi Ito
2
Znalazłem moją starą notatkę, stwierdzającą, że jednoobrotowe systemy MIP sprawdzające O (1) z doskonałą kompletnością z komunikacją O (log n) raczej nie zawierają MA. Dodałem ten argument do odpowiedzi w wersji 3.
Tsuyoshi Ito,
Aby uzyskać więcej informacji na temat wyroczni, w odniesieniu do której BPP⊈P ^ NP wspomniane w tej odpowiedzi, zobacz to pytanie .
Tsuyoshi Ito,