MIP z wydajnymi dowodami

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?

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

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 * .