Krajobraz interaktywnych systemów dowodowych

Moje pierwsze pytanie dotyczy tego, czy charakterystyka interaktywnego systemu dowodu jest znana dla wszystkich klasycznych klas złożoności. Nazwałbym P, NP, PSPACE, EXP, NEXP, EXPSPACE, funkcje rekurencyjne i rekurencyjnie wyliczalne klasyczne (między innymi). W szczególności, czy charakterystyka interaktywnego systemu dowodu znana jest z funkcji rekurencyjnych i rekurencyjnie wyliczalnych?

Wiem tylko, że IP = PSPACE i że MIP = NEXPTIME. Przez „know” rozumiem definicje obiektów po obu stronach równości i prawdopodobnie rozumiem równość.

Moje drugie pytanie dotyczy tego, czy istnieje graficzne podsumowanie różnych rodzajów interaktywnych systemów dowodowych i charakteryzujących je klas złożoności.

W szczególności chciałbym nawiązać do postaci podobnej do obrazu charakteryzującego złożoność opisu Immermana .

W słynnej ankiecie Condon'a można znaleźć wiele charakterystyk (szczególnie dotyczących weryfikatorów ograniczonych przestrzenią): złożoność interaktywnych systemów dowodzenia ograniczonych przestrzenią .

Oto lista niektórych z nich:

• , gdzie 2pfa (weryfikator) jest dwukierunkowym probabilistycznym automatem skończonym.$\mathsf{RE} = \mathsf{weak\mbox{-}IP(2pfa)}$

• , gdzie pfa (weryfikator) jest jednokierunkowym probabilistycznym automatem skończonym oddziałującym z dwoma dowodami.$\mathsf{R} = \mathsf{2IP(pfa)}$

• .$\mathsf{NEXP} = \mathsf{2IP(pfa,poly\mbox{-}time)}$

• .$\mathsf{PSPACE} = \mathsf{IP(log\mbox{-}space,poly\mbox{-}time)}$

• .$\mathsf{NP} = \mathsf{oneway\mbox{-}IP(log\mbox{-}space,poly\mbox{-}time)} = \mathsf{oneway\mbox{-}IP(log\mbox{-}space,log\mbox{-}random\mbox{-}bits)}$

• , E X P = A M ( p o l y - s p a c e ) itp.$\mathsf{P} = \mathsf{AM(log\mbox{-}space)}$$\mathsf{EXP} = \mathsf{AM(poly\mbox{-}space)}$

Niektóre najnowsze (głównie kwantowe) wyniki:

• przezYakaryilmaz, gdzie 2qcfa (weryfikatora) jest dwukierunkowy skończony automat o stałym rozmiarze kwantową rejestru.$\mathsf{RE} = \mathsf{weak\mbox{-}AM(2qcfa)}$

• wedługYakaryilmaza, gdzie 2pca (były weryfikator) jest dwukierunkowym probabilistycznym automatem skończonym z jednym licznikiem, a 2qca (drugi weryfikator) to dwa -drogowy automat skończony kwantowy z jednym licznikiem.$\mathsf{R} = \mathsf{IP(2pca)} = \mathsf{AM(2qca)}$

• Ito, Kobayashi i Watrous podali nową charakterystykę opartą na kwantowych interaktywnych systemach dowodowych z podwójnie wykładniczo niewielką luką w prawdopodobieństwie akceptacji między przypadkami kompletności i solidności.$\mathsf{EXP}$

• autorstwaJaina, Ji, Upadhyay iWatrousa, gdzie QIP jest kwantową generalizacją systemów IP.$\mathsf{PSPACE} = \mathsf{QIP(poly\mbox{-}time)}$

• $\mathsf{NP}$

• $\mathsf{NL} = \mathsf{weak\mbox{-}oneway\mbox{-}IP(2pfa,constant\mbox{-}random\mbox{-}bits)}$

NP jest często scharakteryzowany jako system dowodu, w którym przysłowie wysyła dowód długości wielomianu do deterministycznego weryfikatora czasu wielomianowego, po którym nie następuje interakcja. Klasę języków wymiennych rekurencyjnie można scharakteryzować podobnie, zastępując „wielomian” słowem „skończony”.

Ponadto, ponieważ klasa języków rekurencyjnych R jest przecięciem RE i coRE, można scharakteryzować R jako system dowodowy, w którym wszechmocny władca może przekonać skończonego weryfikatora czasu zarówno pod względem ważności poprawnych roszczeń, jak i nieważności Fałszywe roszczenia.

Klasa EXP ma charakterystykę w kategoriach systemu dowodowego z „konkurującymi dowodami” - tj. Systemu dowodowego, w którym istnieje osoba, która próbuje przekonać weryfikatora, że ​​twierdzenie jest prawdziwe, i osoba, która próbuje przekonać weryfikatora, że roszczenie jest fałszywe. Więcej informacji można znaleźć w artykule „Krótkie gry” Feige i Kilian.