IP (complexité)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 interacive a été introduit pour la premièrère fois en 1985 par Shafi Goldwasser, Silvio Micali, and Charles Rackoff[1],[2].

Un système de preuve interactive consiste en deux machines de Turing, l'une appelée le prouveur et notée P qui présente une proposition de preuve qu'une chaîne donnéew appartient à un certain langage formel, et l'autre appelée un vérificateur et notée V, qui teste que la preuve présentée est correcte. On suppose que le prouveur dispose de capacités de calcul et d'espace infinies, alors que le vérificateur est une machine 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 doit décider si w est dans le langage ou non, avec seulement une possibilité d'erreur de 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).

Définition[modifier | modifier le code]

Un langage L est dans IP s'il existe un vérificateur V et un prouveur P tels que pour tout mot w, et pour tout prouveur Q:

w \in L \Rightarrow \Pr[(V,P)\text{ accepte }w] \ge 2/3
w \notin L \Rightarrow \Pr[ (V,Q)\text{ accepte }w] \le 1/3

Le protocole d'Arthur–Merlin (en), 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 polynome.

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.

Résultat principal[modifier | modifier le code]

Le résultat principal concernant cette classe de complexité est que IP = PSPACE.

Notes et références[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,‎ 1985 (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,‎ 1985 (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, Philadelphia, Society for Industrial and Applied Mathematics, vol. 18, no 1,‎ 1989, p. 186–208 (ISSN 1095-7111, lien DOI?, lire en ligne)

Liens externes[modifier | modifier le code]