IP (complexité)
En informatique théorique, et notamment en théorie de la complexité, la classe IP (une abréviation pour Interactive Polynomial time, c'est-à-dire « interactif en temps polynomial ») est la classe des problèmes de décision qui peuvent être résolus par un système de preuve interactive. Le concept de système de preuve interactive a été introduit pour la première fois en 1985 par Shafi Goldwasser, Silvio Micali et Charles Rackoff[1],[2].
Système de preuve interactive[modifier | modifier le code]
Un système de preuve interactive est composé de deux machines :
- le prouveur, noté P qui présente une proposition de preuve qu'une chaîne donnée w appartient à un certain langage formel. On suppose que le prouveur dispose de capacités de calcul et d'espace infinies ;
- le vérificateur, noté V, qui teste que la preuve présentée est correcte. Le vérificateur est une machine de Turing probabiliste opérant en temps polynomial qui a accès à une chaîne binaire aléatoire dont la longueur est polynomiale en fonction de la longueur de w.
Les deux machines échangent un nombre polynomial de messages, et quand l'interaction est terminée, le vérificateur décide si w est dans le langage ou non, avec une probabilité d'erreur d'au plus 1/3 (par conséquent, tout langage de la classe BPP est dans IP, puisque le vérificateur peut simplement ignorer le prouveur et prendre lui-même la décision).
.svg)
Définition[modifier | modifier le code]
Un langage est dans IP s'il existe un vérificateur et un prouveur tels que pour tout mot , et pour tout prouveur :
- (complétude)
- (correction)
![{\displaystyle w\in L\Rightarrow \Pr[(V,P){\text{ accepte }}w]\geq 2/3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a6b1516d9b7a43c61897181adcb6bdc39bd0e313)
![{\displaystyle w\notin L\Rightarrow \Pr[(V,Q){\text{ accepte }}w]\leq 1/3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a08b84594af06df44248f2d4704e86df038383b0)
Le protocole Arthur-Merlin, introduit par László Babai[3], est semblable, sauf que le nombre de tours d'interaction est borné par une constante plutôt que par un polynôme.
Goldwasser et al.[1] ont montré que les protocoles à tirage publique, qui sont les protocoles où les nombres aléatoires utilisés par le vérificateur sont fournis par le prouveur en même temps que les propositions de preuves, ne sont pas plus puissants que les protocoles à tirage aléatoire privé : en effet, au plus deux tours d'interaction supplémentaires sont requis pour répliquer l'effet d'un tirage privé, et inversement, le vérificateur peut toujours envoyer au prouveur les résultats de son tirage privé. Ceci montre que les deux types de protocoles sont équivalents.
Égalité avec PSPACE[modifier | modifier le code]
La classe IP est égale à PSPACE. Ce résultat est dû à Shamir[4], basé sur le travail de Lund, Fortnow, Farloff, Nisan[5].
C’est un théorème important de la complexité algorithmique, qui démontre qu’un système de preuves interactives peut être utilisé pour décider si une chaine fait partie d’un langage en temps polynomial, même si la preuve traditionnelle dans PSPACE peut être exponentiellement longue.
Variantes[modifier | modifier le code]
Il existe un certain nombre de variantes d’IP qui modifient légèrement la définition du système de preuves interactives. Nous résumons ici les plus connues.
dIP[modifier | modifier le code]
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.
Complétude parfaite[modifier | modifier le code]
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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d464012603434f6806813c89b36e504a9e9b1bb2)
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].
MIP[modifier | modifier le code]
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[modifier | modifier le code]
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[modifier | modifier le code]
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.
compIP[modifier | modifier le code]
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].
Notes et références[modifier | modifier le code]
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « IP (complexity) » (voir la liste des auteurs).
- Goldwasser, Micali et Rackoff 1985.
- Goldwasser, Micali et Rackoff 1989.
- Babai 1985.
- Adi Shamir, « IP = PSPACE », J. ACM, vol. 39, no 4, , p. 869–877 (ISSN 0004-5411, DOI 10.1145/146585.146609, lire en ligne, consulté le )
- Carsten Lund, Lance Fortnow, Howard Karloff et Noam Nisan, « Algebraic Methods for Interactive Proof Systems », J. ACM, vol. 39, no 4, , p. 859–868 (ISSN 0004-5411, DOI 10.1145/146585.146605, lire en ligne, consulté le )
- Martin Furer, Oded Goldreich, Yishay Mansour, Michael Sipser, Stathis Zachos. On Completeness and Soundness in Interactive Proof Systems. Advances in Computing Research: A Research Annual, 5:429-442. 1989.
- R. Chang, B. Chor, Oded Goldreich, J. Hartmanis, J. Håstad, D. Ranjan, et P. Rohatgi. The random oracle hypothesis is false. Journal of Computer and System Sciences, 49(1):24-39. 1994.
- J. Watrous. PSPACE has constant-round quantum interactive proof systems. Proceedings of IEEE FOCS'99, pp. 112-119. 1999.
- A. Kitaev et J. Watrous. « Parallelization, amplification, and exponential time simulation of quantum interactive proof systems »(Archive.org • Wikiwix • Archive.is • Google • Que faire ?). Proceedings of ACM STOC'2000, pp. 608-617. 2000.
- (en) Auteur inconnu, « QIP = PSPACE », ..
- (en) Shafi Goldwasser et Mihir Bellare, « The Complexity of Decision versus Search » [PDF], SIAM Journal on Computing, Volume 23, No 1. Février 1994.
- Cai JY, Threlfall RA, 2004. "A note on quadratic residuosity and UP." Information Processing Letters 92(3): 127-131.
Bibliographie[modifier | modifier le code]
- László Babai, « Trading group theory for randomness », dans Proceedings of Seventeenth ACM Symposium on the Theory of Computation (STOC), Providence (Rhodes Island), ACM, (lire en ligne).
- Shafi Goldwasser, Silvio Micali et Charles Rackoff, « The knowledge complexity of interactive proof-systems », dans Proceedings of Seventeenth ACM Symposium on the Theory of Computation (STOC), Providence (Rhodes Island), ACM, (lire en ligne), p. 291–304. Résumé détaillé.
- Shafi Goldwasser, Silvio Micali et Charles Rackoff, « The knowledge complexity of interactive proof systems », SIAM Journal on Computing, Philadelphie, Society for Industrial and Applied Mathematics, vol. 18, no 1, , p. 186–208 (ISSN 1095-7111, DOI 10.1137/0218012, lire en ligne)
