transformación oculta
La transformación oculta reformula un problema de satisfacción de restricciones de tal manera que todas las restricciones tienen como máximo dos variables. El nuevo problema es satisfacible si y solo si el problema original lo era, y las soluciones se pueden convertir fácilmente de un problema a otro.
Hay una serie de algoritmos para la satisfacción de restricciones que funcionan solo en restricciones que tienen como máximo dos variables. Si un problema tiene restricciones con una aridad mayor (número de variables), la conversión a un problema hecho de restricciones binarias permite la ejecución de estos algoritmos de resolución. Las restricciones con una, dos o más variables se denominan restricciones unarias, binarias o de orden superior . El número de variables en una restricción se llama su aridad .
La transformación oculta convierte un problema de satisfacción de restricciones arbitrario en uno binario. La transformación es similar a la que genera el problema dual . Al problema se le agregan nuevas variables, una por cada restricción del problema original. El dominio de cada variable es el conjunto de tuplas satisfactorias de la restricción correspondiente. Las restricciones del nuevo problema imponen que el valor de las variables originales sea consistente con los valores de las nuevas variables. Por ejemplo, si las nuevas variables , correspondientes a la antigua restricción pueden asumir valores y , se agregan dos nuevas restricciones: la primera obliga a tomar valor si valor si, y viceversa. La segunda condición impone una condición similar para variable .
El gráfico que representa el resultado de esta transformación es bipartito , ya que todas las restricciones están entre una variable nueva y una antigua. Además, las restricciones son funcionales: para cualquier valor dado de una nueva variable, solo un valor de la antigua variable puede satisfacer la restricción.
