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 .

cc.complexity-theory big-picture interactive-proofs

— Vijay D.
źródło

Co już wiesz

— Tsuyoshi Ito

W interaktywnym systemie dowodowym istnieje więcej niż 1 parametr zmienny: jaka jest moc weryfikatora, jaka jest moc dowodu, jaki rodzaj (i ilość) komunikacji jest dozwolony, czy mają one wspólną losowość, czy weryfikator muszę przeczytać całą wiadomość od provera, czy ma on losowy dostęp do wiadomości itp.

— Robin Kothari,

Po dłuższym zastanowieniu nie sądzę, że mogę odpowiednio odpowiedzieć na twoje pytanie, ponieważ interaktywny system dowodowy jest szerokim tematem w teorii złożoności obliczeniowej. Warto sprawdzić rozdział 9 złożoności obliczeniowej: perspektywa koncepcyjna Goldreicha lub rozdziały 8 i 11 złożoności obliczeniowej: współczesne podejście Arory i Baraka.

— Tsuyoshi Ito

@VijayD: Tak, to część problemu. W opisowych charakterystykach złożoności istnieje jedna zmienna (logika), więc gdy przechodzisz wyżej z FO do SO, przechodzisz z AC0 do PH itp. W interaktywnych systemach dowodowych jest tak wiele zmiennych, że nie jest jasne, że fajna można narysować krajobraz.

— Robin Kothari,

Nie jestem pewien, czy to pytanie jest wystarczająco dobrze określone. Odpowiedź jest trywialna: każdą klasę można „scharakteryzować” jako „interaktywny dowód”, w którym przysłowie w zasadzie niewiele robi, a weryfikator jest wystarczająco potężny. Interesującą rzeczą w wynikach IP = PSPACE i MIP = NEXP (i PCP [O (\ log n), O (1)] = NP) jest to, że weryfikator jest zaskakująco słaby.

— Sasho Nikolov,

Odpowiedzi:

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)}$
, 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)}$

— Abuzer Yakaryilmaz
źródło

Dzięki! Właśnie tego chciałem. Brakowało mi sposobu na poprawienie mojego pytania, które było zbyt niejasne dla ekspertów, i cieszę się, że zrozumiałeś mój zamiar.

— Vijay D

Dlaczego więc nie oznaczysz tego jako najlepszej odpowiedzi?

— Cem Powiedz

Bo kto wie, co przyniesie jutro? Chciałbym zdecydować tydzień lub 10 dni po opublikowaniu.

— Vijay D

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.

— Lub Meir
źródło