Consistencia local

La consistencia de nodos requiere que toda restricción unaria sobre una variable sea satisfecha por todos los valores de su dominio, y viceversa. Esta condición se puede garantizar fácilmente reduciendo el dominio de cada variable a los valores que satisfacen todas sus restricciones unarias. Como resultado, las restricciones unarias pueden ignorarse y asumirse incorporadas a los dominios.

Por ejemplo, dada una variable${\displaystyle V}$con un dominio de${\displaystyle \left\{1,2,3,4\right\}}$y una restricción${\displaystyle V\leq 3}$, la consistencia de los nodos restringiría el dominio a${\displaystyle \left\{1,2,3\right\}}$y la restricción podría entonces descartarse. Este paso de preprocesamiento simplifica las etapas posteriores.

Una variable de un problema de satisfacción de restricciones es consistente con otra si cada uno de sus valores admisibles es consistente con algún valor admisible de la segunda variable. Formalmente, una variable${\displaystyle x_{i}}$¿Es el arco consistente con otra variable?${\displaystyle x_{j}}$si, para cada valor${\displaystyle a}$en el dominio de ${\displaystyle x_{i}}$existe un valor${\displaystyle b}$en el dominio de${\displaystyle x_{j}}$de tal manera que${\displaystyle (a,b)}$satisface la restricción binaria entre${\displaystyle x_{i}}$y${\displaystyle x_{j}}$Un problema es consistente en cuanto a su arco si cada variable es consistente en cuanto a su arco con todas las demás.

Por ejemplo, consideremos la restricción${\displaystyle x<y}$donde las variables abarcan el dominio de 1 a 3. Porque${\displaystyle x}$nunca puede ser 3, no hay arco de 3 a un valor en${\displaystyle y}$por lo que es seguro eliminar el valor 3 de${\displaystyle x}$dominio de, lo que resulta en${\displaystyle \{1,2\}}$. Asimismo,${\displaystyle y}$nunca puede ser 1, por lo tanto no hay arco, por lo tanto se puede quitar 1 de${\displaystyle y}$dominio de, lo que resulta en${\displaystyle \{2,3\}}$.

La consistencia de arco también puede definirse en relación con una restricción binaria específica: una restricción binaria es consistente en un arco si cada valor de una variable tiene un valor de la segunda variable tal que satisfacen la restricción. Esta definición de consistencia de arco es similar a la anterior, pero se aplica específicamente a una restricción. Esta diferencia es especialmente relevante para problemas no normalizados, donde la definición anterior consideraría todas las restricciones entre dos variables, mientras que esta solo considera una específica.

Si una variable no es consistente con otra, se puede lograr la consistencia eliminando algunos valores de su dominio. Esta es la forma de propagación de restricciones que impone la consistencia: elimina del dominio de la variable todo valor que no corresponda a un valor de la otra variable. Esta transformación mantiene las soluciones del problema, ya que los valores eliminados no forman parte de ninguna solución.

La propagación de restricciones puede hacer que todo el problema sea consistente repitiendo esta eliminación para todos los pares de variables. Este proceso podría tener que considerar un par de variables dado más de una vez. De hecho, eliminar valores del dominio de una variable puede hacer que otras variables dejen de ser consistentes con ella. Por ejemplo, si${\displaystyle x_{3}}$¿El arco es consistente con?${\displaystyle x_{2}}$pero el algoritmo reduce el dominio de${\displaystyle x_{2}}$, consistencia de arco de${\displaystyle x_{3}}$con${\displaystyle x_{2}}$Ya no es válido y debe aplicarse de nuevo.

Un algoritmo simplista recorrería los pares de variables, aplicando la consistencia de arcos y repitiendo el ciclo hasta que ningún dominio cambie durante un ciclo completo. El algoritmo AC-3 mejora este algoritmo al ignorar las restricciones que no se han modificado desde su último análisis. En concreto, trabaja con un conjunto de restricciones que inicialmente contiene todas las restricciones; en cada paso, toma una restricción y aplica la consistencia de arcos; si esta operación pudiera haber producido una violación de la consistencia de arcos en otra restricción, la vuelve a incluir en el conjunto de restricciones a analizar. De esta forma, una vez que se aplica la consistencia de arcos a una restricción, esta no se vuelve a considerar a menos que cambie el dominio de una de sus variables.

