2-satisfacibilidad

Theoretical computer science problem

En ciencias de la computación , 2-satisfacebilidad , 2-SAT o simplemente 2SAT es un problema computacional de asignar valores a variables, cada una de las cuales tiene dos valores posibles, para satisfacer un sistema de restricciones sobre pares de variables. Es un caso especial del problema de satisfacibilidad booleano general , que puede involucrar restricciones en más de dos variables, y de problemas de satisfacción de restricciones , que pueden permitir más de dos opciones para el valor de cada variable. Pero a diferencia de los problemas más generales, que son NP-completo , la 2-satisfacibilidad se puede resolver en tiempo polinomial .

Las instancias del problema de 2-satisfacibilidad se expresan típicamente como fórmulas booleanas de un tipo especial, llamadas forma normal conjuntiva (2-CNF) o fórmulas de Krom . Alternativamente, pueden expresarse como un tipo especial de grafo dirigido , el grafo de implicación , que expresa las variables de una instancia y sus negaciones como vértices en un grafo, y las restricciones sobre pares de variables como aristas dirigidas. Ambos tipos de entradas pueden resolverse en tiempo lineal , ya sea mediante un método basado en el retroceso o utilizando los componentes fuertemente conectados del gráfico de implicaciones. Resolución, un método para combinar pares de restricciones para crear restricciones válidas adicionales, también conduce a una solución de tiempo polinomial. Los problemas de 2-satisfacibilidad proporcionan una de las dos principales subclases de las fórmulas conjuntivas de forma normal que se pueden resolver en tiempo polinomial; la otra de las dos subclases es la satisfacibilidad de Horn .

2-la satisfacibilidad se puede aplicar a problemas de geometría y visualización en los que una colección de objetos tiene cada uno dos ubicaciones potenciales y el objetivo es encontrar una ubicación para cada objeto que evite superposiciones con otros objetos. Otras aplicaciones incluyen la agrupación de datos para minimizar la suma de los diámetros de los grupos, la programación del aula y los deportes, y la recuperación de formas a partir de la información sobre sus secciones transversales.

En la teoría de la complejidad computacional , la satisfacibilidad 2 proporciona un ejemplo de un problema NL completo , uno que puede resolverse de manera no determinista utilizando una cantidad logarítmica de almacenamiento y que se encuentra entre los problemas más difíciles que se pueden resolver en este límite de recursos. Al conjunto de todas las soluciones para una instancia de satisfacibilidad 2 se le puede dar la estructura de un gráfico de mediana , pero contar estas soluciones es # P-completoy por lo tanto no se espera que tenga una solución de tiempo polinómico. Las instancias aleatorias experimentan una transición de fase brusca de instancias con solución a instancias sin solución a medida que la proporción de restricciones a variables aumenta más allá de 1, un fenómeno conjeturado pero no probado para formas más complicadas del problema de satisfacibilidad. Una variación computacionalmente difícil de 2-satisfacibilidad, encontrar una asignación de verdad que maximiza el número de restricciones satisfechas, tiene un algoritmo de aproximación cuya optimización depende de la conjetura de juegos únicos , y otra variación difícil, encontrar una asignación satisfactoria que minimiza el número de variables verdaderas, es un caso de prueba importante para la complejidad parametrizada .

Representaciones de problemas

El gráfico de implicaciones para el ejemplo 2-instancia de satisfacibilidad que se muestra en esta sección.

Un problema de 2-satisfacibilidad puede describirse usando una expresión booleana con una forma restringida especial. Es una conjunción (un booleano y una operación) de cláusulas , donde cada cláusula es una disyunción (un booleano o una operación) de dos variables o variables negadas. Las variables o sus negaciones que aparecen en esta fórmula se conocen como literales . ^[1] Por ejemplo, la siguiente fórmula está en forma normal conjuntiva, con siete variables, once cláusulas y 22 literales:

$${\displaystyle {\begin{aligned}&(x_{0}\lor x_{2})\land (x_{0}\lor \lnot x_{3})\land (x_{1}\lor \lnot x_{3})\land (x_{1}\lor \lnot x_{4})\land {}\\&(x_{2}\lor \lnot x_{4})\land {}(x_{0}\lor \lnot x_{5})\land (x_{1}\lor \lnot x_{5})\land (x_{2}\lor \lnot x_{5})\land {}\\&(x_{3}\lor x_{6})\land (x_{4}\lor x_{6})\land (x_{5}\lor x_{6}).\end{aligned}}}$$

El problema de 2-satisfacibilidad es encontrar una asignación de verdad a estas variables que haga que toda la fórmula sea verdadera. Tal asignación elige si hacer que cada una de las variables sea verdadera o falsa, de modo que al menos un literal en cada cláusula se convierta en verdadero. Para la expresión que se muestra arriba, una posible asignación satisfactoria es la que establece las siete variables como verdaderas. Cada cláusula tiene al menos una variable no negada, por lo que esta asignación satisface todas las cláusulas. También hay otras 15 formas de establecer todas las variables para que la fórmula se convierta en verdadera. Por lo tanto, la instancia de 2-satisfacebilidad representada por esta expresión es satisfactoria.

Las fórmulas en esta forma se conocen como fórmulas 2-CNF. El "2" en este nombre representa el número de literales por cláusula, y "CNF" representa la forma normal conjuntiva , un tipo de expresión booleana en forma de conjunción de disyunciones. ^[1] También se denominan fórmulas de Krom, por el trabajo del matemático de UC Davis Melven R. Krom, cuyo artículo de 1967 fue uno de los primeros trabajos sobre el problema de la 2-satisfacibilidad. ^[2]

Cada cláusula en una fórmula 2-CNF es lógicamente equivalente a una implicación de una variable o variable negada a la otra. Por ejemplo, la segunda cláusula del ejemplo puede escribirse de tres formas equivalentes:

$${\displaystyle (x_{0}\lor \lnot x_{3})\;\equiv \;(\lnot x_{0}\Rightarrow \lnot x_{3})\;\equiv \;(x_{3}\Rightarrow x_{0}).}$$

Debido a esta equivalencia entre estos diferentes tipos de operación, una instancia de satisfacibilidad 2 también puede escribirse en forma normal implicativa , en la que reemplazamos cada cláusula o en la forma normal conjuntiva por las dos implicaciones a las que es equivalente. ^[3]

Una tercera forma más gráfica de describir una instancia de satisfacibilidad 2 es como un gráfico de implicaciones . Un gráfico de implicación es un gráfico dirigido en el que hay un vértice por variable o variable negada, y un borde que conecta un vértice con otro siempre que las variables correspondientes están relacionadas por una implicación en la forma normal implicativa de la instancia. Un gráfico de implicación debe ser un gráfico de simetría sesgada , lo que significa que tiene una simetría que lleva cada variable a su negación e invierte las orientaciones de todas las aristas. ^[4]

Algoritmos

Se conocen varios algoritmos para resolver el problema de 2-satisfacibilidad. Los más eficientes toman un tiempo lineal . ^{[2] [4] [5]}

Resolución y cierre transitivo

Krom (1967) describió el siguiente procedimiento de decisión de tiempo polinomial para resolver instancias de 2-satisfacibilidad. ^[2]

Suponga que una instancia de 2-satisfacibilidad contiene dos cláusulas que usan la misma variable x , pero que x se niega en una cláusula y no en la otra. Luego, las dos cláusulas pueden combinarse para producir una tercera cláusula, que tiene los otros dos literales en las dos cláusulas; esta tercera cláusula también debe cumplirse siempre que se cumplan las dos primeras. Por ejemplo, podemos combinar las cláusulas y de esta manera producir la cláusula . En términos de la forma implicativo de una fórmula 2-CNF, esta regla equivale a encontrar dos implicaciones y , e inferir por transitividad tercera implicación . ^[2]${\displaystyle (a\lor b)}$${\displaystyle (\lnot b\lor \lnot c)}$${\displaystyle (a\lor \lnot c)}$${\displaystyle \lnot a\Rightarrow b}$${\displaystyle b\Rightarrow \lnot c}$${\displaystyle \lnot a\Rightarrow \lnot c}$

