## [Extraction de Témoins](/fr/node/60864) Définition Le processus consistant à produire un témoin concret, un contre-exemple ou une assignation satisfaisante à partir d'un objet de preuve, d'une réfutation, d'un modèle ou d'une trace de solveur afin que les assertions existentielles ou les résultats de satisfiabilité soient attestés par des artefacts explicites. ## Principe Principe Parcourir l'objet de preuve ou la trace du solveur et traduire les dérivations abstraites en données constructives en interprétant les introductions existentielles, les constructions de modèle ou les composants de contre-modèle ; préserver la correction de sorte que le témoin extrait satisfasse bien la formule d'origine ou en démontre la fausseté. ## Démonstration Démonstration À partir d'une exécution d'un solveur SAT qui trouve une assignation satisfaisante, l'extraction de témoin produit l'assignation booléenne concrète (par ex. x1=true, x2=false). À partir d'une preuve de ∃x P(x) dans un système constructif, l'extraction calcule un terme spécifique t et une dérivation de P(t). À partir d'un solveur SMT renvoyant unsat avec une preuve par résolution, une boucle de raffinage guidée par contre-exemple peut extraire un interpolant ou une assignation concrète utilisée pour raffiner une abstraction. ## Mauvaise application Mauvaise application Tenter d'extraire un témoin constructif d'une preuve d'existence classique qui utilise des principes non constructifs sans réinterprétation constructive conduit à un échec ou à des artefacts fallacieux ; extraire une assignation partielle ou non vérifiée et la traiter comme preuve de satisfaisabilité est non fondé. ## Conséquence Conséquence Une extraction de témoin fiable transforme les résultats abstraits d'un solveur en artefacts tangibles pour vérification indépendante, certificats ou synthèse de programmes ; elle soutient le raffinage d'abstractions guidé par contre-exemples et renforce la confiance en permettant la validation indépendante d'assertions existentielles. ## Inversion Inversion Le contraire est une preuve ou un résultat de solveur opaque qui annonce l'existence ou la satisfaisabilité sans fournir de témoin concret (p. ex. un oracle UNSAT boîte noire ou une preuve non constructive rédigée par un humain), ce qui nuit à la reproductibilité et à la vérification automatisée. ## Limite Limite Nécessite un objet de preuve, un modèle ou une trace de solveur suffisamment détaillé qui encode de l'information constructive ; exclut les affirmations provenant de solveurs ne fournissant que des réponses oui/non sans trace, les sorties statistiques ou les preuves informelles dépourvues de structure formelle exploitable pour l'extraction. ## Tension sémantique Tension sémantique Il existe une tension entre l'extraction de témoins minimaux (les plus petits ou simples) et de témoins canoniques ou reproductibles ; de plus, il faut équilibrer le coût computationnel de l'extraction et l'exhaustivité du témoin retourné. ## Synthèse Synthèse L'extraction de témoins est la traduction disciplinée d'artefacts de preuve ou de solveur en exemples explicites (assignations, termes, contre-modèles) en suivant le contenu constructif encodé dans les dérivations ou traces, produisant une preuve vérifiable que les affirmations existentielles ou de satisfiabilité sont réalisées.