La consistencia de caminos es una propiedad similar a la consistencia de arcos, pero considera pares de variables en lugar de solo una. Un par de variables es consistente con un tercer par de variables si cada evaluación consistente del par se puede extender a la otra variable de tal manera que se satisfagan todas las restricciones binarias . Formalmente,${\displaystyle x_{i}}$y${\displaystyle x_{j}}$son camino consistente con${\displaystyle x_{k}}$si, para cada par de valores${\displaystyle (a,b)}$que satisface la restricción binaria entre${\displaystyle x_{i}}$y${\displaystyle x_{j}}$, existe un valor${\displaystyle c}$en el dominio de${\displaystyle x_{k}}$de tal manera que${\displaystyle (a,c)}$y${\displaystyle (b,c)}$satisfacer la restricción entre${\displaystyle x_{i}}$y${\displaystyle x_{k}}$y entre${\displaystyle x_{j}}$y${\displaystyle x_{k}}$, respectivamente.

La forma de propagación de restricciones que impone la consistencia de ruta funciona eliminando alguna asignación satisfactoria de una restricción. De hecho, la consistencia de ruta se puede imponer eliminando de una restricción binaria todas las evaluaciones que no se pueden extender a otra variable. En cuanto a la consistencia de arco, esta eliminación podría requerir considerar una restricción binaria más de una vez. En el caso de la consistencia de arco, el problema resultante tiene las mismas soluciones que el original, ya que los valores eliminados no están en ninguna solución.

La forma de propagación de restricciones que impone la consistencia de ruta puede introducir nuevas restricciones. Cuando dos variables no están relacionadas por una restricción binaria, están relacionadas virtualmente por la restricción que permite cualquier par de valores. Sin embargo, algún par de valores puede eliminarse mediante la propagación de restricciones. La restricción resultante ya no se satisface con todos los pares de valores. Por lo tanto, deja de ser una restricción virtual y trivial.

El término "consistencia de ruta" deriva de la definición original, que involucraba un par de variables y una ruta entre ellas, en lugar de un par y una sola variable. Si bien ambas definiciones difieren para un solo par de variables, son equivalentes al referirse al problema completo.

La consistencia de arcos y rutas se puede generalizar a restricciones no binarias utilizando tuplas de variables en lugar de una sola o un par. Una tupla de${\displaystyle i-1}$las variables son${\displaystyle i}$-consistente con otra variable si cada evaluación consistente de la${\displaystyle i-1}$Las variables pueden extenderse con un valor de la otra variable manteniendo la consistencia. Esta definición se extiende a problemas completos de la manera obvia. Fuerte${\displaystyle i}$-la consistencia es ${\displaystyle j}$-consistencia para todos${\displaystyle j\leq i}$.

El caso particular de consistencia 2 coincide con la consistencia de arcos (en este artículo se asume que todos los problemas son consistentes en nodos). Por otro lado, la consistencia 3 coincide con la consistencia de caminos solo si todas las restricciones son binarias, ya que la consistencia de caminos no implica restricciones ternarias, mientras que la consistencia 3 sí.

Otra forma de generalizar la consistencia de arco es la hiperconsistencia de arco o consistencia de arco generalizada , que requiere que una sola variable sea extensible para satisfacer una restricción. Es decir, una variable es hiperconsistente con una restricción si cada valor de la variable puede extenderse a las demás variables de la restricción de tal manera que esta se satisfaga.

La propagación de restricciones (que impone una forma de consistencia local) puede generar un dominio vacío o una restricción insatisfacible . En este caso, el problema no tiene solución. Lo contrario no es cierto en general: una instancia inconsistente puede ser consistente en arcos o en caminos sin tener un dominio vacío ni una restricción insatisfacible.