Krom escribe que una fórmula es consistente si la aplicación repetida de esta regla de inferencia no puede generar tanto las cláusulas como , para cualquier variable . Como demuestra, una fórmula 2-CNF es satisfactoria si y solo si es consistente. Porque, si una fórmula no es consistente, no es posible satisfacer ambas de las dos cláusulas y simultáneamente. Y, si es consistente, entonces la fórmula se puede extender agregando repetidamente una cláusula del formulario o${\displaystyle (x\lor x)}$${\displaystyle (\lnot x\lor \lnot x)}$${\displaystyle x}$${\displaystyle (x\lor x)}$${\displaystyle (\lnot x\lor \lnot x)}$${\displaystyle (x\lor x)}$${\displaystyle (\lnot x\lor \lnot x)}$a la vez, conservando la coherencia en cada paso, hasta que incluya una cláusula de este tipo para cada variable. En cada uno de estos pasos de extensión, siempre se puede agregar una de estas dos cláusulas conservando la coherencia, porque si no, la otra cláusula podría generarse utilizando la regla de inferencia. Una vez que todas las variables tienen una cláusula de esta forma en la fórmula, se puede generar una asignación satisfactoria de todas las variables estableciendo una variable en verdadera si la fórmula contiene la cláusula y estableciendola en falso si la fórmula contiene la cláusula . ^[2]${\displaystyle x}$${\displaystyle (x\lor x)}$${\displaystyle (\lnot x\lor \lnot x)}$

Krom se preocupó principalmente por la integridad de los sistemas de reglas de inferencia, más que por la eficiencia de los algoritmos. Sin embargo, su método conduce a un tiempo polinomial limitado para resolver problemas de satisfacibilidad 2. Al agrupar todas las cláusulas que utilizan la misma variable y aplicar la regla de inferencia a cada par de cláusulas, es posible encontrar todas las inferencias que son posibles a partir de una instancia de 2-CNF determinada y comprobar si es coherente. en el tiempo total O ( n ³ ) , donde n es el número de variables en la instancia. Esta fórmula proviene de multiplicar el número de variables por O ( n ² )número de pares de cláusulas que involucran una variable dada, a las que se puede aplicar la regla de inferencia. Por tanto, es posible determinar si una instancia de 2-CNF dada es satisfactoria en el tiempo O ( n ³ ) . Dado que encontrar una asignación satisfactoria mediante el método de Krom implica una secuencia de comprobaciones de coherencia O ( n ) , llevaría tiempo O ( n ⁴ ) . Incluso, Itai y Shamir (1976) citan un límite de tiempo más rápido de O ( n ² ) para este algoritmo, basado en un orden más cuidadoso de sus operaciones. Sin embargo, incluso este límite de tiempo más pequeño fue mejorado en gran medida por los algoritmos de tiempo lineal posteriores deIncluso, Itai & Shamir (1976) y Aspvall, Plass & Tarjan (1979) .

En términos del gráfico de implicaciones de la instancia de 2-satisfacibilidad, la regla de inferencia de Krom se puede interpretar como la construcción del cierre transitivo del gráfico. Como observa Cook (1971) , también puede verse como una instancia del algoritmo de Davis-Putnam para resolver problemas de satisfacibilidad utilizando el principio de resolución . Su corrección se deriva de la corrección más general del algoritmo de Davis-Putnam. Su límite de tiempo polinomial se deriva del hecho de que cada paso de resolución aumenta el número de cláusulas en la instancia, que está delimitado en la parte superior por una función cuadrática del número de variables. ^[6]

Retroceso limitado

Incluso, Itai y Shamir (1976) describen una técnica que implica un retroceso limitado para resolver problemas de satisfacción de restricciones con variables binarias y restricciones por pares. Aplican esta técnica a un problema de programación del aula, pero también observan que se aplica a otros problemas, incluido el 2-SAT. ^[5]

La idea básica de su enfoque es construir una asignación de verdad parcial, una variable a la vez. Ciertos pasos de los algoritmos son "puntos de elección", puntos en los que se puede dar a una variable cualquiera de dos valores de verdad diferentes, y los pasos posteriores del algoritmo pueden hacer que retroceda a uno de estos puntos de elección. Sin embargo, solo se puede dar marcha atrás a la elección más reciente. Todas las elecciones realizadas antes de la más reciente son permanentes. ^[5]

Inicialmente, no hay un punto de elección y todas las variables están sin asignar. En cada paso, el algoritmo elige la variable cuyo valor establecer, de la siguiente manera:

• Si hay una cláusula cuyas variables ya están establecidas, de una manera que falsifica la cláusula, entonces el algoritmo retrocede hasta su punto de elección más reciente, deshaciendo las asignaciones que hizo desde esa elección, e invierte la decisión tomada en esa elección. Si no hay un punto de elección, o si el algoritmo ya ha retrocedido sobre el punto de elección más reciente, aborta la búsqueda e informa que la fórmula 2-CNF de entrada no es satisfactoria.
• Si hay una cláusula en la que ya se ha establecido una de las dos variables de la cláusula, y la cláusula aún podría convertirse en verdadera o falsa, entonces la otra variable se establece de una manera que obliga a la cláusula a convertirse en verdadera.
• En el caso restante, se garantiza que cada cláusula se hará verdadera sin importar cómo se asignen las variables restantes, o ninguna de sus dos variables ha sido asignada todavía. En este caso, el algoritmo crea un nuevo punto de elección y establece cualquiera de las variables no asignadas en un valor elegido arbitrariamente.

Intuitivamente, el algoritmo sigue todas las cadenas de inferencia después de realizar cada una de sus elecciones. Esto conduce a una contradicción y a un paso atrás, o, si no se deriva ninguna contradicción, se sigue que la elección fue correcta y conduce a una asignación satisfactoria. Por lo tanto, el algoritmo encuentra correctamente una asignación satisfactoria o determina correctamente que la entrada no es satisfactoria. ^[5]

Even et al. no describió en detalle cómo implementar este algoritmo de manera eficiente. Solo afirman que "utilizando estructuras de datos apropiadas para encontrar las implicaciones de cualquier decisión", cada paso del algoritmo (aparte del retroceso) se puede realizar rápidamente. Sin embargo, algunas entradas pueden hacer que el algoritmo retroceda muchas veces, cada vez realizando muchos pasos antes de retroceder, por lo que su complejidad general puede ser no lineal. Para evitar este problema, modifican el algoritmo para que, después de llegar a cada punto de elección, comience a probar simultáneamente ambas asignaciones para el conjunto de variables en el punto de elección, gastando el mismo número de pasos en cada una de las dos asignaciones. Tan pronto como la prueba para una de estas dos asignaciones cree otro punto de elección, la otra prueba se detiene,de modo que en cualquier etapa del algoritmo solo hay dos ramas del árbol de retroceso que aún se están probando. De esta forma, el tiempo total empleado en realizar las dos pruebas para cualquier variable es proporcional al número de variables y cláusulas de la fórmula de entrada cuyos valores se asignan permanentemente. Como resultado, el algoritmo tomatiempo lineal en total. ^[5]

Componentes fuertemente conectados

Aspvall, Plass y Tarjan (1979) encontraron un procedimiento de tiempo lineal más simple para resolver instancias de 2-satisfacibilidad, basado en la noción de componentes fuertemente conectados de la teoría de grafos . ^[4]

Se dice que dos vértices en un gráfico dirigido están fuertemente conectados entre sí si hay un camino dirigido de uno a otro y viceversa. Esta es una relación de equivalencia , y los vértices del gráfico pueden dividirse en componentes fuertemente conectados, subconjuntos dentro de los cuales cada dos vértices están fuertemente conectados. Hay varios algoritmos de tiempo lineal eficientes para encontrar los componentes fuertemente conectados de un gráfico, basados ​​en la primera búsqueda en profundidad : el algoritmo de componentes fuertemente conectados de Tarjan ^[7] y el algoritmo de componentes fuertes basado en ruta ^[8] realizan cada uno una primera búsqueda en profundidad única. El algoritmo de Kosaraju realiza dos primeras búsquedas en profundidad, pero es muy simple.

En términos del gráfico de implicaciones, dos literales pertenecen al mismo componente fuertemente conectado siempre que existan cadenas de implicaciones de un literal a otro y viceversa. Por lo tanto, los dos literales deben tener el mismo valor en cualquier asignación satisfactoria a la instancia de 2-satisfacibilidad dada. En particular, si una variable y su negación pertenecen al mismo componente fuertemente conectado, la instancia no se puede satisfacer, porque es imposible asignar a ambos literales el mismo valor. Como Aspvall et al. demostrado, esta es una condición necesaria y suficiente : una fórmula 2-CNF es satisfactoria si y solo si no hay una variable que pertenezca al mismo componente fuertemente conectado que su negación. ^[4]

Esto conduce inmediatamente a un algoritmo de tiempo lineal para probar la satisfacibilidad de las fórmulas 2-CNF: simplemente realice un análisis de conectividad sólido en el gráfico de implicaciones y verifique que cada variable y su negación pertenezcan a componentes diferentes. Sin embargo, como Aspvall et al. También se mostró, también conduce a un algoritmo de tiempo lineal para encontrar una asignación satisfactoria, cuando existe. Su algoritmo realiza los siguientes pasos:

• Construya el gráfico de implicaciones de la instancia y encuentre sus componentes fuertemente conectados utilizando cualquiera de los algoritmos de tiempo lineal conocidos para un análisis de conectividad sólido.
• Compruebe si algún componente fuertemente conectado contiene tanto una variable como su negación. Si es así, informe que la instancia no es satisfactoria y deténgala.
• Construya la condensación del gráfico de implicaciones, un gráfico más pequeño que tenga un vértice para cada componente fuertemente conectado y un borde desde el componente i al componente j siempre que el gráfico de implicaciones contenga un borde uv tal que u pertenezca al componente i y v pertenezca al componente j . La condensación es automáticamente un gráfico acíclico dirigido y, al igual que el gráfico de implicaciones a partir del cual se formó, es simétrico sesgado .
• Ordena topológicamente los vértices de la condensación. En la práctica, esto se puede lograr de manera eficiente como un efecto secundario del paso anterior, ya que los componentes son generados por el algoritmo de Kosaraju en orden topológico y por el algoritmo de Tarjan en orden topológico inverso. ^[9]
• Para cada componente en el orden topológico inverso, si sus variables aún no tienen asignaciones de verdad, establezca todos los literales en el componente como verdaderos. Esto también hace que todos los literales del componente complementario se establezcan en falso.

Debido al orden topológico inverso y la simetría sesgada, cuando un literal se establece en verdadero, todos los literales a los que se puede acceder a través de una cadena de implicaciones ya se habrán establecido en verdadero. Simétricamente, cuando un literal x se establece en falso, todos los literales que conducen a él a través de una cadena de implicaciones ya se habrán establecido en falso. Por tanto, la asignación de verdad construida por este procedimiento satisface la fórmula dada, que también completa la prueba de corrección de la condición necesaria y suficiente identificada por Aspvall et al. ^[4]

Como Aspvall et al. Para mostrar, también se puede usar un procedimiento similar que implica ordenar topológicamente los componentes fuertemente conectados del gráfico de implicaciones para evaluar fórmulas booleanas totalmente cuantificadas en las que la fórmula que se cuantifica es una fórmula 2-CNF. ^[4]

Aplicaciones

Colocación sin conflictos de objetos geométricos

Varios algoritmos exactos y aproximados para el problema de la colocación automática de etiquetas se basan en la satisfacibilidad 2. Este problema se refiere a la colocación de etiquetas textuales en las características de un diagrama o mapa. Por lo general, el conjunto de posibles ubicaciones para cada etiqueta está muy restringido, no solo por el mapa en sí (cada etiqueta debe estar cerca de la característica que etiqueta y no debe ocultar otras características), sino entre sí: cada dos etiquetas deben evitar la superposición unos a otros, porque de lo contrario se volverían ilegibles. En general, encontrar una ubicación de etiqueta que obedezca estas restricciones es un NP-difícilproblema. Sin embargo, si cada entidad tiene solo dos ubicaciones posibles para su etiqueta (por ejemplo, extendiéndose hacia la izquierda y hacia la derecha de la entidad), la ubicación de la etiqueta se puede resolver en tiempo polinomial. Porque, en este caso, se puede crear una instancia de 2-satisfacibilidad que tenga una variable para cada etiqueta y que tenga una cláusula para cada par de etiquetas que puedan superponerse, evitando que se les asignen posiciones superpuestas. Si todas las etiquetas son rectángulos congruentes, se puede demostrar que la instancia de 2-satisfacibilidad correspondiente solo tiene muchas restricciones lineales, lo que lleva a algoritmos de tiempo casi lineales para encontrar un etiquetado. ^[10] Poon, Zhu y Chin (1998)describir un problema de etiquetado de mapa en el que cada etiqueta es un rectángulo que puede colocarse en una de tres posiciones con respecto a un segmento de línea que etiqueta: puede tener el segmento como uno de sus lados, o puede estar centrado en el segmento . Representan estas tres posiciones utilizando dos variables binarias de tal manera que, nuevamente, probar la existencia de un etiquetado válido se convierte en un problema de 2-satisfacibilidad. ^[11]

Formann y Wagner (1991) utilizan 2-satisfacibilidad como parte de un algoritmo de aproximaciónpara el problema de encontrar etiquetas cuadradas del mayor tamaño posible para un conjunto dado de puntos, con la restricción de que cada etiqueta tiene una de sus esquinas en el punto que etiqueta. Para encontrar un etiquetado con un tamaño determinado, eliminan los cuadrados que, si se duplican, se superpondrían a otro punto, y eliminan los puntos que se pueden etiquetar de una manera que posiblemente no se superponga con la etiqueta de otro punto. Muestran que estas reglas de eliminación hacen que los puntos restantes tengan solo dos posibles ubicaciones de etiqueta por punto, lo que permite encontrar una ubicación de etiqueta válida (si existe una) como la solución para una instancia de 2-satisfacibilidad. Al buscar el tamaño de etiqueta más grande que conduce a una instancia de 2-satisfacibilidad con solución, encuentran una ubicación de etiqueta válida cuyas etiquetas son al menos la mitad del tamaño de la solución óptima. Eso es elLa relación de aproximación de su algoritmo es como máximo dos. ^{[10] [12]} De manera similar, si cada etiqueta es rectangular y debe colocarse de tal manera que el punto que etiqueta esté en algún lugar a lo largo de su borde inferior, entonces use 2-satisfiability para encontrar el tamaño de etiqueta más grande para el que existe una solución. en el que cada etiqueta tiene el punto en una esquina inferior conduce a una relación de aproximación de como máximo dos. ^[13]

Se han realizado aplicaciones similares de satisfacibilidad 2 para otros problemas de ubicación geométrica. En el dibujo de gráficos , si las ubicaciones de los vértices son fijas y cada borde debe dibujarse como un arco circular con una de dos ubicaciones posibles (por ejemplo, como un diagrama de arco ), entonces el problema de elegir qué arco usar para cada borde con el fin de Evitar cruces es un problema de 2-satisfacibilidad con una variable para cada borde y una restricción para cada par de ubicaciones que llevaría a un cruce. Sin embargo, en este caso es posible acelerar la solución, en comparación con un algoritmo que construye y luego busca una representación explícita del gráfico de implicaciones, buscando implícitamente en el gráfico . ^[14] En VLSIdiseño de circuito integrado, si una colección de módulos debe estar conectada por cables que se puedan doblar como máximo una vez, entonces nuevamente hay dos rutas posibles para los cables, y el problema de elegir cuál de estas dos rutas usar, de tal manera que todos los cables se pueden enrutar en una sola capa del circuito, se puede resolver como una instancia de 2-satisfacibilidad. ^[15]

Boros y col. (1999) consideran otro problema de diseño de VLSI: la cuestión de si se debe invertir o no en espejo cada módulo en un diseño de circuito. Esta inversión de espejo deja las operaciones del módulo sin cambios, pero cambia el orden de los puntos en los que las señales de entrada y salida del módulo se conectan a él, posiblemente cambiando qué tan bien encaja el módulo en el resto del diseño. Boros y col.Considere una versión simplificada del problema en el que los módulos ya se han colocado a lo largo de un solo canal lineal, en el que los cables entre los módulos deben enrutarse, y hay un límite fijo en la densidad del canal (el número máximo de señales que debe atravesar cualquier sección transversal del canal). Observan que esta versión del problema puede resolverse como una instancia de 2-satisfacibilidad, en la que las restricciones relacionan las orientaciones de pares de módulos que están directamente a través del canal entre sí. Como consecuencia, la densidad óptima también se puede calcular de manera eficiente, realizando una búsqueda binaria en la que cada paso implica la solución de una instancia de satisfacibilidad 2. ^[dieciséis]

Agrupación de datos

Una forma de agrupar un conjunto de puntos de datos en un espacio métrico en dos grupos es elegir los grupos de tal manera que se minimice la suma de los diámetros.de los grupos, donde el diámetro de cualquier grupo es la mayor distancia entre dos de sus puntos. Esto es preferible a minimizar el tamaño máximo del clúster, lo que puede llevar a que se asignen puntos muy similares a diferentes clústeres. Si se conocen los diámetros objetivo de los dos clústeres, se puede encontrar un clúster que logre esos objetivos resolviendo una instancia de 2-satisfacibilidad. La instancia tiene una variable por punto, que indica si ese punto pertenece al primer grupo o al segundo grupo. Siempre que dos puntos estén demasiado separados entre sí para que ambos pertenezcan al mismo clúster, se agrega una cláusula a la instancia que impide esta asignación.

El mismo método también se puede utilizar como subrutina cuando se desconocen los diámetros de los grupos individuales. Para probar si se puede lograr una determinada suma de diámetros sin conocer los diámetros individuales de los conglomerados, se pueden probar todos los pares máximos de diámetros objetivo que sumen como máximo la suma dada, representando cada par de diámetros como una instancia de 2-satisfacibilidad y usando un algoritmo de 2-satisfacibilidad para determinar si ese par se puede realizar mediante un agrupamiento. Para encontrar la suma óptima de diámetros se puede realizar una búsqueda binaria en la que cada paso es una prueba de viabilidad de este tipo. El mismo enfoque también funciona para encontrar agrupaciones que optimicen otras combinaciones distintas de las sumas de los diámetros de agrupaciones, y que utilicen números de disimilitud arbitrarios (en lugar de distancias en un espacio métrico) para medir el tamaño de una agrupación. ^[17]El tiempo límite para este algoritmo está dominado por el tiempo para resolver una secuencia de instancias de 2-satisfacibilidad que están estrechamente relacionadas entre sí, y Ramnath (2004) muestra cómo resolver estas instancias relacionadas más rápidamente que si se resolvieran independientemente de cada una. otro, lo que lleva a un límite de tiempo total de O ( n ³ ) para el problema de agrupamiento de la suma de diámetros. ^[18]

Programación

Incluso, Itai y Shamir (1976) consideran un modelo de programación del aula en el que se debe programar un conjunto de n profesores para enseñar a cada una de las m cohortes de estudiantes. El número de horas por semana que el maestro dedica a la cohorte se describe mediante la entrada de una matriz que se proporciona como entrada al problema, y ​​cada maestro también tiene un conjunto de horas durante las cuales está disponible para programar. Como muestran, el problema es NP-completo , incluso cuando cada maestro tiene como máximo tres horas disponibles, pero se puede resolver como una instancia de satisfacción 2 cuando cada maestro solo tiene dos horas disponibles. (Los profesores con una sola hora disponible pueden ser fácilmente eliminados del problema). En este problema, cada variable${\displaystyle i}$${\displaystyle j}$${\displaystyle R_{ij}}$${\displaystyle R}$${\displaystyle v_{ij}}$corresponde a una hora que el docente debe dedicar a la cohorte , la asignación a la variable especifica si esa hora es la primera o la segunda de las horas disponibles del docente, y hay una cláusula de 2-satisfacibilidad que previene cualquier conflicto de cualquiera de los dos tipos: dos cohortes asignadas a un maestro al mismo tiempo que las demás, o una cohorte asignada a dos maestros al mismo tiempo. ^[5]${\displaystyle i}$${\displaystyle j}$

Miyashiro y Matsui (2005) aplican 2-satisfacibilidad a un problema de programación deportiva, en el que los emparejamientos de un torneo de todos contra todosya han sido elegidos y los juegos deben asignarse a los estadios de los equipos. En este problema, es deseable alternar partidos de local y visitante en la medida de lo posible, evitando "descansos" en los que un equipo juega dos partidos de local seguidos o dos partidos de visitante seguidos. Como máximo, dos equipos pueden evitar los descansos por completo, alternando entre partidos en casa y fuera; ningún otro equipo puede tener el mismo horario de local que estos dos, porque entonces no podría jugar contra el equipo con el que tenía el mismo horario. Por lo tanto, un horario óptimo tiene dos equipos sin descanso y un solo descanso para todos los demás equipos. Una vez que se elige uno de los equipos sin descanso, se puede establecer un problema de 2-satisfacibilidad en el que cada variable representa la asignación de local para un solo equipo en un solo juego,y las restricciones imponen las propiedades de que dos equipos tienen una asignación consistente para sus juegos, que cada equipo tiene como máximo un descanso antes y como máximo un descanso después del juego con el equipo sin descanso, y que ningún equipo tiene dos descansos. Por lo tanto, se puede probar si un programa admite una solución con el número óptimo de descansos resolviendo un número lineal de problemas de 2-satisfacibilidad, uno para cada elección del equipo sin interrupciones. Una técnica similar también permite encontrar horarios en los que cada equipo tiene un solo descanso, y maximizar en lugar de minimizar el número de descansos (para reducir el kilometraje total recorrido por los equipos).Se puede probar si un cronograma admite una solución con el número óptimo de descansos resolviendo un número lineal de problemas de 2-satisfacibilidad, uno para cada elección del equipo sin interrupciones. Una técnica similar también permite encontrar horarios en los que cada equipo tiene un solo descanso, y maximizar en lugar de minimizar el número de descansos (para reducir el kilometraje total recorrido por los equipos).Se puede probar si un cronograma admite una solución con el número óptimo de descansos resolviendo un número lineal de problemas de 2-satisfacibilidad, uno para cada elección del equipo sin interrupciones. Una técnica similar también permite encontrar horarios en los que cada equipo tiene un solo descanso, y maximizar en lugar de minimizar el número de descansos (para reducir el kilometraje total recorrido por los equipos).^[19]

Tomografía discreta

Ejemplo de un rompecabezas de un nonograma que se está resolviendo.

La tomografía es el proceso de recuperar formas de sus secciones transversales. En la tomografía discreta , una versión simplificada del problema que se ha estudiado con frecuencia, la forma a recuperar es un poliomino (un subconjunto de los cuadrados en el retículo cuadrado bidimensional ), y las secciones transversales proporcionan información agregada sobre los conjuntos. de cuadrados en filas y columnas individuales de la celosía. Por ejemplo, en los populares acertijos de nonogramas , también conocidos como pintar por números o cuadrículas, el conjunto de cuadrados a determinar representa los píxeles oscuros en una imagen binaria., y la información proporcionada al solucionador de acertijos le dice cuántos bloques consecutivos de píxeles oscuros debe incluir en cada fila o columna de la imagen, y la longitud que debe tener cada uno de esos bloques. En otras formas de tomografía digital, se proporciona incluso menos información sobre cada fila o columna: solo el número total de cuadrados, en lugar del número y la longitud de los bloques de cuadrados. Una versión equivalente del problema es que debemos recuperar una matriz 0-1 dada dadas solo las sumas de los valores en cada fila y en cada columna de la matriz.

Aunque existen algoritmos de tiempo polinomial para encontrar una matriz con sumas de filas y columnas dadas, ^[20] la solución puede estar lejos de ser única: cualquier submatriz en forma de matriz de identidad 2 × 2 puede complementarse sin afectar la corrección de la solución. . Por lo tanto, los investigadores han buscado restricciones en la forma a reconstruir que puedan usarse para restringir el espacio de soluciones. Por ejemplo, se podría suponer que la forma está conectada; sin embargo, probar si existe una solución conectada es NP-completo. ^[21] Una versión aún más restringida que es más fácil de resolver es que la forma es ortogonalmente convexa.: tener un solo bloque contiguo de cuadrados en cada fila y columna. Mejorando varias soluciones anteriores, Chrobak & Dürr (1999) mostraron cómo reconstruir formas convexas ortogonalmente conectadas de manera eficiente, utilizando 2-SAT. ^[22]La idea de su solución es adivinar los índices de las filas que contienen las celdas más a la izquierda y más a la derecha de la forma que se va a reconstruir, y luego establecer un problema de 2-satisfacibilidad que prueba si existe una forma consistente con estas conjeturas y con la forma dada. sumas de filas y columnas. Usan cuatro variables de 2-satisfacibilidad para cada cuadrado que podría ser parte de la forma dada, una para indicar si pertenece a cada una de las cuatro posibles "regiones de esquina" de la forma, y ​​usan restricciones que obligan a estas regiones a ser disjuntas. tener las formas deseadas, formar una forma general con filas y columnas contiguas, y tener las sumas de filas y columnas deseadas. Su algoritmo toma el tiempo O ( m ³ n ) donde mes la menor de las dos dimensiones de la forma de entrada yn es la mayor de las dos dimensiones. El mismo método se extendió más tarde a formas ortogonalmente convexas que podrían conectarse solo en diagonal en lugar de requerir conectividad ortogonal. ^[23]

Como parte de un solucionador de acertijos completos de nonogramas, Batenburg y Kosters ( 2008 , 2009 ) utilizaron 2-satisfacibilidad para combinar información obtenida de varias otras heurísticas . Dada una solución parcial al rompecabezas, utilizan la programación dinámica dentro de cada fila o columna para determinar si las restricciones de esa fila o columna obligan a cualquiera de sus cuadrados a ser blanco o negro, y si dos cuadrados cualesquiera de la misma fila o columna pueden hacerlo. estar conectado por una relación de implicación. También transforman el nonograma en un problema de tomografía digital al reemplazar la secuencia de longitudes de bloque en cada fila y columna por su suma, y ​​usan un flujo máximoformulación para determinar si este problema de tomografía digital que combina todas las filas y columnas tiene algún cuadrado cuyo estado se pueda determinar o pares de cuadrados que se puedan conectar por una relación de implicación. Si alguna de estas dos heurísticas determina el valor de uno de los cuadrados, se incluye en la solución parcial y se repiten los mismos cálculos. Sin embargo, si ambas heurísticas no logran establecer ningún cuadrado, las implicaciones encontradas por ambas se combinan en un problema de 2-satisfacibilidad y se usa un solucionador de 2-satisfacibilidad para encontrar cuadrados cuyo valor está fijado por el problema, después de lo cual el procedimiento es repitió de nuevo. Este procedimiento puede tener éxito o no en encontrar una solución, pero se garantiza que se ejecutará en tiempo polinomial. Batenburg y Kosters informan que, aunque la mayoría de los rompecabezas de los periódicos no necesitan toda su potencia,tanto este procedimiento como un procedimiento más poderoso pero más lento que combina este enfoque de 2-satisfacibilidad con el retroceso limitado deIncluso, Itai y Shamir (1976) ^[5] son significativamente más efectivos que la programación dinámica y la heurística de flujo sin 2-satisfacibilidad cuando se aplican a nonogramas generados aleatoriamente más difíciles. ^[24]

Satisfacción de Cuerno Renamable

Junto a 2-satisfacibilidad, la otra subclase principal de problemas de satisfacibilidad que se puede resolver en tiempo polinomial es la satisfacibilidad de Horn . En esta clase de problemas de satisfacibilidad, la entrada es nuevamente una fórmula en forma normal conjuntiva. Puede tener arbitrariamente muchos literales por cláusula pero como máximo un literal positivo. Lewis (1978) encontró una generalización de esta clase, renombrable satisfacibilidad de Horn , que aún puede resolverse en tiempo polinomial por medio de una instancia auxiliar 2-satisfacibilidad. Una fórmula se renombra Horncuando es posible ponerlo en forma de Horn reemplazando algunas variables por sus negaciones. Para hacerlo, Lewis configura una instancia de 2-satisfacibilidad con una variable para cada variable de la instancia de Horn renombrable, donde las variables de 2-satisfacibilidad indican si se niegan o no las correspondientes variables de Horn renombrables. Para producir una instancia de Horn, no deben aparecer dos variables que aparezcan en la misma cláusula de la instancia de Horn renombrable en esa cláusula; esta restricción sobre un par de variables es una restricción de 2-satisfacibilidad. Al encontrar una asignación satisfactoria a la instancia de 2-satisfacibilidad resultante, Lewis muestra cómo convertir cualquier instancia de Horn renombrable en una instancia de Horn en tiempo polinomial. ^[25]Al dividir las cláusulas largas en varias cláusulas más pequeñas y aplicar un algoritmo de 2-satisfacibilidad de tiempo lineal, es posible reducir esto a tiempo lineal. ^[26]

Otras aplicaciones

2-la satisfacibilidad también se ha aplicado a problemas de reconocimiento de gráficos no dirigidos que se pueden dividir en un conjunto independiente y un pequeño número de subgrafos bipartitos completos , ^[27] infiriendo relaciones comerciales entre subsistemas autónomos de Internet, ^[28] y reconstrucción de evolutivos árboles . ^[29]

Complejidad y extensiones

NL-completitud

Un algoritmo no determinista para determinar si una instancia de 2-satisfacibilidad no es satisfactoria, usando solo una cantidad logarítmica de memoria de escritura, es fácil de describir: simplemente elija (no deterministamente) una variable v y busque (no deterministamente) una cadena de implicaciones que comiencen desde v. a su negación y luego de regreso al v . Si se encuentra tal cadena, la instancia no puede ser satisfactoria. Según el teorema de Immerman-Szelepcsényi , también es posible en el espacio logarítmico no determinista verificar que una instancia de 2-satisfacibilidad satisfactoria es satisfactoria.

2-satisfacibilidad es NL-completo , ^[30] lo que significa que es uno de los problemas "más difíciles" o "más expresivos" en la clase de complejidad NL de problemas que se pueden resolver de forma no determinista en el espacio logarítmico. La completitud aquí significa que una máquina de Turing determinista que usa solo espacio logarítmico puede transformar cualquier otro problema en NL en un problema de 2-satisfacibilidad equivalente. De manera análoga a resultados similares para la clase de complejidad NP más conocida , esta transformación junto con el teorema de Immerman-Szelepcsényi permiten representar cualquier problema en NL como una lógica de segundo ordenfórmula con un solo predicado cuantificado existencialmente con cláusulas limitadas a la longitud 2. Tales fórmulas se conocen como SO-Krom. ^[31] De manera similar, la forma normal implicativa se puede expresar en lógica de primer orden con la adición de un operador para el cierre transitivo . ^[31]

El conjunto de todas las soluciones

El gráfico de la mediana que representa todas las soluciones al ejemplo ejemplo 2-satisfacibilidad cuya gráfica implicación se muestra arriba.

El conjunto de todas las soluciones para una instancia de satisfacibilidad 2 tiene la estructura de un gráfico mediano , en el que un borde corresponde a la operación de invertir los valores de un conjunto de variables que están todas restringidas a ser iguales o desiguales entre sí. En particular, siguiendo los bordes de esta manera se puede pasar de cualquier solución a cualquier otra solución. Por el contrario, cualquier gráfico de mediana se puede representar como el conjunto de soluciones para una instancia de satisfacibilidad 2 de esta manera. La mediana de cualesquiera tres soluciones se forma estableciendo cada variable en el valor que tiene en la mayoría de las tres soluciones. Esta mediana siempre forma otra solución para la instancia. ^[32]

Feder (1994) describe un algoritmo para enumerar de manera eficiente todas las soluciones a una instancia dada de 2-satisfacibilidad y para resolver varios problemas relacionados. ^[33] También existen algoritmos para encontrar dos asignaciones satisfactorias que tengan la máxima distancia de Hamming entre sí. ^[34]

Contando el número de asignaciones satisfactorias

# 2SAT es el problema de contar el número de asignaciones satisfactorias para una fórmula 2-CNF dada. Este problema de conteo es # P-completo , ^{[35] lo} que implica que no se puede resolver en tiempo polinómico a menos que P = NP . Además, no existe un esquema de aproximación aleatoria completamente polinomial para # 2SAT a menos que NP = RP y esto incluso se mantiene cuando la entrada está restringida a fórmulas monótonas 2-CNF, es decir, fórmulas 2-CNF en las que cada literal es una ocurrencia positiva de una variable . ^[36]

El algoritmo más rápido conocido para calcular el número exacto de asignaciones satisfactorias a una fórmula 2SAT se ejecuta en el tiempo . ^{[37] [38] [39]}${\displaystyle O(1.2377^{n})}$

Instancias aleatorias de 2-satisfacibilidad

Se puede formar una instancia de 2-satisfacibilidad al azar, para un número dado n de variables ym de cláusulas, eligiendo cada cláusula de manera uniforme al azar del conjunto de todas las cláusulas de dos variables posibles. Cuando m es pequeño en relación con n , tal instancia probablemente será satisfactoria, pero los valores más grandes de m tienen menores probabilidades de ser satisfactorios. Más precisamente, si m / n se fija como una constante α ≠ 1, la probabilidad de satisfacibilidad tiende a un límite cuando n llega al infinito: si α <1, el límite es uno, mientras que si α> 1, el límite es cero . Por lo tanto, el problema presenta una transición de fase.en α = 1. ^[40]

Máxima-2-satisfacibilidad

En el problema de máxima-2-satisfacibilidad ( MAX-2-SAT ), la entrada es una fórmula en forma normal conjuntiva con dos literales por cláusula, y la tarea es determinar el número máximo de cláusulas que pueden ser satisfechas simultáneamente por una asignación. . Al igual que el problema de satisfacción máxima más general , MAX-2-SAT es NP-hard . La prueba es por reducción de 3SAT . ^[41]

Al formular MAX-2-SAT como un problema de encontrar un corte (es decir, una partición de los vértices en dos subconjuntos) maximizando el número de aristas que tienen un punto final en el primer subconjunto y un punto final en el segundo, en un gráfico relacionado con el gráfico de implicaciones, y aplicando métodos de programación semidefinidos a este problema de corte, es posible encontrar en tiempo polinomial una solución aproximada que satisfaga al menos 0.940 ... veces el número óptimo de cláusulas. ^[42] Una instancia de MAX 2-SAT balanceada es una instancia de MAX 2-SAT donde cada variable aparece positiva y negativamente con el mismo peso. Para este problema, Austrin ha mejorado la relación de aproximación a . ^[43]${\displaystyle \min \left\{(3-\cos \theta )^{-1}(2+(2/\pi )\theta )\,:\,\pi /2\leq \theta \leq \pi \right\}=0.943...}$

Si la conjetura de los juegos únicos es cierta, entonces es imposible aproximar MAX 2-SAT, balanceado o no, con una constante de aproximación mejor que 0.943 ... en tiempo polinomial. ^[44] Bajo el supuesto más débil de que P ≠ NP , solo se sabe que el problema es inapropiable dentro de una constante mejor que 21/22 = 0,95454 ... ^[45]

Varios autores también han explorado límites de tiempo exponenciales en el peor de los casos para la solución exacta de instancias MAX-2-SAT. ^[46]

Satisfacción ponderada 2

En el problema de satisfacibilidad 2 ponderado ( W2SAT ), la entrada es una instancia de 2SAT variable y un número entero k , y el problema es decidir si existe una asignación satisfactoria en la que como máximo k de las variables son verdaderas.${\displaystyle n}$

El problema W2SAT incluye como caso especial el problema de la cobertura de vértices , de encontrar un conjunto de k vértices que juntos tocan todos los bordes de un gráfico no dirigido dado. Para cualquier instancia dada del problema de cobertura de vértices, se puede construir un problema W2SAT equivalente con una variable para cada vértice de una gráfica. Cada arista uv de la gráfica se puede representar mediante una cláusula 2SAT u ∨ v que solo se puede satisfacer al incluir u o v entre las verdaderas variables de la solución. Luego, las instancias satisfactorias de la fórmula 2SAT resultante codifican soluciones al problema de cobertura de vértices, y hay una asignación satisfactoria con kVariables verdaderas si y solo si hay una cubierta de vértice con k vértices. Por lo tanto, al igual que la cobertura de vértices, W2SAT es NP-completo .

Además, en la complejidad parametrizada, W2SAT proporciona un problema natural W [1] -completo , ^{[47] lo} que implica que W2SAT no es manejable con parámetros fijos a menos que esto sea válido para todos los problemas en W [1] . Es decir, es poco probable que exista un algoritmo para W2SAT cuyo tiempo de ejecución adopte la forma f ( k ) · n ^{O (1)} . Aún más fuertemente, W2SAT no se puede resolver en el tiempo n ^{o ( k ) a} menos que falle la hipótesis del tiempo exponencial . ^[48]

Fórmulas booleanas cuantificadas

Además de encontrar el primer algoritmo de tiempo polinómico para la satisfacibilidad 2, Krom (1967) también formuló el problema de evaluar fórmulas booleanas totalmente cuantificadas en las que la fórmula que se cuantifica es una fórmula 2-CNF. El problema de 2-satisfacibilidad es el caso especial de este problema 2-CNF cuantificado, en el que todos los cuantificadores son existenciales . Krom también desarrolló un procedimiento de decisión eficaz para estas fórmulas. Aspvall, Plass y Tarjan (1979) demostraron que se puede resolver en tiempo lineal, mediante una extensión de su técnica de componentes fuertemente conectados y ordenamiento topológico. ^{[2] [4]}

Lógicas de muchos valores

También se puede plantear el problema de la 2-satisfacibilidad para lógicas proposicionales de muchos valores . Los algoritmos no suelen ser lineales y, para algunas lógicas, el problema es incluso NP-completo. Ver Hähnle ( 2001 , 2003 ) para encuestas. ^[49]

Referencias

1. Prestwich, Steven (2009), "2. Codificaciones CNF" , en Biere, Armin; Heule, Marijn ; van Maaren, Hans; Walsh, Toby (eds.), Handbook of Satisfiability , Frontiers in Artificial Intelligence and Applications, 185 , IOS Press, págs. 75–98, doi : 10.3233 / 978-1-58603-929-5-75 , ISBN 978-1-58603-929-5.
2. Krom, Melven R. (1967), "El problema de decisión para una clase de fórmulas de primer orden en las que todas las disyunciones son binarias", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , 13 (1-2 ): 15-20, doi : 10.1002 / malq.19670130104.
3. Russell, Stuart Jonathan; Norvig, Peter (2010), Inteligencia artificial: un enfoque moderno , serie de Prentice Hall en inteligencia artificial, Prentice Hall, p. 282, ISBN 978-0-13-604259-4.
4. Aspvall, Bengt; Plass, Michael F .; Tarjan, Robert E. (1979), "Un algoritmo de tiempo lineal para probar la verdad de ciertas fórmulas booleanas cuantificadas" (PDF) , Information Processing Letters , 8 (3): 121-123, doi : 10.1016 / 0020-0190 ( 79) 90002-4 .
5. Par, S .; Itai, A .; Shamir, A. (1976), "Sobre la complejidad del calendario y los problemas de flujo de múltiples productos", SIAM Journal on Computing , 5 (4): 691–703, doi : 10.1137 / 0205048.
6. Cook, Stephen A. (1971), "La complejidad de los procedimientos de demostración de teoremas", Proc. 3er ACM Symp. Teoría de la Computación (STOC) , págs. 151-158, doi : 10.1145 / 800157.805047.
7. Tarjan, Robert E. (1972), "Búsqueda en profundidad primero y algoritmos de gráficos lineales", SIAM Journal on Computing , 1 (2): 146-160, doi : 10.1137 / 0201010.
8. Publicado por primera vez por Cheriyan, J .; Mehlhorn, K. (1996), "Algoritmos para redes y gráficos densos en la computadora de acceso aleatorio", Algorithmica , 15 (6): 521–549, doi : 10.1007 / BF01940880. Redescubierto en 1999 por Harold N. Gabow, y publicado en Gabow, Harold N. (2003), "Searching (Ch 10.1)", en Gross, JL; Yellen, J. (eds.), Matemáticas discretas. y sus aplicaciones: Handbook of Graph Theory , 25 , CRC Press, págs. 953–984.
9. Harrison, Paul, Clasificación topológica robusta y algoritmo de Tarjan en Python , consultado el 9 de febrero de 2011
10. Formann, M .; Wagner, F. (1991), "Un problema de empaquetado con aplicaciones a la rotulación de mapas", Proc. Séptimo Simposio de ACM sobre geometría computacional , págs. 281–288, doi : 10.1145 / 109648.109680 , ISBN 978-0-89791-426-0.
11. Poon, Chung Keung; Zhu, Binhai; Chin, Francis (1998), "Una solución de tiempo polinomial para etiquetar un mapa rectilíneo", Information Processing Letters , 65 (4): 201-207, doi : 10.1016 / S0020-0190 (98) 00002-7.
12. Wagner, Frank; Wolff, Alexander (1997), "Un algoritmo práctico de etiquetado de mapas", Geometría computacional: teoría y aplicaciones , 7 (5–6): 387–404, doi : 10.1016 / S0925-7721 (96) 00007-7.
13. Doddi, Srinivas; Marathe, Madhav V .; Mirzaian, Andy; Moret, Bernard ME; Zhu, Binhai (1997), "Etiquetado de mapas y sus generalizaciones", Proc. 8vo ACM-SIAM Symp. Algoritmos discretos (SODA) , Soda '97, págs. 148-157, ISBN 9780898713909.
14. Efrat, Alon; Erten, Cesim; Kobourov, Stephen G. (2007), "Dibujo de arco circular de ubicación fija de gráficos planares" (PDF) , Journal of Graph Algorithms and Applications , 11 (1): 145-164, doi : 10.7155 / jgaa.00140 .
15. Raghavan, Raghunath; Cohoon, James; Sahni, Sartaj (1986), "Cableado de una sola curva", Journal of Algorithms , 7 (2): 232-237, doi : 10.1016 / 0196-6774 (86) 90006-4.
16. Boros, Endre; Hammer, Peter Ladislaw ; Minoux, Michel; Rader, David J., Jr. (1999), "Cambio de celda óptimo para minimizar la densidad de canal en el diseño VLSI y optimización pseudo-booleana", Discrete Applied Mathematics , 90 (1-3): 69-88, doi : 10.1016 / S0166 -218X (98) 00114-0.
17. Hansen, P .; Jaumard, B. (1987), "Suma mínima de diámetros agrupados", Journal of Classification , 4 (2): 215-226, doi : 10.1007 / BF01896987.
18. Ramnath, Sarnath (2004), "La conectividad dinámica del dígrafo acelera la agrupación mínima de suma de diámetros", SIAM Journal on Discrete Mathematics , 18 (2): 272-286, doi : 10.1137 / S0895480102396099.
19. Miyashiro, Ryuhei; Matsui, Tomomi (2005), "Un algoritmo de tiempo polinomial para encontrar una asignación equitativa en casa fuera", Cartas de investigación de operaciones , 33 (3): 235–241, CiteSeerX 10.1.1.64.240 , doi : 10.1016 / j.orl .2004.06.004 .
20. Brualdi, RA (1980), "Matrices de ceros y unos con vectores de suma de filas y columnas fijas", Linear Algebra Appl. , 33 : 159–231, doi : 10.1016 / 0024-3795 (80) 90105-6.
21. Woeginger, GJ (1996), La reconstrucción de poliominós a partir de sus proyecciones ortogonales , Informe técnico SFB-65, Graz, Austria: TU Graz.
22. Chrobak, Marek; Dürr, Christoph (1999), "Reconstrucción de poliominós hv-convexos a partir de proyecciones ortogonales", Information Processing Letters , 69 (6): 283-289, arXiv : cs / 9906021 , Bibcode : 1999cs ........ 6021D , doi : 10.1016 / S0020-0190 (99) 00025-3.
23. Kuba, Atila; Balogh, Emese (2002), "Reconstrucción de conjuntos discretos 2D convexos en tiempo polinomial", Informática teórica , 283 (1): 223–242, doi : 10.1016 / S0304-3975 (01) 00080-9; Brunetti, Sara; Daurat, Alain (2003), "Un algoritmo que reconstruye conjuntos de celosías convexas" (PDF) , Ciencias de la computación teóricas , 304 (1-3): 35-57, doi : 10.1016 / S0304-3975 (03) 00050-1 .
24. Batenburg, K. Joost; Kosters, Walter A. (2008), "Un marco de razonamiento para la resolución de nonogramas", Análisis combinatorio de imágenes, 12th International Workshop, IWCIA 2008, Buffalo, NY, EE. UU., 7 al 9 de abril de 2008, Actas , Lecture Notes in Computer Science, 4958 , Springer-Verlag, págs. 372–383, doi : 10.1007 / 978-3-540-78275-9_33 , ISBN 978-3-540-78274-2; Batenburg, K. Joost; Kosters, Walter A. (2009), "Resolver nonogramas combinando relajaciones", Reconocimiento de patrones , 42 (8): 1672-1683, CiteSeerX 10.1.1.177.76 , doi : 10.1016 / j.patcog.2008.12.003 .
25. Lewis, Harry R. (1978), "Cambiar el nombre de un conjunto de cláusulas como un conjunto de Horn", Journal of the ACM , 25 (1): 134-135, doi : 10.1145 / 322047.322059 , MR 0468315 .
26. Aspvall, Bengt (1980), "Reconociendo casos NR (1) disfrazados del problema de satisfacibilidad", Journal of Algorithms , 1 (1): 97-103, doi : 10.1016 / 0196-6774 (80) 90007-3 , MR 0578079 .
27. Brandstädt, Andreas ; Hammer, Peter Ladislaw ; Le, Van Bang; Lozin, Vadim V. (2005), "Bisplit graphs", Discrete Mathematics , 299 (1-3): 11-32, doi : 10.1016 / j.disc.2004.08.046.
28. Wang, Hao; Xie, Haiyong; Yang, Yang Richard; Silberschatz, Avi; Li, Li Erran; Liu, Yanbin (2005), "Selección de ruta de salida estable para ingeniería de tráfico entre dominios: modelo y análisis", 13ª Conf. IEEE. Protocolos de red (ICNP) , págs. 16–29, CiteSeerX 10.1.1.106.7345 , doi : 10.1109 / ICNP.2005.39 , ISBN  978-0-7695-2437-5.
29. Eskin, Eleazar; Halperin, Eran; Karp, Richard M. (2003), "Reconstrucción eficiente de la estructura del haplotipo a través de la filogenia perfecta", Journal of Bioinformatics and Computational Biology , 1 (1): 1–20, doi : 10.1142 / S0219720003000174 , PMID 15290779 .
30. Papadimitriou, Christos H. (1994), Complejidad computacional , Addison-Wesley, págs. Capítulo 4.2, ISBN 978-0-201-53082-7., Thm. 16.3.
31. Cook, Stephen ; Kolokolova, Antonina (2004), "A Second-Order Theory for NL", XIX Simposio anual del IEEE sobre lógica en la informática (LICS'04) , págs. 398–407, doi : 10.1109 / LICS.2004.1319634 , ISBN 978-0-7695-2192-3.
32. Bandelt, Hans-Jürgen; Chepoi, Victor (2008), "Teoría y geometría de grafos métricos: una encuesta", Encuestas sobre geometría discreta y computacional , Matemáticas contemporáneas, 453 , Providence, RI: American Mathematical Society, págs. 49-86, doi : 10.1090 / conm / 453/08795 , ISBN 9780821842393, MR  2405677. Chung, FRK ; Graham, RL ; Saks, ME (1989), "Un problema de ubicación dinámica para gráficos" (PDF) , Combinatorica , 9 (2): 111-132, doi : 10.1007 / BF02124674 . Feder, T. (1995), Redes estables y gráficos de productos , Memorias de la Sociedad Matemática Estadounidense, 555.
33. Feder, Tomás (1994), "Network flow and 2-satisfiability", Algorithmica , 11 (3): 291–319, doi : 10.1007 / BF01240738.
34. Angelsmark, Ola; Thapper, Johan (2005), "Algoritmos para el problema de máxima distancia de Hamming", Recent Advances in Constraints , Lecture Notes in Computer Science, 3419 , Springer-Verlag, pp.  128-141 , doi : 10.1007 / 11402763_10 , ISBN 978-3-540-25176-7.
35. Valiant, Leslie G. (1979), "La complejidad de los problemas de enumeración y confiabilidad", SIAM Journal on Computing , 8 (3): 410–421, doi : 10.1137 / 0208032
36. Galés, Dominic ; Gale, Amy (2001), "La complejidad de los problemas de conteo", Aspectos de la complejidad: minicursos de algorítmica, complejidad y álgebra computacional: taller de matemáticas, Kaikoura, 7 al 15 de enero de 2000 , págs. 115 y ss., Teorema 57.
37. Dahllöf, Vilhelm; Jonsson, Peter; Wahlström, Magnus (2005), "Modelos de conteo para fórmulas 2SAT y 3SAT", Informática teórica , 332 (1-3): 265-291, doi : 10.1016 / j.tcs.2004.10.037
38. Furero, Martín; Kasiviswanathan, Shiva Prasad (2007), "Algoritmos para contar soluciones 2-SAT y colorantes con aplicaciones", Aspectos algorítmicos en información y gestión , Lecture Notes in Computer Science, 4508 , Springer-Verlag, pp. 47-57, CiteSeerX 10.1. 1.634.4498 , doi : 10.1007 / 978-3-540-72870-2_5 , ISBN  978-3-540-72868-9.
39. Wahlström, Magnus (2008), "Un límite más estricto para contar soluciones de peso máximo en instancias 2sat", Taller internacional sobre cómputo parametrizado y exacto , Lecture Notes in Computer Science, 5018 , pp. 202-213, CiteSeerX 10.1.1.129. 9232 , doi : 10.1007 / 978-3-540-79723-4_19 , ISBN  978-3-540-79722-7
40. Bollobás, Béla ; Borgs, Christian; Chayes, Jennifer T .; Kim, Jeong Han; Wilson, David B. (2001), "La ventana de escalado de la transición 2-SAT", Estructuras y algoritmos aleatorios , 18 (3): 201-256, arXiv : math / 9909031 , doi : 10.1002 / rsa.1006; Chvátal, V .; Reed, B. (1992), "Mick obtiene algo (las probabilidades están de su lado)", Proc. 33a IEEE Symp. Fundamentos de la informática (FOCS) , págs. 620–627, doi : 10.1109 / SFCS.1992.267789 , ISBN 978-0-8186-2900-6; Goerdt, A. (1996), "Un umbral de insatisfacción", Journal of Computer and System Sciences , 53 (3): 469–486, doi : 10.1006 / jcss.1996.0081.
41. MR Garey; DS Johnson; LJ Stockmeyer (1976), "Algunos problemas de gráficos NP-completos simplificados", Informática teórica , 1 (3): 237-267, doi : 10.1016 / 0304-3975 (76) 90059-1 , ISSN 0304-3975 ; ver págs. 4-6
42. Lewin, Michael; Livnar, Dror; Zwick, Uri (2002), "Técnicas de redondeo mejoradas para los problemas MAX 2-SAT y MAX DI-CUT", Actas de la 9ª Conferencia internacional de IPCO sobre programación de enteros y optimización combinatoria , Springer-Verlag, págs. 67–82, ISBN 978-3-540-43676-8
43. Austrin, Per (2007), "Balanced Max 2-sat podría no ser el más difícil", Actas del trigésimo noveno simposio anual de ACM sobre teoría de la computación (STOC '07) , Nueva York, NY, EE. UU.: ACM, págs. . 189–197, doi : 10.1145 / 1250790.1250818 , ISBN 978-1-59593-631-8.
44. Khot, Subhash ; Kindler, Guy; Mossel, Elchanan; O'Donnell, Ryan (2004), "Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?", FOCS '04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science , IEEE, págs. 146-154 , CiteSeerX 10.1.1.126.2295 , doi : 10.1109 / FOCS.2004.49 , ISBN  978-0-7695-2228-9
45. Håstad, Johan (2001), "Algunos resultados óptimos de inaproximabilidad", Journal of the ACM , 48 (4): 798–859, CiteSeerX 10.1.1.638.2808 , doi : 10.1145 / 502090.502098 .
46. Bansal, N .; Raman, V. (1999), "Límites superiores para MaxSat: mejorado aún más", en Aggarwal, A .; Pandu Rangan, C. (eds.), Proc. 10ª Conf. Algoritmos y Computación, ISAAC'99 , Lecture Notes in Computer Science, 1741 , Springer-Verlag, págs. 247–258; Gramm, Jens; Hirsch, Edward A .; Niedermeier, Rolf; Rossmanith, Peter (2003), "Límites superiores del peor caso para MAX-2-SAT con una aplicación a MAX-CUT", Discrete Applied Mathematics , 130 (2): 139-155, doi : 10.1016 / S0166-218X (02 ) 00402-X; Kojevnikov, Arist; Kulikov, Alexander S. (2006), "Un nuevo enfoque para probar los límites superiores para MAX-2-SAT", Proc. 17º ACM-SIAM Symp. Algoritmos discretos , págs. 11-17, doi : 10.1145 / 1109557.1109559 , ISBN 978-0-89871-605-4
47. Flum, Jörg; Grohe, Martin (2006), Teoría de la complejidad parametrizada , Springer, ISBN 978-3-540-29952-3
48. Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A .; Xia, Ge (2006), "Límites inferiores computacionales fuertes a través de la complejidad parametrizada", Journal of Computer and System Sciences , 72 (8): 1346-1367, doi : 10.1016 / j.jcss.2006.04.007
49. Hähnle, Reiner (2001), "Lógicas avanzadas de muchos valores", en Gabbay, Dov M .; Günthner, Franz (eds.), Handbook of Philosophical Logic , 2 , Springer, págs. 297–395, doi : 10.1007 / 978-94-017-0452-6_5 , ISBN 978-94-017-0452-6(ver en particular la p. 373 ); Hähnle, Reiner (2003), "Complejidad de lógicas multivaluadas", en Fitting, Melvin; Orlowska, Ewa (eds.), Más allá de dos: teoría y aplicaciones de la lógica de valores múltiples , Estudios en borrosidad y computación blanda, 114 , Springer, págs. 211-233, doi : 10.1007 / 978-3-7908-1769-0_9 , ISBN 978-3-7908-1541-2