Landschaft interaktiver Beweissysteme

Meine erste Frage ist, ob für alle klassischen Komplexitätsklassen eine interaktive Proofsystemcharakterisierung bekannt ist. Ich würde unter anderem P, NP, PSPACE, EXP, NEXP, EXPSPACE, rekursive und rekursiv aufzählbare Funktionen als klassisch bezeichnen. Speziell, ist eine interaktive Beweissystemcharakterisierung für rekursive und rekursiv aufzählbare Funktionen bekannt?

Ich weiß nur, dass IP = PSPACE und MIP = NEXPTIME. Unter "wissen" verstehe ich die Definitionen von Objekten auf beiden Seiten der Gleichheit und verstehe möglicherweise die Gleichheit.

Meine zweite Frage ist, ob es eine grafische Zusammenfassung der verschiedenen Arten interaktiver Beweissysteme und der von ihnen charakterisierten Komplexitätsklassen gibt.

Insbesondere möchte ich auf eine Abbildung verweisen, die Immermans Bild der Beschreibung von Komplexitätscharakterisierungen ähnelt .

cc.complexity-theory big-picture interactive-proofs Vijay D
quelle

Was weißt du schon?

Tsuyoshi Ito

In einem interaktiven Beweissystem gibt es mehr als einen variablen Parameter: Welche Macht hat der Prüfer, welche Macht hat der Prüfer, welche Art (und Menge) von Kommunikation ist zulässig, haben sie eine vorab geteilte Zufälligkeit, hat der Prüfer muss die gesamte Nachricht vom Prüfer lesen oder hat er zufälligen Zugriff auf die Nachricht usw.

Robin Kothari

Nach einigem Nachdenken glaube ich nicht, dass ich Ihre Frage angemessen beantworten kann, da interaktives Beweissystem ein weites Thema in der Theorie der rechnerischen Komplexität ist. Vielleicht möchten Sie Kapitel 9 von Computational Complexity: A Conceptual Perspective von Goldreich oder Kapitel 8 und 11 von Computational Complexity: A Modern Approach von Arora und Barak überprüfen .

Tsuyoshi Ito

@ VijayD: Ja, das ist ein Teil des Problems. In beschreibenden Komplexitätscharakterisierungen gibt es eine Variable (die Logik). Wenn Sie also von FO nach SO aufsteigen, gehen Sie von AC0 nach PH usw. In interaktiven Proofsystemen gibt es so viele Variablen, dass es nicht klar ist, dass es nett ist Landschaft kann gezeichnet werden.

Robin Kothari

Ich bin mir nicht sicher, ob diese Frage genau genug ist. Es gibt eine triviale Antwort: Jede Klasse kann als "interaktiver Beweis" "charakterisiert" werden, bei dem der Prüfer im Grunde nicht viel tut und der Prüfer mächtig genug ist. Das Interessante an den Ergebnissen IP = PSPACE und MIP = NEXP (und PCP [O (\ log n), O (1)] = NP) ist, dass der Verifizierer überraschend schwach ist.

Sasho Nikolov

Antworten:

In Condons berühmter Umfrage finden Sie viele Charakterisierungen (insbesondere für weltraumgebundene Verifizierer): Die Komplexität weltraumgebundener interaktiver Beweissysteme .

Hier ist eine Liste von einigen von ihnen:

, wobei 2pfa (der Verifizierer) ein probabilistischer endlicher Zwei-Wege-Automat ist. $\mathsf{RE} = \mathsf{weak\mbox{-}IP(2pfa)}$
, wobei pfa (der Verifizierer) ein in eine Richtung wahrscheinlicher endlicher Automat ist, der mit zwei Beweisen interagiert. $\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)}$
, und etc. $\mathsf{P} = \mathsf{AM(log\mbox{-}space)}$ $\mathsf{EXP} = \mathsf{AM(poly\mbox{-}space)}$

Einige neuere (meist quantenmässige) Ergebnisse:

$\mathsf{RE} = \mathsf{weak\mbox{-}AM(2qcfa)}$
$\mathsf{R} = \mathsf{IP(2pca)} = \mathsf{AM(2qca)}$
$\mathsf{EXP}$
$\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
quelle

Vielen Dank! Genau das wollte ich. Ich wusste nicht, wie ich meine für Experten zu vage gestellte Frage verbessern sollte, und bin froh, dass Sie meine Absicht verstanden haben.

Vijay D

Warum kennst du es dann nicht als die beste Antwort?

Cem Say

Denn wer weiß was morgen bringt? Ich würde gerne eine Woche oder 10 Tage nach dem Posten entscheiden.

Vijay D

NP wird häufig als Beweissystem charakterisiert, bei dem der Prüfer einen Beweis mit polynomischer Länge an einen deterministischen Polynomzeitprüfer sendet und nach dem keine Wechselwirkung stattfindet. Die Klasse der rekursiv aufzählbaren Sprachen kann auf ähnliche Weise charakterisiert werden, indem "Polynom" durch "endlich" ersetzt wird.

Da die Klasse der rekursiven Sprachen R die Schnittstelle von RE und coRE ist, können Sie R auch als Beweissystem charakterisieren, in dem ein allmächtiger Prüfer einen endlichen Zeitprüfer sowohl von der Gültigkeit korrekter Behauptungen als auch von der Ungültigkeit von überzeugen kann falsche Behauptungen.

Die Klasse EXP hat eine Charakterisierung in Bezug auf ein Beweissystem mit "konkurrierenden Prüfern" - dh ein Beweissystem, in dem es einen Prüfer gibt, der versucht, den Prüfer davon zu überzeugen, dass die Behauptung wahr ist, und einen Verweigerer, der versucht, den Prüfer davon zu überzeugen Die Behauptung ist falsch. Weitere Informationen finden Sie in der Veröffentlichung "Making games short" von Feige und Kilian.

Oder Meir
quelle