Un proceso en la resolución de restricciones en el que se aplican reglas de inferencia locales a las restricciones para reducir iterativamente los dominios de las variables eliminando valores que no pueden participar en ninguna solución bajo las restricciones actuales, frecuentemente como preprocesado o durante la búsqueda para podar el espacio de búsqueda.

Principio

Aplicar repetidamente una noción de consistencia local elegida (nodo, arco, camino, k‑consistencia, o propagadores globales específicos): detectar y eliminar valores de dominio contradichos por las restricciones mediante algoritmos de propagación (por ejemplo AC‑3, AC‑4, GAC para restricciones globales), hasta alcanzar un punto fijo o una contradicción.

Demostración

En un CSP de Sudoku, la propagación de consistencia de arcos elimina dígitos imposibles del dominio de cada celda considerando las restricciones de fila, columna y bloque; a medida que los dominios se reducen, la propagación puede forzar singletons que provocan reducciones adicionales, podando drásticamente la búsqueda con retroceso.

Aplicación incorrecta

Confiar en la propagación local para resolver completamente CSPs NP‑difíciles o aplicar un filtrado excesivamente agresivo que sea no correcto (elimina valores que pertenecen a alguna solución global) debido a una implementación incorrecta del propagador; o usar propagación sin combinarla con búsqueda cuando la propagación sola no decide la satisfacibilidad.

Consecuencia

La propagación reduce el esfuerzo de búsqueda al podar combinaciones de valores inviables, permite detectar contradicciones de forma temprana, soporta resolución incremental y dinámica y se integra bien con heurísticas de ramificación; no obstante no sustituye en general a la búsqueda exhaustiva salvo en clases tratables.

Inversión

La generación o relajación de restricciones invierte la función restrictiva de la propagación: en lugar de podar dominios para descartar valores, se pueden ampliar dominios o debilitar restricciones para guiar la búsqueda o capturar información dual, intercambiando poda por flexibilidad o sobreaproximación.

Límite

Se aplica en CSPs con dominios finitos o finitamente representables y depende del nivel de consistencia elegido; la propagación es correcta (no elimina soluciones) solo si los propagadores son correctos, y la completitud (encontrar una solución sin búsqueda) se da únicamente en clases de problemas tratables o niveles de consistencia global.

Tensión semántica

La tensión existe entre propagación y enfoques por codificación (a SAT/SMT) o entre consistencia local y razonamiento global: la propagación local es más barata pero más débil que el cierre completo de las restricciones, mientras que una propagación más fuerte (restricciones globales) es más costosa pero permite más poda.

Síntesis

La propagación de restricciones es un mecanismo iterativo de inferencia local y correcto que poda los dominios de variables según las restricciones para hacer viable la búsqueda; combinado con ramificación, propagadores globales y heurísticas constituye la columna vertebral de la programación por restricciones práctica, equilibrando coste de inferencia y potencia de poda.