MIP z wydajnymi dowodami

17

Powszechnie wiadomo, że zestawem języków posiadających dwuczłonowy interaktywny system proof, w którym weryfikator działa w czasie wielomianowym (MIP), jest NEXP. Ale czy znane są granice mocy takich interaktywnych dowodów, gdy dowody mają ograniczoną moc? Na przykład, jaka jest klasa języków, które dopuszczają dowody interaktywne z dwoma dowodami z dowodami czasu wielomianowego?

Mówiąc dokładniej, powiedzmy, że na wejściu x pozwalam dowódcom na dowolny czas wstępnego obliczenia, ale gdy rozpocznie się interakcja z weryfikatorem, ograniczają się one do korzystania z przestrzeni wielomianowej (w tym przechowywania wyników dowolnego wstępnego obliczenia) i czasu wielomianowego obliczyć odpowiedzi na pytanie weryfikatora. Załóżmy również, że te ograniczenia czasowe i przestrzenne są stałym wielomianem długości pytań, które zostaną wysłane przez weryfikatora (zamiast długości x), aby wykluczyć bardziej trywialne rozwiązanie, w którym weryfikator jakoś wyczerpałby się przestrzeń provera związana jest zadawaniem wielomianowo więcej pytań.

Oczywiście wystarcza to dla NP. Co z PSPACE? Gdyby istniała tylko przestrzeń ograniczona, mogliby to zrobić, ale co z czasem? Czy są jakieś ciekawe wyniki w tym kierunku?

Interesują mnie również inne ograniczenia, które można wziąć pod uwagę przy dowodzeniu. Jednym z nich byłaby ilość weryfikatora komunikacji -> weryfikator, który, jak sądzę, został dokładnie zbadany w kontekście PCP. Jakie są inne interesujące ograniczenia?

Tomasz
źródło

Odpowiedzi:

17

Wygląda na to, że ta klasa byłaby dokładnie MA. Świadkiem mogą być wyniki przetwarzania wstępnego (które ma wielkość wielomianową). Probabilistyczna procedura weryfikacji polegałaby wówczas na symulacji protokołu, w tym na wielu dowodach (które są wielomianowe, biorąc pod uwagę wyniki przetwarzania wstępnego).

Russell Impagliazzo

Russell Impagliazzo
źródło
Dobra uwaga, dzięki. Mówiąc bardziej ogólnie, zastanawiałem się, w jaki sposób wiele osób przeprowadzających testy może udowodnić, że języki, które nie są powiązane z czasem T (modulo etap wstępnego przetwarzania), weryfikatorowi wieloczasowego, a twoja odpowiedź pokazuje, że nigdy nie będzie to więcej niż odpowiadające MA (T), z weryfikatorem czasu T. Ale jak to się ma do niektórych klas weryfikatorów wieloczasowych? Powiedz, że jeśli dowódcom wolno teraz używać PSPACE, nadal mogą udowodnić NEXP. Czy można je jeszcze bardziej ograniczyć i nadal udowodnić to samo?
Thomas
2

Jeśli dwa dowody są ograniczone do dwóch maszyn BQP, które nie komunikują się ze sobą, ale dzielą splątanie, podczas gdy weryfikator jest w BPP, wówczas dwa dowody mogą udowodnić dowolny język w BQP klasycznemu weryfikatorowi za pomocą Universal Blind Quantum Computation protokół Broadbent, Fitzsimons i Kashefi. Ten protokół został również wykorzystany przez tych samych autorów jako blok konstrukcyjny, aby pokazać QMIP = MIP * .

Martin Schwarz
źródło
1
Dzięki Martin, nie chciałem wspominać o mojej własnej pracy.
Joe Fitzsimons