IP (complexité)

Une sous-classe de IP est celle des preuves interactives déterministes, qui est similaire à IP mais utilise un vérificateur déterministe (c’est-à-dire sans aléatoire). Cette classe NP.

Une définition équivalente de IP remplace la condition que l’interaction réussie avec une grande probabilité sur les chaines du langage par la condition qu’elle réussisse toujours :

${\displaystyle w\in L\Rightarrow \Pr[V\leftrightarrow P{\text{ accepts }}w]=1}$

Ce critère apparemment plus fort de « complétude parfaite » ne change en fait pas la classe IP, puisque tout langage avec un système de preuves interactives a un système de preuves interactives avec complétude parfaite[6].

En 1988, Goldwasser et al. ont créé un système de preuves interactives encore plus puissant basé sur IP et appelé MIP, pour lequel il y a deux prouveurs indépendants. Les deux prouveurs ne peuvent pas communiquer une fois que le vérificateur a commencé à leur envoyer des messages. Tout comme il est plus facile de savoir si un criminel ment si lui et son partenaire sont interrogés dans des salles séparées, il est plus facile de détecter un prouveur malicieux essayant de tromper le vérificateur s’il y a un autre prouveur qui peut confirmer cela. En fait, c’est tellement utile que Babai, Fortnow, et Lund ont pu prouver que MIP = NEXPTIME, la classe des problèmes résolubles par une machine non déterministe en temps exponentiel, une classe très grande. De plus, tous les langages dans NP ont une preuve sans connaissance dans un système MIP, même sans hypothèse additionnelle ; c’est un résultat connu pour IP seulement en admettant l’existence de fonctions à sens unique.

IPP (IP non bornée) est une variante de IP où l’on remplace le vérificateur BPP par un vérificateur PP. Plus précisément, on modifie les conditions de complétude et de correction ainsi :

• Complétude : si une chaine est dans le langage, le vérificateur honête sera convaincu de cela avec une probabilité au moins 1/2 ;
• Correction: si la chaine n’est pas dans le langage, aucun prouveur ne pourra convaincre l’honnête vérificateur qu’elle l’est avec une probabilité supérieure 1/2.

Bien que IPP soit égale à PSPACE, les protocoles IPP se comportent d’une façon assez différente de ceux de IP vis-à-vis des oracles : IPP=PSPACE vis-à-vis de tous les oracles, alors que IP ≠ PSPACE pour certains oracles oracles[7].

QIP est une version d’IP où l’on remplace le vérificateur BPP par un vérificateur BQP, où BQP est la classe des problèmes décidables par ordinateurs quantiques en temps polynomial. Les messages sont composés de qubits[8].

Kitaev and Watrous montre que QIP est inclus dans EXPTIME[9]. En 2009, Jain, Ji, Upadhyay, et Watrous démontre que QIP est en fait aussi égale à PSPACE[10], ce qui implique que cela n’ajoute pas de puissance au protocole.

Alors qu’IPPP et QIP donnent plus de puissance au vérificateur, un système compIP (système de preuves IP avec compétition) affaiblit la condition de complétude d’une façon qui affaiblit le prouveur :

• Complétude: si la chaine est dans le langage L, l’honnête vérificateur sera convaincu de cela par un prouveur honnête avec probabilité au moins 2/3. De plus, le prouveur doit le faire probabilitistiquement en temps polynomial en ayant un oracle sur le langage L.

Principalement, cela fait du prouveur une machine BPP avec un oracle sur le langage, mais seulement dans le cas de complétude, pas dans le cas de la correction. L’idée est que si un langage est dans compIP, alors le prouver interactivement est d’une certaine façon aussi facile que de le décider. Avec l’oracle, le prouveur peut facilement résoudre le problème, mais sa puissance limitée lui rend bien plus difficile la tâche de convaincre le vérificateur de quoi que ce soit. En fait, compIP n’est même pas connu ou considéré comme contenant NP.

Cependant, un tel système peut résoudre certains problèmes que l’on pense être difficiles. Paradoxalement, même si on ne pense pas qu’un tel système soit capable de résoudre tout NP, il peut facilement résoudre tous les problèmes NP-complets grâce à leur auto-réductibilité. Cela vient du fait que si le langage L n’est pas NP-difficile, le prouveur est très fortement limité dans sa puissance (puisqu’il ne peut plus décider tous les problèmes NP avec son oracle).

De plus, le problème de nonisomorphisme de graphe (qui est un problème classique dans IP) est lui aussi dans compIP, puisque la seule opération difficile dont peut se contenter le prouveur est le test d’isomorphisme, qu’il peut utiliser un oracle pour résoudre. Les problèmes la résiduosité quadratique et de l’isomorphisme de graphe sont aussi dans compIP[11]. Notons que la non-résiduosité quadratique (QNR) est probablement un problème plus simple que l’isomorphisme de graphe puisque QNR est dans UP intersect co-UP[12].