Interaktive Beweise für coNP

9

Ich versuche, interaktive Beweissysteme zu verstehen und habe das folgende Problem als Übung ausprobiert. Wir wissen, dass und , also kommen Sie mit (leicht verständlichen) interaktiven Proof-Systemen für ? $PH \subseteq PSPACE$ $IP=PSPACE$ $PH$

Ein interaktives für ist trivial, aber ich habe selbst für kein interaktives . Kennen Sie ein explizites interaktives Proof-System (mit explizit meine ich, ohne die Route zu ) für ? $NP$ $coNP$ $IP=PSPACE$ $coNP$

complexity-theory interactive-proof-systems Shitikanth
quelle

Können Sie klarstellen, was Sie unter interaktivem Proofsystem verstehen? Für diejenigen, die mit dem Begriff nicht vertraut sind.

jmite

3

Sogar die Einbeziehung von erfordert nicht relativierende Techniken. Der einzige bekannte Weg, dies zu zeigen, ist die Algebrisierung, wie in Yuvals Antwort. Das Anzeigen von ist lediglich eine geringfügige technische Änderung dieses Beweises.

c o N P \subseteq I P

$coNP \subseteq IP$

I P = P S P A C E

$IP=PSPACE$

SDCVVC

2

@sdcvvc, ich denke, Ihr Kommentar ist es wert, als Antwort veröffentlicht zu werden. Es erklärt, warum es keine so einfachen Beispiele wie für NP gibt.

Kaveh

6

Wikipedia skizziert ein solches Beispiel. Betrachten Sie das coNP-vollständige Problem UNSAT: Wenn ein CNF für Variablen gegeben ist, möchten wir den Prüfer davon überzeugen, dass nicht erfüllbar ist. Wir arithmetisieren zu einem Polynom und wählen eine große Primzahl . Sei $\varphi$ $n$ $\varphi$ $\varphi$ $p$ $q$ Das Protokoll läuft wie folgt ab:

p (x_{1}, \dots, x_{k}) = \sum_{x_{k + 1} = 0}^{1} \dots \sum_{x_{n} = 0}^{1} p (x_{1}, \dots, x_{n}) .

$p(x_1,\ldots,x_k) = \sum_{x_{k+1}=0}^1 \cdots \sum_{x_n=0}^1 p(x_1,\ldots,x_n).$

Der Prüfer sendet dem Prüfer eine Primzahl , und diese überprüft, ob eine Primzahl ist. $q \in (2^n,2^{n+1})$ $q$
Der Prüfer sendet den Prüfer . Der Prüfer überprüft, ob , und sendet dem Prüfer ein zufälliges . $p(z) \in \mathbb{Z}_q[z]$ $p(0) + p(1) = 0$ $r_1$
Der Prüfer sendet den Prüfer . Der Prüfer überprüft, ob , und sendet dem Prüfer ein zufälliges . $p(r_1,z) \in \mathbb{Z}_q[z]$ $p(r_1,0) + p(r_1,1) = p(r_1)$ $r_2$
Schließlich erhält der Prüfer und überprüft, ob er den richtigen Wert hat, indem er direkt auswertet . $p(r_1,\ldots,r_n) \in \mathbb{Z}_q$ $p$

Da der Grad von im Vergleich zu klein ist, wird der Prüfer sie wahrscheinlich fangen, wenn der Prüfer betrügt (siehe Wikipedia für den Beweis, oder erarbeiten Sie es selbst mit dem Schwartz-Zippel-Lemma). $p$ $q$

Yuval Filmus
quelle

-1

Graph-Nicht-Isomorphismus bei Beweisen, die nichts als ihre Gültigkeit oder alle Sprachen in NP liefern, haben Zero-Knowledge-Beweise , Goldreich, Micali und Wigderson, JACM, 1991.

$G_1, G_2$ $i \in \{1,2\}$ $G_i$ $b \in \{1,2\}$

$b=i$

Solidität: Für isomorphe Graphen gibt der Prüfer mit Wahrscheinlichkeit die richtige Antwort $\frac{1}{2}$

Vadym Fedyukovych
quelle

Bitte verweisen Sie ordnungsgemäß auf einen von Experten geprüften Artikel und eine kurze Zusammenfassung des Inhalts. Links wie der von Ihnen bereitgestellte neigen dazu, zu brechen, und dann enthält Ihre Antwort keine Informationen.

Raphael

Interaktive Beweise für coNP

Antworten: