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?
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 * .
źródło