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.

Existen varios algoritmos para la satisfacción de restricciones que funcionan únicamente con 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 compuesto por 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 denomina su aridad .

La transformación oculta convierte un problema de satisfacción de restricciones arbitrarias en uno binario. La transformación es similar a la que genera el problema dual . Al problema se le añaden nuevas variables, una por cada restricción del problema original. El dominio de cada una de estas variables es el conjunto de tuplas que satisfacen la restricción correspondiente. Las restricciones del nuevo problema obligan a que el valor de las variables originales sea consistente con los valores de las nuevas variables. Por ejemplo, si las nuevas variables${\displaystyle c}$, correspondiente a la antigua restricción${\displaystyle C(x,y)}$pueden asumir valores${\displaystyle (1,2)}$y${\displaystyle (2,0)}$Se añaden dos nuevas restricciones: la primera impone${\displaystyle x}$tomar valor${\displaystyle 1}$si${\displaystyle c=(1,2)}$valor${\displaystyle 2}$si${\displaystyle c=(2,0)}$y viceversa. La segunda condición impone una condición similar para la variable${\displaystyle y}$.

El grafo que representa el resultado de esta transformación es bipartito , ya que todas las restricciones se establecen entre una variable nueva y una antigua. Además, las restricciones son funcionales: para cualquier valor dado de una variable nueva, solo un valor de la variable antigua puede satisfacer la restricción.

• Fahiem Bacchus ; Xinguang Chen; Peter van Beek; Toby Walsh (2002). "Restricciones binarias frente a no binarias" (PDF) . Inteligencia Artificial . 140 (1/2): 1–37 . doi : 10.1016/S0004-3702(02)00210-2 .