Les preuves sont la base de toutes les mathématiques. Une preuve est une affirmation ou un théorème que vous essayez de prouver et une séquence de dérivations faites pour déclarer que le théorème a été prouvé. par exemple. tous les angles d’un triangle totalisant 180° peuvent être vérifiés indépendamment par n’importe qui (vérificateur).
Preuves
Le prouveur —> fait une réclamation —> le vérificateur choisit —> accepter/rejeter
(Le prouveur et le vérificateur sont des algorithmes)
En informatique, le terme pour les preuves effectivement vérifiables est les preuves NP. Ces preuves courtes peuvent être vérifiées en temps polynomial. L’idée générale étant “Il existe une solution à un théorème et elle est transmise au vérificateur pour la vérifier”
Dans un langage NP = deux conditions doivent être remplies :
Intégralité : les affirmations vraies seront acceptées par le vérificateur (permet aux preuves honnêtes d’atteindre la vérification)
Solidité : les fausses affirmations n’auront aucune preuve (pour toute stratégie de preuve de triche, ils seront incapables de prouver l’exactitude d’une affirmation incorrecte).
Interaction : plutôt que de simplement lire la preuve, le vérificateur s’engage avec un prouveur dans les deux sens sur plusieurs séries de messages.
Aléatoire : les demandes du vérificateur au prouveur sont aléatoires et le prouveur doit être en mesure de répondre correctement à chacune.
En utilisant l’interaction et le hasard ensemble, il est possible de prouver une affirmation à un vérificateur aveugle en temps polynomial probabiliste (PPT).
Les preuves interactives peuvent-elles vérifier efficacement plus que les preuves NP ?