La complejidad de la satisfacción de restricciones es la aplicación de la teoría de la complejidad computacional sobre la satisfacción de restricciones . Se ha estudiado principalmente para discriminar entre clases tratables e intratables de problemas de satisfacción de restricciones en dominios finitos.
Resolver un problema de satisfacción de restricciones en un dominio finito es un problema NP-completo en general. La investigación ha demostrado una serie de subcasas de tiempo polinómico, la mayoría obtenidas restringiendo los dominios o restricciones permitidos o la forma en que se pueden colocar restricciones sobre las variables. La investigación también ha establecido una relación entre el problema de satisfacción de restricciones y problemas en otras áreas, como la teoría de modelos finitos y las bases de datos .
Descripción general
Establecer si un problema de satisfacción de restricciones en un dominio finito tiene soluciones es un problema NP completo en general. Ésta es una consecuencia fácil de una serie de otros problemas NP completos que se pueden expresar como problemas de satisfacción de restricciones. Dichos otros problemas incluyen la satisfacibilidad proposicional y la capacidad de tres colores .
La manejabilidad se puede obtener considerando clases específicas de problemas de satisfacción de restricciones. Por ejemplo, si el dominio es binario y todas las restricciones son binarias , establecer la satisfacibilidad es un problema de tiempo polinomial porque este problema es equivalente a 2-SAT , que es manejable. La investigación ha mostrado una serie de subcampos manejables. Algunas de estas clases se basan en restringir los dominios o relaciones permitidos, otras en restringir la forma en que se imponen restricciones a las variables y algunas en ambos tipos de restricciones.
Una línea de investigación utilizó una correspondencia entre el problema de satisfacción de restricciones y el problema de establecer la existencia de un homomorfismo entre dos estructuras relacionales. Esta correspondencia se ha utilizado para vincular la satisfacción de las restricciones con temas tradicionalmente relacionados con la teoría de bases de datos .
Un problema de investigación considerado se refiere a la existencia de dicotomías entre conjuntos de restricciones. Esta es la cuestión de si un conjunto de restricciones contiene solo restricciones de tiempo polinómico y restricciones NP-completo. Esta cuestión está resuelta para algunos conjuntos de restricciones, pero aún está abierta para el conjunto de todas las restricciones basadas en un dominio fijo y un conjunto de relaciones, a partir de 2007.[actualizar]. Algunos autores consideran que esta es la pregunta abierta más importante sobre la complejidad de la satisfacción de las restricciones.
Restricciones
Pueden obtenerse subcampos manejables de los problemas generales de satisfacción de restricciones imponiendo restricciones adecuadas a los problemas. Se han considerado varios tipos de restricciones.
Restricciones estructurales y relacionales
La manejabilidad se puede obtener restringiendo los posibles dominios o restricciones. En particular, se han considerado dos tipos de restricciones:
- las restricciones relacionales delimitan el dominio y los valores que satisfacen las restricciones;
- Las restricciones estructurales limitan la forma en que las restricciones se distribuyen entre las variables.
Más precisamente, una restricción relacional especifica un lenguaje de restricción , que es un dominio y un conjunto de relaciones sobre este dominio. Un problema de satisfacción de restricciones cumple con esta restricción si tiene exactamente este dominio y la relación de cada restricción está en el conjunto de relaciones dado. En otras palabras, una restricción relacional limita el dominio y el conjunto de valores satisfactorios de cada restricción, pero no cómo se colocan las restricciones sobre las variables. En cambio, esto se hace mediante restricciones estructurales. La restricción estructural se puede verificar mirando solo los alcances de las restricciones (sus variables), ignorando sus relaciones (su conjunto de valores satisfactorios).
Un lenguaje de restricción es manejable si existe un algoritmo polinomial que resuelva todos los problemas en función del lenguaje, es decir, utilizando el dominio y las relaciones especificadas en el dominio. Un ejemplo de un lenguaje de restricciones manejable es el de los dominios binarios y las restricciones binarias. Formalmente, esta restricción corresponde a permitir solo dominios de tamaño 2 y solo restricciones cuya relación sea una relación binaria. Si bien el segundo hecho implica que los alcances de las restricciones son binarios, esto no es una restricción estructural porque no prohíbe que se coloque ninguna restricción en un par arbitrario de variables. Por cierto, el problema se vuelve NP completo si se elimina alguna de las restricciones: las restricciones binarias y los dominios ternarios pueden expresar el problema de coloración del gráfico , mientras que las restricciones ternarias y los dominios binarios pueden expresar 3-SAT ; estos dos problemas son NP-completos.
Un ejemplo de una clase manejable definida en términos de una restricción estructural es la de problemas acíclicos binarios. Dado un problema de satisfacción de restricciones con solo restricciones binarias, su gráfico asociado tiene un vértice para cada variable y un borde para cada restricción; dos vértices se unen si están en una restricción. Si la gráfica de un problema es acíclica, el problema también se llama acíclico. El problema de la satisfacibilidad en la clase de problema acíclico binario es manejable. Ésta es una restricción estructural porque no pone ningún límite al dominio ni a los valores específicos que satisfacen una restricción; más bien, restringe la forma en que se colocan las restricciones sobre las variables.
Si bien las restricciones relacionales y estructurales son las que se utilizan principalmente para derivar clases manejables de satisfacción de restricciones, hay algunas clases manejables que no pueden definirse solo mediante restricciones relacionales o solo restricciones estructurales. La clase manejable definida en términos de convexidad de filas no se puede definir solo en términos de relaciones o solo en términos de estructura, ya que la convexidad de filas depende tanto de las relaciones como del orden de las variables (y por lo tanto no se puede verificar mirando solo en cada restricción a su vez).
Restricciones uniformes y no uniformes
El subcaso obtenido al restringir a un lenguaje de restricción finito se denomina problema no uniforme . Estos problemas se consideran principalmente al expresar la satisfacción de la restricción en términos del problema del homomorfismo, como se explica a continuación. Los problemas uniformes también se definieron en el contexto de los problemas de homomorfismo; un problema uniforme se puede definir como la unión de una colección (posiblemente infinita) de problemas no uniformes. Un problema uniforme hecho de un conjunto infinito de problemas no uniformes puede ser intratable incluso si todos estos problemas no uniformes son manejables.
Restricciones basadas en árboles
Algunas restricciones consideradas se basan en la manejabilidad del problema de satisfacción de restricciones donde las restricciones son todas binarias y forman un árbol sobre las variables. Esta es una restricción estructural, ya que se puede verificar mirando solo los alcances de las restricciones, ignorando dominios y relaciones.
Esta restricción se basa en el gráfico primario del problema, que es un gráfico cuyos vértices son las variables del problema y los bordes representan la presencia de una restricción entre dos variables. Sin embargo, la trazabilidad también se puede obtener colocando la condición de árbol en el gráfico primario de problemas que son reformulaciones del original.
Condiciones de equivalencia
Los problemas de satisfacción de restricciones pueden reformularse en términos de otros problemas, lo que lleva a condiciones equivalentes a la tratabilidad. La reformulación más utilizada es la del problema del homomorfismo .
Satisfacción de la restricción y el problema del homomorfismo
Se ha proporcionado un vínculo entre la satisfacción de la restricción y la teoría de la base de datos en forma de correspondencia entre el problema de la satisfacibilidad de la restricción y el problema de comprobar si existe un homomorfismo entre dos estructuras relacionales. Una estructura relacional es una representación matemática de una base de datos: es un conjunto de valores y un conjunto de relaciones sobre estos valores. Formalmente,, donde cada es una relación sobre , es decir, un conjunto de tuplas de valores de .
Una estructura relacional es diferente de un problema de satisfacción de restricciones porque una restricción es una relación y una tupla de variables. También es diferente la forma en que se utilizan: para un problema de satisfacción de restricciones, encontrar una asignación satisfactoria es el problema principal; para una estructura de relación, el principal problema es encontrar la respuesta a una consulta.
Sin embargo, el problema de la satisfacción con la restricción está relacionado con el problema de establecer la existencia de un homomorfismo entre dos estructuras relacionales. Un homomorfismo es una función de los valores de la primera relación a los valores de la segunda que, cuando se aplica a todos los valores de una relación de la primera estructura, la convierte en un subconjunto de la relación correspondiente de la segunda estructura. Formalmente, es un homomorfismo de a si es una función de a tal que, si luego .
Se puede establecer una correspondencia directa entre el problema de la satisfacción de restricciones y el problema de homomorfismo. Para un problema de satisfacción de restricciones dado, se pueden construir un par de estructuras relacionales, la primera codifica las variables y las firmas de las restricciones, la segunda codifica los dominios y las relaciones de las restricciones. La satisfacción del problema de satisfacción de la restricción corresponde a encontrar un valor para cada variable de manera que reemplazar un valor en una firma lo convierte en una tupla en la relación de la restricción. Esto es posible exactamente si esta evaluación es un homomorfismo entre las dos estructuras relacionales.
La correspondencia inversa es la opuesta: dadas dos estructuras relacionales, una codifica los valores de la primera en las variables de un problema de satisfacción de restricciones y los valores de la segunda en el dominio del mismo problema. Para cada tupla de cada relación de la primera estructura, existe una restricción que tiene como valores la relación correspondiente de la segunda estructura. De esta manera, un homomorfismo corresponde a mapear cada alcance de cada restricción (cada tupla de cada relación de la primera estructura) en una tupla en la relación de la restricción (una tupla en la relación correspondiente de la segunda estructura).
Un problema de satisfacción de restricciones no uniforme es una restricción en la que se fija la segunda estructura del problema de homomorfismo. En otras palabras, toda estructura relacional define un problema no uniforme, el de decir si una estructura de relación es homomórfica a ella. Se puede imponer una restricción similar a la primera estructura; para cualquier primera estructura fija, el problema del homomorfismo es manejable. Un problema de satisfacción de restricción uniforme es una restricción arbitraria a los conjuntos de estructuras para la primera y segunda estructura del problema de homomorfismo.
Evaluación y contención de consultas conjuntivas
Dado que el problema de homomorfismo es equivalente a la evaluación de consultas conjuntivas y la contención de consultas conjuntivas , estos dos problemas también son equivalentes a la satisfacción de restricciones.
Unirse a la evaluación
Cada restricción se puede ver como una tabla en una base de datos , donde las variables se interpretan como nombres de atributos y la relación es el conjunto de registros en la tabla. Las soluciones de un problema de satisfacción de restricciones son el resultado de una combinación interna de las tablas que representan sus restricciones; por tanto, el problema de la existencia de soluciones puede reformularse como el problema de comprobar si el resultado de una combinación interna de varias tablas está vacío.
Teoremas de dicotomía
Se sabe que algunos lenguajes de restricción (o problemas no uniformes) corresponden a problemas que se pueden resolver en tiempo polinomial , y se sabe que algunos otros expresan problemas NP-completos . Sin embargo, es posible que algunos lenguajes de restricción no lo sean. Se sabe por el teorema de Ladner que si P no es igual a NP, entonces existen problemas en NP que no son ni en tiempo polinómico ni NP-duro. A partir de 2007[actualizar], no se sabe si tales problemas pueden expresarse como problemas de satisfacción de restricciones con un lenguaje de restricciones fijo. Si los lenguajes de Ladner no fueran expresables de esta manera, el conjunto de todos los lenguajes de restricción podría dividirse exactamente en los que definen el tiempo polinómico y los que definen los problemas NP-completos; es decir, este conjunto exhibiría una dicotomía .
Se conocen resultados parciales para algunos conjuntos de lenguajes de restricción. El resultado más conocido es el teorema de la dicotomía de Schaefer , que prueba la existencia de una dicotomía en el conjunto de lenguajes de restricción en un dominio binario. Más precisamente, demuestra que una restricción de relación en un dominio binario es manejable si todas sus relaciones pertenecen a una de las seis clases y es NP-completa en caso contrario. Bulatov demostró un teorema de dicotomía para dominios de tres elementos.
Otro teorema de dicotomía para los lenguajes de restricción es el teorema de Hell-Nesetril , que muestra una dicotomía para problemas sobre restricciones binarias con una sola relación simétrica fija. En términos del problema de homomorfismo, cada uno de estos problemas es equivalente a la existencia de un homomorfismo desde una estructura relacional a un gráfico fijo no dirigido (un gráfico no dirigido puede considerarse como una estructura relacional con una sola relación simétrica binaria). El teorema de Hell-Nesetril demuestra que cada problema de este tipo es polinomial-tiempo o NP-completo. Más precisamente, el problema es polinomio-tiempo si el gráfico es 2-coloreable, es decir, es bipartito y es NP-completo en caso contrario.
Condiciones suficientes para la tractabilidad
Algunos resultados de complejidad demuestran que algunas restricciones son polinomiales sin probar que todas las demás restricciones posibles del mismo tipo son NP-duras.
Registro de datos
Una condición suficiente para la tractabilidad está relacionada con la expresividad en Datalog . Una consulta de registro de datos booleanos da un valor de verdad a un conjunto de literales sobre un alfabeto dado, siendo cada literal una expresión de la forma; como resultado, una consulta Boolean Datalog expresa un conjunto de conjuntos de literales, ya que puede considerarse semánticamente equivalente al conjunto de todos los conjuntos de literales que evalúa como verdadero.
Por otro lado, un problema no uniforme puede verse como una forma de expresar un conjunto similar. Para un problema no uniforme dado, el conjunto de relaciones que se pueden usar en las restricciones es fijo; como resultado, se pueden dar nombres únicosa ellos. Una instancia de este problema no uniforme se puede escribir como un conjunto de literales de la forma. Entre estas instancias / conjuntos de literales, algunas son satisfactorias y otras no; si un conjunto de literales es satisfactorio depende de las relaciones, que son especificadas por el problema no uniforme. A la inversa, un problema no uniforme indica qué conjuntos de literales representan instancias satisfactorias y cuáles representan instancias insatisfactorias. Una vez que se nombran las relaciones, un problema no uniforme expresa un conjunto de conjuntos de literales: los asociados a instancias satisfactorias (o insatisfactorias).
Una condición suficiente de manejabilidad es que un problema no uniforme sea manejable si el conjunto de sus instancias insatisfactorias puede expresarse mediante una consulta de registro de datos booleanos. En otras palabras, si el conjunto de conjuntos de literales que representan instancias insatisfactorias del problema no uniforme es también el conjunto de conjuntos de literales que satisfacen una consulta de registro de datos booleanos, entonces el problema no uniforme es manejable.
Consistencia local
En ocasiones, la satisfacción puede establecerse imponiendo una forma de coherencia local y luego comprobando la existencia de un dominio vacío o una relación de restricción. En general, este es un algoritmo de insatisfacción correcto pero incompleto: un problema puede ser insatisfactorio incluso si no se produce un dominio vacío o una relación de restricción. Para algunas formas de coherencia local, este algoritmo también puede requerir un tiempo exponencial. Sin embargo, para algunos problemas y para algunos tipos de consistencia local, es correcto y de tiempo polinómico.
Las siguientes condiciones explotan el gráfico principal del problema, que tiene un vértice para cada variable y un borde entre dos nodos si las variables correspondientes están en una restricción. Las siguientes son condiciones sobre los problemas de satisfacción de restricciones binarias donde hacer cumplir la consistencia local es manejable y permite establecer la satisfacibilidad:
- hacer cumplir la coherencia del arco, si el gráfico principal es acíclico;
- imponer la coherencia del arco direccional para un ordenamiento de las variables que hace que el gráfico ordenado de restricción tenga ancho 1 (tal ordenamiento existe si y solo si el gráfico primario es un árbol, pero no todos los ordenamientos de un árbol generan ancho 1);
- imponer una fuerte consistencia de la ruta direccional para un orden de las variables que hace que el gráfico primario tenga un ancho inducido 2.
Una condición que extiende la última se cumple para problemas de satisfacción de restricciones no binarias. Es decir, para todos los problemas para los que existe un orden que hace que el gráfico principal tenga un ancho inducido limitado por una i constante, la aplicación de una i-consistencia direccional fuerte es manejable y permite establecer la satisfacibilidad.
Condiciones basadas en árboles
Los problemas de satisfacción de restricciones compuestos por restricciones binarias solo pueden verse como gráficos , donde los vértices son variables y los bordes representan la presencia de una restricción entre dos variables. Esta gráfica se llama gráfica de Gaifman o gráfica de restricción primaria (o simplemente gráfica primaria) del problema.
Si el gráfico principal de un problema es acíclico, establecer la satisfacibilidad del problema es un problema manejable. Esta es una restricción estructural, ya que se puede verificar mirando solo los alcances de las restricciones, sin tener en cuenta sus relaciones y el dominio. Un gráfico acíclico es un bosque , pero generalmente se asume la conectividad ; como resultado, la condición que generalmente se considera es que los gráficos primarios son árboles .
Esta propiedad de los problemas de satisfacción de restricciones en forma de árbol se explota mediante métodos de descomposición , que convierten los problemas en equivalentes que solo contienen restricciones binarias organizadas como un árbol. Las variables de estos problemas corresponden a conjuntos de variables del problema original; el dominio de dicha variable se obtiene considerando algunas de las restricciones del problema original cuyo alcance está contenido en el correspondiente conjunto original de variables; Las restricciones de estos nuevos problemas representan la igualdad de variables que están contenidas en dos conjuntos.
Si la gráfica de uno de esos problemas equivalentes es un árbol, el problema se puede resolver de manera eficiente. Por otro lado, producir uno de estos problemas equivalentes puede no ser eficiente debido a dos factores: la necesidad de determinar los efectos combinados de un grupo de restricciones sobre un conjunto de variables, y la necesidad de almacenar todas las tuplas de valores que satisfagan un determinado grupo de restricciones.
Condición necesaria para la tractabilidad.
Se ha demostrado una condición necesaria para la manejabilidad de un lenguaje de restricción basado en el dispositivo universal . El artilugio universal es un problema particular de satisfacción de restricciones que se definió inicialmente con el fin de expresar nuevas relaciones mediante la proyección.
El gadget universal
Una relación que no está presente en un lenguaje de restricción puede ser "simulada" por restricciones usando las relaciones en el lenguaje. En particular, se puede crear una nueva relación colocando un conjunto de restricciones y usando solo algunas de sus variables. Si todas las demás restricciones usan solo estas variables, este conjunto de restricciones obliga a estas variables a asumir solo valores específicos, simulando prácticamente una nueva relación.
Cada problema de satisfacción de restricciones y subconjunto de sus variables define una relación, que está compuesta por todas las tuplas de valores de las variables que pueden extenderse a las otras variables para formar una solución. Técnicamente, esta relación se obtiene proyectando la relación que tiene las soluciones como filas sobre las variables consideradas.
El gadget universal se basa en la observación de que toda relación que contiene -tuplas se pueden definir proyectando una relación que contiene todas las columnas posibles de elementos del dominio. Como ejemplo, las siguientes tablas muestran tal proyección:
abcdefghbd--------------- ---1 1 1 1 0 0 0 0 -> 1 11 1 0 0 1 1 0 0 1 01 0 1 0 1 0 1 0 0 0
Si la tabla de la izquierda es el conjunto de soluciones de un problema de satisfacción de restricciones, sus variables y están restringidos a los valores de la tabla de la derecha. Como resultado, el problema de satisfacción de restricciones se puede utilizar para establecer una restricción cuya relación sea la tabla de la derecha, que puede no estar en el lenguaje de restricciones.
Como resultado, si un problema de satisfacción de restricciones tiene la tabla de la izquierda como su conjunto de soluciones, cada relación puede expresarse proyectando sobre un conjunto adecuado de variables. Una forma de intentar obtener esta tabla como el conjunto de soluciones es colocar todas las restricciones posibles que las soluciones requeridas no violen.
Como ejemplo, si el lenguaje contiene la relación binaria que representa la disyunción booleana (una relación que contiene todas las tuplas de dos elementos que contiene al menos un 1), esta relación se coloca como una restricción en y , porque sus valores en la tabla anterior son , de nuevo y . Dado que todos estos valores satisfacen la restricción, se coloca la restricción. Por otro lado, una restricción con esta relación no se coloca en y , ya que la restricción de la tabla anterior a estas dos variables contiene como una tercera fila, y esta evaluación viola esa restricción.
El artilugio universal del orden es el problema de satisfacción de restricciones que contiene todas las restricciones que se pueden colocar para obtener la tabla anterior. Las soluciones del gadget universal incluyen las filas de esta tabla, pero pueden contener otras filas. Si las soluciones son exactamente las filas de la tabla, cada relación se puede expresar proyectando sobre un subconjunto de las variables. Sin embargo, incluso si las soluciones incluyen otras filas, algunas relaciones aún se pueden expresar. Una propiedad del artilugio universal es que es capaz de expresar, mediante proyección, toda relación que pueda expresarse mediante proyección a partir de un problema de satisfacción de restricciones arbitrario basado en el mismo lenguaje. Más precisamente, el artilugio universal del orden expresa todas las relaciones de filas que se pueden expresar en el lenguaje de restricción.
Dada una relación específica, su expresibilidad en el lenguaje se puede verificar considerando una lista arbitraria de variables cuyas columnas en la tabla anterior (las soluciones "ideales" para el dispositivo universal) forman esa relación. La relación puede expresarse en el lenguaje si y solo si las soluciones del dispositivo universal coinciden con la relación cuando se proyecta sobre dicha lista de variables. En otras palabras, se puede verificar la expresibilidad seleccionando variables "como si" las soluciones del dispositivo universal fueran como en la tabla, y luego verificar si la restricción de las soluciones "reales" es realmente la misma que la relación. En el ejemplo anterior, la expresibilidad de la relación en la tabla de la derecha se puede verificar mirando si las soluciones del dispositivo universal, cuando se restringen a las variables y , son exactamente las filas de esta tabla.
Soluciones como funciones en el gadget universal
Una condición necesaria para la manejabilidad se puede expresar en términos de dispositivo universal. Las soluciones de dicho dispositivo se pueden tabular de la siguiente manera:
abcdefgh---------------1 1 1 1 0 0 0 01 1 0 0 1 1 0 0 (soluciones que existen por definición)1 0 1 0 1 0 1 0---------------....1 0 0 1 1 1 0 0 (son posibles otras soluciones)....
Esta mesa se compone de dos partes. La primera parte contiene las soluciones que existen por definición de este problema; la segunda parte (que puede estar vacía) contiene todas las demás soluciones. Dado que las columnas de la tabla están por definición asociadas a los posibles-tuplas de valores del dominio, cada solución puede verse como una función de un -tupla de elementos a un solo elemento.
La función correspondiente a una solución se puede calcular a partir de la primera parte de la tabla anterior y la solución. Como ejemplo, para la última solución marcada en la tabla, esta función se puede determinar para argumentoscomo sigue: primero, estos tres valores son la primera parte de la fila "c" en la tabla; el valor de la función es el valor de la solución en la misma columna, es decir, 0.
Una condición necesaria para la tractabilidad es la existencia de una solución para un dispositivo universal de algún orden que forme parte de algunas clases de funciones. Sin embargo, este resultado solo es válido para los idiomas reducidos, que se definen a continuación.
Funciones de aplastamiento y dominios reducidos
Las funciones de aplastamiento son funciones que se utilizan para reducir el tamaño del dominio de los lenguajes de restricción. Una función de aplastamiento se define en términos de una partición del dominio y un elemento representativo para cada conjunto en la partición. La función de aplastamiento mapea todos los elementos de un conjunto en la partición al elemento representativo de ese conjunto. Para que dicha función sea una función de aplastamiento, también es necesario que la aplicación de la función a todos los elementos de una tupla de una relación en el lenguaje produzca otra tupla en la relación. Se supone que la partición contiene al menos un conjunto de tamaño superior a uno.
Formalmente, dada una partición del dominio que contiene al menos un conjunto de tamaño mayor que uno, una función de aplastamiento es una función tal que para cada en la misma partición, y para cada tupla , se mantiene .
Para problemas de restricción en un lenguaje de restricción que tiene una función de aplastamiento, el dominio se puede reducir mediante la función de aplastamiento. De hecho, cada elemento de un conjunto en la partición puede ser reemplazado con el resultado de aplicarle la función de aplastamiento, ya que este resultado está garantizado para satisfacer al menos todas las restricciones que fueron satisfechas por el elemento. Como resultado, todos los elementos no representativos se pueden eliminar del lenguaje de restricción.
Los lenguajes de restricción para los que no existe una función de aplastamiento se denominan lenguajes reducidos; de manera equivalente, estos son lenguajes en los que se han aplicado todas las reducciones a través de funciones de aplastamiento.
La condición necesaria para la tractabilidad.
La condición necesaria para la tractabilidad basada en el dispositivo universal es válida para lenguajes reducidos. Tal lenguaje es manejable si el dispositivo universal tiene una solución que, cuando se ve como una función en la forma especificada anteriormente, es una función constante, una función mayoritaria, una función binaria idempotente, una función afín o una semiproyección.
Referencias
- Dechter, Rina (2003). Procesamiento de restricciones . Morgan Kaufmann.ISBN 1-55860-890-7
- Vardi, Moshe Y. (2000). "Satisfacción de restricciones y teoría de bases de datos: un tutorial" . PODS 2000 . págs. 76–85.
- Bulatov, Andrei A. (2006). "Un teorema de dicotomía para problemas de satisfacción de restricciones en un conjunto de 3 elementos". Revista de la ACM . 53 (1): 66-120. doi : 10.1145 / 1120582.1120584 . S2CID 18220438 .