El proceso de producir un testigo concreto, contraejemplo o asignación satisfactoria a partir de una prueba, refutación, modelo o rastro del solver, de modo que las afirmaciones existenciales o los resultados de satisfacibilidad queden atestiguados por artefactos explícitos.

Principio

Recorrer el objeto de prueba o el rastro del solver y mapear las derivaciones abstractas a datos constructivos interpretando introducciones existenciales, construcciones de modelos o componentes de contra-modelos; preservar la corrección para que el testigo extraído satisfaga la fórmula original o demuestre su falsedad.

Demostración

De una ejecución de un solver SAT que encuentra una asignación satisfactoria, la extracción de testigo produce la asignación booleana concreta (p. ej. x1=true, x2=false). De una prueba de ∃x P(x) en un sistema constructivo, la extracción computa un término t específico y una derivación de P(t). De un solver SMT que devuelve unsat con una prueba por resolución, un bucle de refinamiento guiado por contraejemplos puede extraer un interpolante o una asignación concreta usada para refinar una abstracción.

Aplicación incorrecta

Intentar extraer un testigo constructivo de una prueba clásica de existencia que usa principios no constructivos sin una reinterpretación constructiva conduce al fallo o a artefactos espurios; extraer una asignación parcial o no verificada y tratarla como prueba de satisfacibilidad es insostenible.

Consecuencia

La extracción fiable de testigos convierte resultados abstractos del solver en artefactos tangibles para comprobación independiente, certificados o síntesis de programas; apoya el refinamiento de abstracciones guiado por contraejemplos y refuerza la confianza al permitir la validación independiente de afirmaciones existenciales.

Inversión

El contrario es una prueba u resultado del solver opaco que informa existencia o satisfacibilidad sin proporcionar ningún testigo concreto (p. ej. un oráculo UNSAT caja negra o una prueba no constructiva escrita a mano), lo que perjudica la reproducibilidad y la comprobación automatizada.

Límite

Requiere un objeto de prueba, un modelo o un rastro de solver lo suficientemente detallado que codifique información constructiva; excluye afirmaciones de solvers que solo dan respuestas sí/no sin rastro, salidas estadísticas o pruebas informales sin estructura formal para la extracción.

Tensión semántica

Existe tensión entre extraer testigos mínimos (los más pequeños o simples) y testigos canónicos o reproducibles; además, hay que equilibrar el coste computacional de la extracción y la completitud del testigo devuelto.

Síntesis

La extracción de testigos es la traducción disciplinada de artefactos de prueba o de solver en ejemplos explícitos (asignaciones, términos, contra-modelos) siguiendo el contenido constructivo codificado en derivaciones o rastros, produciendo evidencia verificable de que las afirmaciones existenciales o de satisfacibilidad se realizan.