## [Compression de Preuves](/fr/node/59944) Définition Techniques et transformations visant à réduire la taille, la longueur ou la complexité structurelle d'une preuve tout en préservant sa correction et sa vérifiabilité. ## Principe Principe La compression supprime des sous-preuves redondantes, fusionne des dérivations identiques en sous-structures partagées (DAGification), introduit des lemmes ou abstractions, et exploite des stratégies de normalisation ou d'introduction/élimination de coupures pour conserver la validité tout en réduisant la représentation. ## Démonstration Démonstration Une preuve longue de style séquentielle contenant des dérivations répétées pour le même lemme intermédiaire est transformée en graphe acyclique dirigé qui partage la sous-preuve commune une seule fois, réduisant le nombre total de nœuds et accélérant la vérification par des assistants de preuve. ## Mauvaise application Mauvaise application Une compression trop agressive qui supprime la structure traçable ou remplace des étapes par des hypothèses implicites peut rendre la preuve non vérifiable par des vérificateurs standard ou réduire son interprétabilité humaine, et l'introduction de lemmes non démontrés détruit la correction. ## Conséquence Conséquence Réduit les coûts de stockage et de transmission, accélère la vérification automatique et la relecture des preuves, et met souvent au jour une structure de haut niveau (lemmes et raisonnement modulaire) utile pour la maintenance et la compréhension. ## Inversion Inversion Expansion de preuve : dérouler toutes les macro-étapes et intégrer tous les lemmes en étapes primitives, ce qui augmente la taille et peut masquer la structure malgré une explicitation maximale. ## Limite Limite S'applique aux preuves formelles dans des systèmes déductifs où les transformations préservent la validité logique et la vérifiabilité ; n'inclut pas les résumés avec perte qui sacrifient la vérifiabilité ni les esquisses informelles omettant complètement les dérivations. ## Tension sémantique Tension sémantique Tension entre compression maximale pour l'efficacité machine et préservation d'une structure de preuve lisible et inspectable par l'humain ; tension aussi avec les certificats de preuve qui priorisent la vérifiabilité sur la taille minimale. ## Synthèse Synthèse La compression de preuves recouvre des transformations correctes — partage de sous-dérivations, extraction de lemmes, normalisation — qui réduisent la taille de la représentation d'une preuve tout en maintenant sa correction et sa vérifiabilité, conciliant efficience machine et traçabilité.