Preuves interactives pour coNP

9

J'essaie de comprendre les systèmes de preuve interactifs et j'ai essayé le problème suivant comme exercice. Nous savons que et , alors imaginez des systèmes de preuve interactifs (faciles à comprendre) pour ? $PH \subseteq PSPACE$ $IP=PSPACE$ $PH$

Un système de preuve interactif pour est trivial, mais je n'a pas pu obtenir un système de preuve interactive , même pour . Connaissez-vous un système de preuve interactif explicite (par explicite, je veux dire sans passer par la route ) pour ? $NP$ $coNP$ $IP=PSPACE$ $coNP$

complexity-theory interactive-proof-systems Shitikanth
la source

Pourriez-vous clarifier ce que vous entendez par système de preuve interactif? Pour ceux qui ne connaissent pas le terme.

jmite

3

Même l'inclusion

nécessite des techniques non relativisantes; la seule façon connue de le montrer est par algèbre, comme dans la réponse de Yuval. Montrer

n'est qu'une légère modification technique de cette preuve.

c o N P \subseteq I P

$coNP \subseteq IP$

I P = P S P A C E

$IP=PSPACE$

sdcvvc

2

@sdcvvc, je pense que votre commentaire mérite d'être publié comme réponse. Il explique pourquoi il n'y a pas d'exemples aussi simples que ceux pour NP.

Kaveh

6

Wikipedia donne un tel exemple. Considérons le problème UNNAT complet de coNP: étant donné un CNF sur variables, nous voulons convaincre le vérificateur que n'est pas satisfaisable. Nous arithmétisons en un polynôme et choisissons un grand premier . Soit $\varphi$ $n$ $\varphi$ $\varphi$ $p$ $q$ Le protocole se déroule comme suit:

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).$

Le prouveur envoie au vérificateur un premier , et ce dernier vérifie que est premier. $q \in (2^n,2^{n+1})$ $q$
Le prouveur envoie le vérificateur . Le vérificateur vérifie que et envoie au prouveur un aléatoire . $p(z) \in \mathbb{Z}_q[z]$ $p(0) + p(1) = 0$ $r_1$
Le prouveur envoie le vérificateur . Le vérificateur vérifie que et envoie au prouveur un aléatoire . $p(r_1,z) \in \mathbb{Z}_q[z]$ $p(r_1,0) + p(r_1,1) = p(r_1)$ $r_2$
$p(r_1,\ldots,r_n) \in \mathbb{Z}_q$ $p$

$p$ $q$

Yuval Filmus
la source

-1

Graphique de non-isomorphisme aux preuves qui ne produisent rien d'autre que leur validité ou toutes les langues dans NP ont des preuves de connaissance zéro , Goldreich, Micali et Wigderson, JACM, 1991.

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

$b=i$

$\frac{1}{2}$

Vadym Fedyukovych
la source

Veuillez donner une référence appropriée à un article évalué par les pairs et un bref résumé du contenu. Des liens comme celui que vous fournissez ont tendance à se briser, puis votre réponse ne contient aucune information.

Raphael

Preuves interactives pour coNP

Réponses: