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 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 subcasos de tiempo polinomial , en su mayoría obtenidos restringiendo los dominios o restricciones permitidos o la forma en que se pueden imponer 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 .
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 que una serie de otros problemas NP-completos se puedan expresar como problemas de satisfacción de restricciones. Otros problemas similares 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. Como ejemplo, si el dominio es binario y todas las restricciones son binarias , establecer la satisfacibilidad es un problema de tiempo polinómico porque este problema es equivalente a 2-SAT , que es un problema de tiempo polinómico.
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. Ésta es la cuestión de si un conjunto de restricciones contiene sólo restricciones de tiempo polinomial y restricciones NP-completas. Para las restricciones relacionales (ver más abajo), esta cuestión se resolvió positivamente para los dominios booleanos mediante 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 imponiendo restricciones adecuadas a los problemas. Se han considerado varios tipos de restricciones.
La manejabilidad se puede obtener restringiendo los posibles dominios o restricciones. En particular, se han considerado dos tipos de restricciones:
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 logra mediante restricciones estructurales. La restricción estructural se puede comprobar observando únicamente 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 polinómico que resuelve todos los problemas basándose en el lenguaje, es decir, utilizando el dominio y las relaciones especificadas en el dominio. Un ejemplo de lenguaje de restricciones manejable es el de dominios binarios y restricciones binarias. Formalmente, esta restricción corresponde a permitir sólo dominios de tamaño 2 y sólo restricciones cuya relación sea 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 imponer ninguna restricción a 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 3 colores 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 el de los problemas binarios acíclicos. Dado un problema de satisfacción de restricciones solo con 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 bajo 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 binario acíclico 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 a 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 únicamente mediante restricciones relacionales o estructurales. La clase manejable definida en términos de convexidad de filas no puede definirse sólo en términos de las relaciones o sólo 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 puede comprobarse observando únicamente cada restricción por turno).
El subcaso obtenido restringiendo a un lenguaje de restricciones finitas se denomina problema no uniforme . Estos problemas se consideran principalmente al expresar la satisfacción de restricciones en términos del problema de homomorfismo, como se explica a continuación. También se definieron problemas uniformes en el contexto de 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 todas las restricciones son binarias y forman un árbol sobre las variables. Esta es una restricción estructural, ya que puede comprobarse observando únicamente los alcances de las restricciones, ignorando los dominios y las relaciones.
Esta restricción se basa en la gráfica primal del problema, que es una gráfica 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 colocando la condición de ser un árbol en el gráfico primario de problemas que son reformulaciones del original.
Los problemas de satisfacción de restricciones pueden reformularse en términos de otros problemas, lo que lleva a condiciones equivalentes de manejabilidad. La reformulación más utilizada es la del 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 correspondencia entre el problema de la satisfacibilidad de restricciones 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 relacional : es un conjunto de valores y un conjunto de relaciones sobre estos valores. Formalmente, donde cada uno 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, el problema principal es encontrar una asignación satisfactoria; Para una estructura de relación, el principal problema es encontrar la respuesta a una consulta.
Sin embargo, el problema de satisfacción de restricciones 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 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 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 satisfacibilidad del problema de satisfacción de restricciones corresponde a encontrar un valor para cada variable tal que reemplazar un valor en una firma la 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 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 uniformes es una restricción donde la segunda estructura del problema de homomorfismo es fija. En otras palabras, toda estructura relacional define un problema no uniforme, el de saber si una estructura relacional es homomórfica con ella. Se puede imponer una restricción similar a la primera estructura; para cualquier primera estructura fija, el problema del homomorfismo es manejable, porque entonces solo hay un número polinomial de funciones desde la primera estructura a la segunda. Un problema de satisfacción de restricciones uniformes es una restricción arbitraria a los conjuntos de estructuras para la primera y segunda estructuras del problema de homomorfismo.
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.
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 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 comprobar 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 que se pueden resolver en tiempo polinomial , y se sabe que otros expresan problemas NP-completos . Sin embargo, es posible que algunos lenguajes de restricciones no sean ninguno de los dos. Se sabe por el teorema de Ladner que si P no es igual a NP, entonces existen problemas en NP que no son ni de tiempo polinomial ni NP-difíciles. Para problemas de restricciones con un lenguaje de restricciones fijo y sin restricciones estructurales, estos 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 es expresable como problemas de satisfacción de restricciones, el conjunto de todos los lenguajes de restricciones se puede dividir exactamente en los que definen el tiempo polinómico y los que definen los problemas NP-completos; es decir, este conjunto presenta 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 de 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 gráfico fijo no dirigido dado (un gráfico 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 polinómico o NP completo. Más precisamente, el problema es de tiempo polinómico si el gráfico tiene dos colores, es decir, es bipartito y, en caso contrario, es NP completo.
Algunos resultados de complejidad prueban que algunas restricciones son polinómicas sin demostrar que todas las demás restricciones posibles del mismo tipo son NP-duras.
Una condición suficiente para la manejabilidad está relacionada con la expresabilidad en Datalog . Una consulta de registro de datos booleano proporciona un valor de verdad a un conjunto de literales sobre un alfabeto determinado, siendo cada literal una expresión de la forma ; como resultado, una consulta booleana de registro de datos 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 utilizar en las restricciones es fijo; como resultado, se les pueden dar nombres únicos. 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; El hecho de que un conjunto de literales sea satisfactoria depende de las relaciones que especifica el problema no uniforme. Por el contrario, un problema no uniforme indica qué conjuntos de literales representan instancias satisfactibles y cuáles representan instancias insatisfactorias. Una vez nombradas las relaciones, un problema no uniforme expresa un conjunto de conjuntos de literales: aquellos asociados a instancias satisfactibles (o insatisfactibles).
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 booleana de registro de datos. 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 booleana de registro de datos, entonces el problema no uniforme es manejable.
En ocasiones, la satisfacibilidad puede establecerse imponiendo una forma de coherencia local y luego verificando la existencia de un dominio vacío o una relación de restricción. En general, este es un algoritmo de insatisfacibilidad 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 en 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 bajo una restricción. Las siguientes son condiciones en problemas de satisfacción de restricciones binarias donde hacer cumplir la coherencia local es manejable y permite establecer la satisfacibilidad:
Una condición que extiende la última es válida para problemas de satisfacción de restricciones no binarias. Es decir, para todos los problemas para los cuales existe un ordenamiento que hace que el gráfico primario tenga un ancho inducido limitado por una i constante, imponer una fuerte consistencia i direccional es manejable y permite establecer la satisfacibilidad.
Los problemas de satisfacción de restricciones compuestos por restricciones binarias solo pueden verse como gráficos , donde los vértices son variables y las aristas representan la presencia de una restricción entre dos variables. Esta gráfica se llama gráfica de Gaifman o gráfica de restricciones primarias (o simplemente gráfica primaria) del problema.
Si el gráfico primario de un problema es acíclico, establecer la satisfacibilidad del problema es un problema manejable. Esta es una restricción estructural, ya que puede comprobarse observando únicamente 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 supone que está conectado ; como resultado, la condición que generalmente se considera es que los grafos primarios sean á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 problemas equivalentes que solo 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 correspondiente conjunto original de variables; Las restricciones de estos nuevos problemas representan la igualdad de variables 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 un problema equivalente 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 problema. grupo dado de restricciones.
Se ha demostrado que es una condición necesaria para la manejabilidad de un lenguaje de restricciones basado en un 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 proyección.
Una relación que no está presente en un lenguaje de restricciones puede ser "simulada" mediante restricciones que utilizan las relaciones en el lenguaje. En particular, se puede crear una nueva relación colocando un conjunto de restricciones y utilizando sólo 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 artilugio universal se basa en la observación de que cada relación que contiene tuplas puede definirse proyectando una relación que contenga todas las columnas posibles de elementos del dominio. A modo de 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 es 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 conjunto de soluciones, cada relación se puede expresar proyectando sobre un conjunto adecuado de variables. Una forma de intentar obtener esta tabla como conjunto de soluciones es colocar todas las restricciones posibles que no sean violadas por las soluciones requeridas.
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, 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 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 variables. Sin embargo, incluso si las soluciones incluyen otras filas, aún se pueden expresar algunas relaciones. 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 dispositivo universal de orden expresa todas las relaciones de filas que pueden expresarse en el lenguaje de restricciones.
Dada una relación específica, su expresabilidad en el lenguaje puede comprobarse considerando una lista arbitraria de variables cuyas columnas en la tabla anterior (las soluciones "ideales" del dispositivo universal) forman esa relación. La relación puede expresarse en el lenguaje si y sólo si las soluciones del dispositivo universal coinciden con la relación cuando se proyecta sobre dicha lista de variables. En otras palabras, se puede comprobar la expresabilidad seleccionando variables "como si" las soluciones del dispositivo universal fueran como en la tabla, y luego comprobar si la restricción de las soluciones "reales" es realmente la misma que la relación. En el ejemplo anterior, la expresabilidad de la relación en la tabla de la derecha se puede comprobar 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 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 (otras soluciones son posibles)....
Esta mesa está hecha 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 asociadas por definición a las posibles tuplas de valores del dominio, cada solución puede verse como una función desde una tupla de elementos hasta 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 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 los 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 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 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 uno en la misma partición, y para cada tupla , se cumple .
Para problemas de restricciones en un lenguaje de restricciones 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 se puede reemplazar con el resultado de aplicarle la función de aplastamiento, ya que se garantiza que este resultado satisfará al menos todas las restricciones que cumplió el elemento. Como resultado, todos los elementos no representativos se pueden eliminar del lenguaje de restricciones.
Los lenguajes de restricciones para los cuales 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 mediante funciones de aplastamiento.
La condición necesaria para la manejabilidad basada en el dispositivo universal se aplica a las lenguas reducidas. Un lenguaje así es manejable si el artilugio universal tiene una solución que, vista como una función en la forma especificada anteriormente, sea una función constante, una función mayoritaria, una función binaria idempotente, una función afín o una semiproyección.
