Système de preuve interactive

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

En théorie de la complexité, un système de preuve interactive est une machine abstraite qui modélise un échange de messages entre deux partis. Ces deux partis, un prouveur et un vérificateur, communiquent afin de démonter le fait qu'une chaîne de caractères appartient ou pas à un langage formel donné. Le prouveur a des ressources calculatoires illimitées tandis que le vérificateur a des ressources limitées. Les deux interagissent aussi longtemps qu'il faut au vérificateur pour trouver une réponse au problème et être convaincu qu'elle est la bonne.

Deux propriétés doivent être satisfaites :

consistance (completeness) : si le fournisseur de preuve et le vérificateur suivent le protocole alors le vérificateur doit toujours accepter la preuve
solidité (soundness) : si la proposition est fausse, aucun fournisseur de preuve malicieux ne peut convaincre un vérificateur « honnête » que la proposition est vraie et ceci avec une forte probabilité