La complejidad de la satisfacción de restricciones es la aplicación de la teoría de la complejidad computacional a la satisfacción de restricciones . Se ha estudiado principalmente para discriminar entre clases manejables e intratables de problemas de satisfacción de restricciones en dominios finitos.
La solución de un problema de satisfacción de restricciones en un dominio finito es, en general, un problema NP-completo . Las investigaciones han mostrado una serie de subcasos de tiempo polinómico , en su mayoría obtenidos restringiendo los dominios o restricciones permitidos o la forma en que se pueden imponer restricciones sobre las variables. Las investigaciones también han 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 .
Establecer si un problema de satisfacción de restricciones en un dominio finito tiene soluciones es un problema NP-completo en general. Esta es una consecuencia fácil de una serie de otros problemas NP-completos que se pueden expresar como problemas de satisfacción de restricciones. Estos otros problemas incluyen la satisfacibilidad proposicional y la tricolorabilidad .
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 un problema de tiempo polinomial.
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 restricciones con temas tradicionalmente relacionados con la teoría de bases de datos .
Un problema de investigación considerado es el de la existencia de dicotomías entre conjuntos de restricciones. Se trata de la cuestión de si un conjunto de restricciones contiene solo restricciones de tiempo polinomial y restricciones NP-completas. Para las restricciones relacionales (ver más abajo), esta cuestión fue resuelta positivamente para dominios booleanos por el teorema de dicotomía de Schaefer [1] y para cualquier dominio finito por Andrei Bulatov [2] y Dmitriy Zhuk, [3] de forma independiente, en 2017.
Se pueden obtener subcasos manejables del problema general de satisfacción de restricciones mediante la imposición de restricciones adecuadas a los problemas. Se han considerado varios tipos de restricciones.
La manejabilidad se puede obtener restringiendo los dominios o restricciones posibles. En particular, se han considerado dos tipos de restricciones:
Más precisamente, una restricción relacional especifica un lenguaje de restricciones , 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 dado de relaciones. 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. Esto se hace mediante restricciones estructurales. La restricción estructural se puede verificar observando solo los alcances de las restricciones (sus variables), ignorando sus relaciones (su conjunto de valores satisfactorios).
Un lenguaje de restricciones es manejable si existe un algoritmo polinomial que resuelva todos los problemas basados en el lenguaje, es decir, que utilice 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 cualquiera de las restricciones: las restricciones binarias y los dominios ternarios pueden expresar el problema de 3-coloración de grafos , mientras que las restricciones ternarias y los dominios binarios pueden expresar 3-SAT ; estos dos problemas son ambos NP-completos.
Un ejemplo de una clase manejable definida en términos de una restricción estructural es la de los 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 una arista para cada restricción; dos vértices se unen si están en una restricción. Si el gráfico de un problema es acíclico, el problema también se llama acíclico. El problema de satisfacibilidad en la clase de problema acíclico binario es manejable. Esta es una restricción estructural porque no impone 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 imponen 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, existen algunas clases manejables que no se pueden definir solo mediante restricciones relacionales o solo mediante restricciones estructurales. La clase manejable definida en términos de convexidad de filas no se puede definir solo en términos de las relaciones o solo en términos de la 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 observando solo cada restricción por separado).
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 de 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 formado por un conjunto infinito de problemas no uniformes puede ser intratable incluso si todos estos problemas no uniformes son tratables.
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 comprobar observando únicamente los alcances de las restricciones, ignorando los dominios y las relaciones.
Esta restricción se basa en el grafo primal del problema, que es un grafo cuyos vértices son las variables del problema y las aristas representan la presencia de una restricción entre dos variables. Sin embargo, la manejabilidad también se puede obtener poniendo la condición de ser un árbol al grafo primal de los problemas que son reformulaciones del original.
Los problemas de satisfacción de restricciones pueden reformularse en términos de otros problemas, lo que conduce a condiciones equivalentes a la manejabilidad. La reformulación más utilizada es la que se basa en el problema del homomorfismo .
Se ha proporcionado un vínculo entre la satisfacción de restricciones y la teoría de bases de datos en forma de una correspondencia entre el problema de la satisfacibilidad de restricciones y el problema de verificar si existe un homomorfismo entre dos estructuras relacionales. Una estructura relacional es una representación matemática de una base de datos relacional : es un conjunto de valores y un conjunto de relaciones sobre estos valores. Formalmente, , donde cada una 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 problema principal es encontrar la respuesta a una consulta.
El problema de satisfacción de restricciones está relacionado, sin embargo, 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 entonces .
Se puede establecer una correspondencia directa entre el problema de satisfacción de restricciones y el problema de homomorfismo. Para un problema de satisfacción de restricciones dado, se puede construir un par de estructuras relacionales, la primera codificando las variables y las firmas de las restricciones, la segunda codificando los dominios y las relaciones de las restricciones. La satisfacibilidad del problema de satisfacción de restricciones corresponde a encontrar un valor para cada variable tal que reemplazar un valor en una firma lo convierta 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 ámbito 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 la segunda estructura del problema de homomorfismo es fija. En otras palabras, cada estructura relacional define un problema no uniforme, el de determinar 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 de homomorfismo es manejable, porque entonces solo hay un número polinómico de funciones desde la primera estructura hasta la segunda. Un problema de satisfacción de restricciones uniforme es una restricción arbitraria a los conjuntos de estructuras para la primera y la segunda estructura del problema de homomorfismo.
Dado que el problema del homomorfismo es equivalente a la evaluación de consultas conjuntivas y a la contención de consultas conjuntivas, estos dos problemas también son equivalentes a la satisfacción de restricciones.
Cada restricción puede verse 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 unión interna de las tablas que representan sus restricciones; por lo tanto, el problema de la existencia de soluciones puede reformularse como el problema de verificar si el resultado de una unión interna de varias tablas no está vacío.
Se sabe que algunos lenguajes de restricciones (o problemas no uniformes) corresponden a problemas resolubles en tiempo polinomial , y se sabe que otros expresan problemas NP-completos . Sin embargo, es posible que algunos lenguajes de restricciones no sean ni lo uno ni lo otro. 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 polinomial ni NP-difíciles. Para los problemas de restricciones con un lenguaje de restricciones fijo y sin restricciones estructurales, tales problemas intermedios no existen, como lo demostraron Andrei Bulatov [2] y Dmitriy Zhuk, [3] de forma independiente, en 2017. Si ningún lenguaje de Ladner se puede expresar como problemas de satisfacción de restricciones, el conjunto de todos los lenguajes de restricciones se puede dividir exactamente en aquellos que definen problemas en tiempo polinomial y aquellos que definen problemas NP-completos; es decir, este conjunto exhibe una dicotomía .
Ya se conocían algunos casos particulares del resultado de Bulatov y Zhuk. El resultado más conocido es el teorema de dicotomía de Schaefer , que demuestra 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 seis clases, y es NP-completa en caso contrario. Bulatov demostró un teorema de dicotomía para dominios de tres elementos. [4]
Otro teorema de dicotomía para lenguajes con restricciones es el teorema de Hell-Nesetril, que muestra una dicotomía para problemas sobre restricciones binarias con una única relación simétrica fija . En términos del problema del homomorfismo, cada uno de estos problemas es equivalente a la existencia de un homomorfismo de una estructura relacional a un grafo no dirigido fijo dado (un grafo no dirigido puede considerarse como una estructura relacional con una única relación simétrica binaria). El teorema de Hell-Nesetril demuestra que cada uno de estos problemas es de tiempo polinomial o NP-completo. Más precisamente, el problema es de tiempo polinomial si el grafo es 2-coloreable, es decir, es bipartito , y es NP-completo en caso contrario.
Algunos resultados de complejidad prueban que algunas restricciones son polinómicas sin probar que todas las demás restricciones posibles del mismo tipo sean NP-duras.
Una condición suficiente para la manejabilidad está relacionada con la expresividad en Datalog . Una consulta booleana Datalog otorga 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 booleana 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 verdaderos.
Por otra parte, 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 les pueden dar nombres únicos. Una instancia de este problema no uniforme se puede escribir entonces como un conjunto de literales de la forma . Entre estas instancias/conjuntos de literales, algunas son satisfacibles y otras no; si un conjunto de literales es satisfacible depende de las relaciones, que se especifican mediante el problema no uniforme. A la inversa, un problema no uniforme indica qué conjuntos de literales representan instancias satisfacibles y cuáles representan instancias insatisfacibles. Una vez que se nombran las relaciones, un problema no uniforme expresa un conjunto de conjuntos de literales: aquellos asociados a instancias satisfacibles (o insatisfacibles).
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 booleana. 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 booleana, entonces el problema no uniforme es manejable.
En ocasiones, la satisfacibilidad se puede establecer imponiendo una forma de consistencia local y luego verificando la existencia de un dominio vacío o una relación de restricción. En general, se trata de un algoritmo de insatisfacbilidad correcto pero incompleto: un problema puede ser insatisfacible incluso si no se produce un dominio vacío o una relación de restricción. Para algunas formas de consistencia local, este algoritmo también puede requerir tiempo exponencial. Sin embargo, para algunos problemas y para algunos tipos de consistencia local, es correcto y de tiempo polinomial.
Las siguientes condiciones explotan el gráfico primario del problema, que tiene un vértice para cada variable y una arista entre dos nodos si las variables correspondientes están en una restricción. Las siguientes son condiciones sobre problemas de satisfacción de restricciones binarias donde la aplicación de la consistencia local es factible y permite establecer la satisfacibilidad:
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 grafo primario que tiene un ancho inducido esté limitado por una constante i, imponer una fuerte consistencia direccional i es factible y permite establecer la satisfacibilidad.
Los problemas de satisfacción de restricciones compuestos únicamente por restricciones binarias pueden verse como grafos , donde los vértices son variables y las aristas representan la presencia de una restricción entre dos variables. Este grafo se denomina grafo de Gaifman o grafo de restricción primaria (o simplemente grafo primario) del problema.
Si el grafo primario 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 observando solo los alcances de las restricciones, sin tener en cuenta sus relaciones y el dominio. Un grafo acíclico es un bosque , pero generalmente se supone que existe conectividad ; como resultado, la condición que generalmente se considera es que los grafos 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 otros equivalentes que sólo contienen restricciones binarias dispuestas en forma de á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 conjunto original de variables correspondiente; las restricciones de estos nuevos problemas representan la igualdad de variables que están contenidas en dos conjuntos.
Si el gráfico de uno de esos problemas equivalentes es un árbol, el problema se puede resolver de manera eficiente. Por otra parte, producir uno de esos 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 satisfacen un grupo dado de restricciones.
Se ha demostrado una condición necesaria para la manejabilidad de un lenguaje de restricciones basado en el gadget universal. El gadget universal es un problema particular de satisfacción de restricciones que se definió inicialmente con el fin de expresar nuevas relaciones mediante proyección.
Una relación que no está presente en un lenguaje de restricciones puede ser "simulada" mediante restricciones que utilicen las relaciones del lenguaje. En particular, se puede crear una nueva relación colocando un conjunto de restricciones y utilizando solo algunas de sus variables. Si todas las demás restricciones utilizan 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 cada relación que contiene -tuplas se puede definir proyectando una relación que contenga todas las posibles columnas de elementos del dominio. Como ejemplo, las siguientes tablas muestran dicha 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 restringidas 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 mediante una proyección 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 no sean violadas por las soluciones requeridas.
Por 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 contienen al menos un 1), esta relación se coloca como una restricción en y , porque sus valores en la tabla anterior son , nuevamente, y . Dado que todos estos valores satisfacen la restricción, se coloca la restricción. Por otro lado, no se coloca una restricción con esta relación 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 de orden es el problema de satisfacción de restricciones que contiene todas las restricciones que se pueden establecer para obtener la tabla anterior. Las soluciones del artilugio 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 mediante proyección sobre un subconjunto de las variables. Sin embargo, incluso si las soluciones incluyen otras filas, aún se pueden expresar algunas relaciones. Una propiedad del artilugio universal es que puede expresar, mediante proyección, cada relación que se puede expresar 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 de orden expresa todas las relaciones de filas que se pueden expresar en el lenguaje de restricciones.
Dada una relación específica, su expresibilidad en el lenguaje puede comprobarse considerando una lista arbitraria de variables cuyas columnas en la tabla anterior (las soluciones "ideales" del gadget universal) forman esa relación. La relación puede expresarse en el lenguaje si y solo si las soluciones del gadget universal coinciden con la relación cuando se proyecta sobre dicha lista de variables. En otras palabras, se puede comprobar la expresibilidad seleccionando variables "como si" las soluciones del gadget universal fueran como en la tabla, y luego comprobar si la restricción de las soluciones "reales" es en realidad la misma que la relación. En el ejemplo anterior, la expresibilidad de la relación en la tabla de la derecha puede comprobarse observando si las soluciones del gadget universal, cuando se restringen a las variables y , son exactamente las filas de esta tabla.
Una condición necesaria para la manejabilidad puede expresarse en términos del artilugio universal. Las soluciones de dicho artilugio pueden tabularse 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 tabla 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. Como las columnas de la tabla están asociadas por definición a las posibles -tuplas de valores del dominio, cada solución puede verse como una función de una -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 de la solución. A modo de ejemplo, para la última solución marcada en la tabla, esta función se puede determinar para los argumentos de la siguiente manera: primero, estos tres valores son la primera parte de la fila "c" de 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 manejabilidad 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 sólo es válido para lenguajes reducidos, que se definen a continuación.
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 asigna todos los elementos de un conjunto en la partición al elemento representativo de ese conjunto. Para que una función de este tipo 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 mayor que 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 cumple .
En el caso de problemas de restricción en los que un lenguaje de restricción tiene una función de aplastamiento, el dominio se puede reducir mediante dicha función. De hecho, cada elemento de un conjunto en la partición se puede reemplazar con el resultado de aplicarle la función de aplastamiento, ya que se garantiza que este resultado satisface al menos todas las restricciones que satisfacía el elemento. Como resultado, se pueden eliminar todos los elementos no representativos del lenguaje de restricción.
Los lenguajes de restricciones para los cuales no existen funciones de aplastamiento se denominan lenguajes reducidos; equivalentemente, son lenguajes en los que se han aplicado todas las reducciones mediante funciones de aplastamiento.
La condición necesaria para la manejabilidad basada en el artilugio universal se aplica a los lenguajes reducidos. Un lenguaje de este tipo es manejable si el artilugio universal tiene una solución que, cuando se considera 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.