De hecho, la consistencia local es solo relativa a la consistencia de grupos de variables. Por ejemplo, la consistencia de arco garantiza que toda evaluación consistente de una variable se puede extender consistentemente a otra variable. Sin embargo, cuando un solo valor de una variable se extiende a otras dos variables, no hay garantía de que estos dos valores sean consistentes entre sí. Por ejemplo,${\displaystyle x_{1}=1}$puede ser consistente con${\displaystyle x_{2}=1}$y con${\displaystyle x_{3}=1}$pero estas dos evaluaciones pueden no ser coherentes entre sí.

Sin embargo, la propagación de restricciones puede utilizarse para demostrar la satisfacibilidad en algunos casos. Un conjunto de restricciones binarias consistentes en arcos y sin dominio vacío solo puede ser inconsistente si la red de restricciones contiene ciclos. De hecho, si las restricciones son binarias y forman un grafo acíclico, los valores siempre pueden propagarse entre ellas: para cada valor de una variable, todas las variables en una restricción que la contiene tienen un valor que satisface dicha restricción. Como resultado, se puede encontrar una solución eligiendo iterativamente una variable sin asignar y propagándola recursivamente a través de las restricciones. Este algoritmo nunca intenta asignar un valor a una variable que ya está asignada, ya que eso implicaría la existencia de ciclos en la red de restricciones.

Una condición similar se aplica a la consistencia de caminos. Los casos especiales en los que se puede establecer la satisfacibilidad al imponer la consistencia de arcos y la consistencia de caminos son los siguientes.

1. La aplicación de la consistencia de arcos establece la satisfacibilidad de problemas compuestos por restricciones binarias sin ciclos (un árbol de restricciones binarias);
2. La imposición de la consistencia de la ruta establece la satisfacibilidad para restricciones binarias (posiblemente con ciclos) con dominios binarios;
3. hacer cumplir las normas con firmeza${\displaystyle n}$La consistencia establece la satisfacibilidad de los problemas que contienen${\displaystyle n}$variables.

Algunas definiciones o resultados sobre consistencia relativa solo son válidos en casos especiales.

Cuando los dominios están compuestos por números enteros , se puede definir la consistencia de límites. Esta forma de consistencia se basa en la consistencia de los valores extremos de los dominios, es decir, los valores mínimo y máximo que puede tomar una variable.

Cuando las restricciones son algebraicas o booleanas , la consistencia de arcos es equivalente a agregar una nueva restricción o modificar sintácticamente una antigua, y esto se puede hacer componiendo restricciones adecuadamente.

Algunos tipos de restricciones son de uso común. Por ejemplo, se suele utilizar la restricción de que ciertas variables sean todas diferentes. Existen algoritmos especializados y eficientes para garantizar la consistencia de arcos en dichas restricciones.

La restricción que obliga a que varias variables sean diferentes se suele escribir${\displaystyle \mathop {\rm {alldifferent}} (x_{1},\ldots ,x_{n})}$o alldifferent([X1,...,Xn]). Esta restricción es equivalente a la desigualdad de todos los pares de variables diferentes, es decir,${\displaystyle x_{i}\not =x_{j}}$por cada${\displaystyle i\not =j}$Cuando el dominio de una variable se reduce a un único valor, este valor puede eliminarse de todos los demás dominios mediante la propagación de restricciones al garantizar la consistencia de arcos. El uso de la restricción especializada permite aprovechar propiedades que no se cumplen para desigualdades binarias individuales .

Una primera propiedad es que el número total de elementos en los dominios de todas las variables debe ser al menos igual al número de variables. Más precisamente, después de que se impone la consistencia de arcos, el número de variables no asignadas no debe exceder el número de valores en la unión de sus dominios. De lo contrario, la restricción no puede cumplirse. Esta condición puede verificarse fácilmente en una restricción de la alldifferentforma, pero no corresponde a la consistencia de arcos de la red de desigualdades. Una segunda propiedad de la alldifferentrestricción única es que la consistencia de hiperarcos puede verificarse eficientemente utilizando un algoritmo de emparejamiento bipartito . En particular, se construye un grafo con variables y valores como los dos conjuntos de nodos, y se ejecuta un algoritmo de emparejamiento de grafos bipartitos especializado para verificar la existencia de dicho emparejamiento. ^{[ 1 ]}

Otro tipo de restricción comúnmente utilizada es la cumulativesiguiente. Fue introducida para problemas de programación y asignación. Por ejemplo, cumulative([S1,...,Sm], [D1,...,Dm], [R1,...,Rm], L)se puede usar para formalizar la condición en la que hay mactividades, cada una con tiempo de inicio si, duración diy que utiliza una cantidad ride un recurso. La restricción establece que la cantidad total de recursos disponibles es L. Existen técnicas especializadas de propagación de restricciones para restricciones acumulativas; se utilizan diferentes técnicas dependiendo de qué dominios de variables ya se hayan reducido a un solo valor.

Una tercera restricción especializada que se utiliza en la programación lógica con restricciones es la elementsiguiente. En la programación lógica con restricciones, se permiten listas como valores de variables. Una restricción element(I, L, X)se satisface si Les una lista y Xes el I-ésimo elemento de esta lista. Existen reglas de propagación de restricciones especializadas para estas restricciones. Por ejemplo, si Ly se reducen a un dominio de un solo valor, se puede determinar Iun valor único para . De forma más general, se pueden inferir valores imposibles de a partir del dominio de .XX${\displaystyle I}$y viceversa.

Si un algoritmo evalúa variables en el orden${\displaystyle x_{1},\ldots ,x_{n}}$La consistencia solo es útil cuando garantiza que los valores de las variables de índice inferior sean todos consistentes con los valores de las variables de índice superior.

Al elegir un valor para una variable, se pueden descartar los valores que sean inconsistentes con todos los valores de una variable no asignada. De hecho, incluso si estos valores son consistentes con la evaluación parcial actual, el algoritmo no encontrará posteriormente un valor consistente para la variable no asignada. Por otro lado, no es necesario garantizar la consistencia con las variables que ya han sido evaluadas: si el algoritmo elige un valor inconsistente con la evaluación parcial actual, la inconsistencia se detectará de todos modos.

Suponiendo que el orden de evaluación de las variables es${\displaystyle x_{1},\ldots ,x_{n}}$, un problema de satisfacción de restricciones es consistente en arcos direccionales si cada variable${\displaystyle x_{i}}$¿Es el arco consistente con cualquier otra variable?${\displaystyle x_{j}}$de tal manera que${\displaystyle i<j}$La consistencia de la trayectoria direccional es similar, pero dos variables${\displaystyle x_{i},x_{j}}$tienen que ser un camino coherente con${\displaystyle x_{z}}$solo si${\displaystyle i,j<z}$La consistencia de trayectoria direccional fuerte implica tanto consistencia de trayectoria direccional como consistencia de arco direccional. Se pueden dar definiciones similares para las otras formas de consistencia.

La propagación de restricciones que impone la consistencia de arco direccional itera sobre las variables desde la última hasta la primera, imponiendo en cada paso la consistencia de arco de cada variable de índice inferior con ella. Si el orden de las variables es${\displaystyle x_{1},\ldots ,x_{n}}$, este algoritmo itera sobre variables de${\displaystyle x_{n}}$a${\displaystyle x_{1}}$; para variable${\displaystyle x_{j}}$, impone consistencia de arco de cada variable de índice inferior a${\displaystyle j}$con${\displaystyle x_{j}}$.

La consistencia de trayectoria direccional y la consistencia de trayectoria direccional fuerte pueden imponerse mediante algoritmos similares al de la consistencia de arco. Estos procesan variables desde${\displaystyle x_{n}}$a${\displaystyle x_{1}}$; para cada variable${\displaystyle x_{z}}$dos variables${\displaystyle x_{i},x_{j}}$con${\displaystyle i,j<z}$se consideran y la consistencia de trayectoria de ellos con${\displaystyle x_{z}}$se aplica. No se requiere ninguna operación si el problema no contiene ninguna restricción en${\displaystyle x_{i}}$y${\displaystyle x_{z}}$o ninguna restricción entre${\displaystyle x_{j}}$y${\displaystyle x_{z}}$Sin embargo, incluso si no hay ninguna restricción entre${\displaystyle x_{i}}$y${\displaystyle x_{j}}$Se asume una restricción trivial. Si la propagación de restricciones reduce su conjunto de asignaciones satisfactorias, crea efectivamente una nueva restricción no trivial. La propagación de restricciones que impone una fuerte consistencia de ruta direccional es similar, pero también impone consistencia de arco.

La consistencia direccional garantiza que las soluciones parciales que satisfacen una restricción se pueden extender de forma consistente a otra variable de índice superior. Sin embargo, no garantiza que las extensiones a diferentes variables sean consistentes entre sí. Por ejemplo, una solución parcial puede extenderse de forma consistente a una variable.${\displaystyle x_{i}}$o a variable${\displaystyle x_{j}}$, pero estas dos extensiones no son consistentes entre sí.

Hay dos casos en los que esto no sucede, y la consistencia direccional garantiza la satisfacibilidad si ningún dominio está vacío y ninguna restricción es insatisfacible.

El primer caso corresponde a un problema de restricciones binarias con una ordenación de las variables que da como resultado un grafo ordenado de restricciones de ancho 1. Dicha ordenación existe si y solo si el grafo de restricciones es un árbol. En tal caso, el ancho del grafo limita el número máximo de nodos inferiores (según la ordenación) a los que se une un nodo. La consistencia de arcos direccionales garantiza que toda asignación consistente a una variable se puede extender a nodos superiores, y el ancho 1 garantiza que un nodo no se une a más de un nodo inferior. Por lo tanto, una vez asignada la variable inferior, su valor se puede extender de forma consistente a todas las variables superiores con las que se une. Esta extensión no puede generar inconsistencias posteriormente. De hecho, ninguna otra variable inferior se une a esa variable superior, ya que el grafo tiene ancho 1.

Como resultado, si un problema de restricciones tiene un ancho de 1 con respecto a un ordenamiento de sus variables (lo que implica que su grafo correspondiente es un árbol) y el problema es consistente en cuanto a la dirección del arco con respecto al mismo ordenamiento, se puede encontrar una solución (si la hay) asignando iterativamente variables de acuerdo con el ordenamiento.

El segundo caso en el que la consistencia direccional garantiza la satisfacibilidad si ningún dominio está vacío y ninguna restricción es insatisfacible es el de los problemas de restricciones binarias cuyo grafo tiene un ancho inducido de 2, utilizando una consistencia de camino direccional fuerte. De hecho, esta forma de consistencia garantiza que cada asignación a una variable o a un par de variables puede extenderse a una variable de mayor orden, y el ancho 2 garantiza que esta variable no se une a otro par de variables de menor orden.

La razón por la que se considera el ancho inducido en lugar del ancho es que imponer consistencia de ruta direccional puede añadir restricciones. De hecho, si dos variables no están en la misma restricción, sino en una restricción con una variable de mayor nivel, algunos pares de sus valores pueden violar la consistencia de ruta. Eliminar dichos pares crea una nueva restricción. Como resultado, la propagación de restricciones puede producir un problema cuyo grafo tiene más aristas que el original. Sin embargo, todas estas aristas están necesariamente en el grafo inducido, ya que todas se encuentran entre dos padres del mismo nodo. Un ancho de 2 garantiza que cada evaluación parcial consistente se puede extender a una solución, pero este ancho es relativo al grafo generado. Por lo tanto, se requiere un ancho inducido de 2 para una fuerte consistencia de ruta direccional que garantice la existencia de soluciones.

Direccional${\displaystyle i}$-la consistencia es la garantía de que cada asignación consistente a${\displaystyle i-1}$Las variables pueden extenderse de forma consistente a otra variable que se encuentra en un orden superior. Fuerte direccionalidad${\displaystyle i}$-la consistencia se define de manera similar, pero todos los grupos de como máximo${\displaystyle i-1}$Se consideran variables. Si un problema es fuertemente direccional${\displaystyle i}$-consistente y tiene un ancho menor que${\displaystyle i}$y no tiene dominio vacío ni restricción insatisfacible, tiene soluciones.

Cada problema puede plantearse de forma fuertemente direccional.${\displaystyle i}$-consistente, pero esta operación puede aumentar el ancho de sus gráficos correspondientes. El procedimiento de propagación de restricciones que impone consistencia direccional es similar al utilizado para la consistencia de arcos direccionales y la consistencia de caminos. Las variables se consideran por turno, de la última a la primera según el orden. Para la variable${\displaystyle x_{k}}$, el algoritmo considera cada grupo de${\displaystyle i-1}$variables que tienen un índice inferior a${\displaystyle k}$y están en una restricción con${\displaystyle x_{k}}$. Consistencia de estas variables con${\displaystyle x_{k}}$se verifica y posiblemente se aplica eliminando las asignaciones satisfactorias de la restricción entre todas estas${\displaystyle i}$variables (si las hay, o creando una nueva en caso contrario).

Este procedimiento genera una dirección fuertemente marcada.${\displaystyle i}$-instancia consistente. Sin embargo, también puede agregar nuevas restricciones a la instancia. Como resultado, incluso si el ancho del problema original es${\displaystyle i}$, el ancho de la instancia resultante puede ser mayor. Si este es el caso, la consistencia fuerte direccional no implica satisfacibilidad incluso si ningún dominio está vacío y ninguna restricción es insatisfacible.

Sin embargo, la propagación de restricciones solo agrega restricciones a las variables que son menores que la que está considerando actualmente. Como resultado, ninguna restricción sobre una variable se modifica o agrega una vez que el algoritmo ha procesado esta variable. En lugar de considerar una variable fija${\displaystyle i}$, se puede modificar al número de padres de cada variable considerada (los padres de una variable son las variables de índice inferior a la variable y que están en una restricción con la variable). Esto corresponde a considerar todos los padres de una variable dada en cada paso. En otras palabras, para cada variable${\displaystyle x_{i}}$desde el último hasta el primero, todos sus padres están incluidos en una nueva restricción que limita sus valores a los que son consistentes con${\displaystyle x_{i}}$. Dado que este algoritmo puede considerarse una modificación del anterior con un valor${\displaystyle i}$ que se cambia al número de padres de cada nodo, se llama consistencia adaptativa .

Este algoritmo impone una fuerte direccionalidad.${\displaystyle i}$-consistencia con${\displaystyle i}$igual al ancho inducido del problema. La instancia resultante es satisfacible si y solo si ningún dominio o restricción se deja vacío. Si este es el caso, se puede encontrar fácilmente una solución estableciendo iterativamente una variable no asignada a un valor arbitrario y propagando esta evaluación parcial a otras variables. Este algoritmo no siempre es polinomial, ya que el número de restricciones introducidas al imponer una consistencia direccional fuerte puede producir un aumento exponencial del tamaño. Sin embargo, el problema es resoluble en tiempo polinomial si la imposición de la consistencia direccional fuerte no amplía la instancia de forma superpolinomial . Como resultado, si una instancia tiene un ancho inducido acotado por una constante, se puede resolver en tiempo polinomial.

La eliminación de cubetas es un algoritmo de satisfacibilidad. Puede definirse como una reformulación de la consistencia adaptativa. Su definición utiliza cubetas, que son contenedores de restricciones, donde cada variable tiene una cubeta asociada. Una restricción siempre pertenece a la cubeta de su variable de mayor valor.

El algoritmo de eliminación de cubetas procede de la variable más alta a la más baja sucesivamente. En cada paso, las restricciones en las cubetas de esta variable${\displaystyle x_{i}}$se consideran. Por definición, estas restricciones solo involucran variables que son menores que${\displaystyle x_{i}}$. El algoritmo modifica la restricción entre estas variables inferiores (si existe, de lo contrario crea una nueva). En particular, obliga a que sus valores sean extensibles a${\displaystyle x_{i}}$consistentemente con las restricciones en el cubo de${\displaystyle x_{i}}$. Esta nueva restricción, si la hay, se coloca entonces en el contenedor apropiado. Dado que esta restricción solo involucra variables que son menores que${\displaystyle x_{i}}$, se agrega a un cubo de una variable que es menor que${\displaystyle x_{i}}$.

Este algoritmo es equivalente a imponer consistencia adaptativa. Dado que ambos imponen consistencia de una variable con todos sus padres, y dado que no se agrega ninguna restricción nueva después de considerar una variable, el resultado es una instancia que se puede resolver sin retroceso .

Dado que el grafo de la instancia que generan es un subgrafo del grafo inducido, si el ancho inducido está limitado por una constante, la instancia generada tendrá un tamaño polinomial con respecto al tamaño de la instancia original. En consecuencia, si el ancho inducido de una instancia está limitado por una constante, ambos algoritmos pueden resolverla en tiempo polinomial.

Un problema de satisfacción de restricciones puede ser relacionalmente consistente, no tener dominio vacío ni restricciones insatisfacibles, y aun así ser insatisfacible. Sin embargo, existen algunos casos en los que esto no es posible.

El primer caso es el de relaciones fuertemente relacionales.${\displaystyle m}$-problema consistente cuando los dominios contienen como máximo${\displaystyle m}$elementos. En este caso, una evaluación consistente de${\displaystyle k}$Las variables siempre se pueden extender a otra única variable. Si${\displaystyle x_{1}=a_{1},\ldots ,x_{k}=a_{k}}$es tal evaluación y${\displaystyle x_{k+1}}$es la variable, solo hay${\displaystyle m}$posibles valores que puede tomar la variable. Si todos esos valores son inconsistentes con la evaluación, hay${\displaystyle m}$restricciones (no necesariamente únicas) que son violadas por la evaluación y uno de sus posibles valores. Como resultado, la evaluación no puede extenderse para satisfacer todas estas${\displaystyle m}$-o menos restricciones, violando la condición de fuerte relación${\displaystyle m}$-consistencia.

El segundo caso está relacionado con una medida de las restricciones, en lugar de los dominios. Una restricción es${\displaystyle m}$-ajustado si cada evaluación de todas sus variables excepto una puede extenderse para satisfacer la restricción ya sea por todos los valores posibles de la otra variable o por como máximo${\displaystyle m}$de sus valores. Problema tener${\displaystyle m}$-las restricciones estrictas son satisfechas si y solo si son fuertemente relacionales.${\displaystyle m+1}$-coherente.

El tercer caso es el de las restricciones binarias que pueden representarse mediante matrices convexas por filas. Una restricción binaria puede representarse mediante una matriz bidimensional.${\displaystyle M}$, dónde${\displaystyle M_{ij}}$es 0 o 1 dependiendo de si el${\displaystyle i}$-ésimo valor del dominio de${\displaystyle x_{i}}$y el${\displaystyle j}$-ésimo valor del dominio de${\displaystyle x_{j}}$Satisfacer la restricción. Una fila de esta matriz es convexa si los 1 que contiene son consecutivos (formalmente, si dos elementos son 1, todos los elementos intermedios también lo son). Una matriz es convexa por filas si todas sus filas son convexas.

La condición que hace que la consistencia de ruta relacional fuerte sea equivalente a la satisfacibilidad es la de los problemas de satisfacción de restricciones para los cuales existe un orden de las variables que hace que todas las restricciones se representen mediante matrices convexas por filas. Este resultado se basa en el hecho de que un conjunto de filas convexas que tienen un elemento común por pares también tienen un elemento común globalmente. Considerando una evaluación sobre${\displaystyle k}$variables, los valores permitidos para la${\displaystyle k+1}$-ésimo se obtienen seleccionando algunas filas de algunas restricciones. En particular, para cada variable entre las${\displaystyle k}$unos, la fila relativa a su valor en la matriz que representa la restricción que la relaciona con la${\displaystyle k+1}$Una representa los valores permitidos de la otra. Dado que estas filas son convexas y tienen un elemento común por pares debido a la consistencia de la ruta, también tienen un elemento común compartido, que representa un valor de la última variable que es consistente con los demás.