2-satisfacibilidad

En informática , 2-satisfacibilidad , 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 booleano de satisfacibilidad general , que puede implicar restricciones sobre 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-completos , la satisfacibilidad 2 se puede resolver en tiempo polinomial .

Los casos del problema de satisfacibilidad 2 generalmente se expresan como fórmulas booleanas de un tipo especial, llamado forma normal conjuntiva (2-CNF) o fórmulas de Krom . Alternativamente, pueden expresarse como un tipo especial de gráfico dirigido , el gráfico de implicación , que expresa las variables de una instancia y sus negaciones como vértices en un gráfico, y 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 retroceder o utilizando los componentes fuertemente conectados del gráfico de implicaciones. La 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 subclases principales de fórmulas de forma normal conjuntiva que se pueden resolver en tiempo polinomial; la otra de las dos subclases es la satisfacibilidad de Horn .

La 2-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 de aulas y deportes, y la recuperación de formas a partir de 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 se puede resolver de forma 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 recurso limitado. Al conjunto de todas las soluciones de una instancia de 2-satisfacibilidad se le puede dar la estructura de un gráfico de mediana , pero contar estas soluciones es #P-completo y, por lo tanto, no se espera que tenga una solución en tiempo polinomial. Las instancias aleatorias experimentan una transición de fase brusca de instancias solubles a insolubles a medida que la relación entre restricciones y 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, que encuentra 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 única del juego , y otra variación difícil, que encuentra 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

Un problema de 2-satisfacibilidad se puede describir utilizando una expresión booleana con una forma restringida especial. Es una conjunción (una operación booleana u ) de cláusulas , donde cada cláusula es una disyunción (una operación booleana u ) 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:

{\begin{alineado}&(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 consiste en 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 aquella que establece las siete variables en 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 configurar todas las variables para que la fórmula sea verdadera. Por lo tanto, la instancia de 2-satisfacibilidad representada por esta expresión es satisfacible.

Las fórmulas de esta forma se conocen como fórmulas de 2-CNF. El "2" de 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 les llama fórmulas de Krom, en honor al 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 2-satisfacibilidad. ^[2]

Cada cláusula de 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 cualquiera de tres formas equivalentes:

(x_{0}\lor \lnot x_{3})\;\equiv \;(\lnot x_{0}\Rightarrow \lnot x_{3})\;\equiv \;(x_{3} \Flecha derecha x_{0}).

o^[3]

Una tercera forma, más gráfica, de describir una instancia de 2-satisfacibilidad 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 sesgado-simétrico , 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 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]

Supongamos 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. Entonces las dos cláusulas pueden combinarse para producir una tercera cláusula, teniendo los otros dos literales en las dos cláusulas; esta tercera cláusula también debe cumplirse siempre que se cumplan las dos primeras cláusulas. Esto se llama resolución . Por ejemplo, podemos combinar las cláusulas y de esta manera producir la cláusula . En términos de la forma implicativa de una fórmula 2-CNF, esta regla equivale a encontrar dos implicaciones y e inferir por transitividad una tercera implicación . ^[2] $(a\lor b)$ $(\lnot b\lor \lnot c)$ $(a\lor \lnot c)$ $\lno es\Rightarrow b$ $b\Rightarrow \lno c$ $\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 ambas cláusulas y , para cualquier variable . Como demuestra, una fórmula de 2-CNF es satisfactoria si y sólo si es consistente. Porque, si una fórmula no es consistente, no es posible satisfacer ambas cláusulas y simultáneamente. Y, si es coherente, entonces la fórmula se puede ampliar agregando repetidamente una cláusula de la forma o a la vez, preservando la coherencia en cada paso, hasta que incluya dicha cláusula para cada variable. En cada uno de estos pasos de extensión, siempre se puede agregar una de estas dos cláusulas preservando la coherencia; de lo contrario, 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 verdadero si la fórmula contiene la cláusula y configurándola en falso si la fórmula contiene la cláusula . ^[2] $(x\lor x)$ $(\lnot x\lor \lnot x)$ $x$ $(x\lor x)$ $(\lnot x\lor \lnot x)$ $(x\lor x)$ $(\lnot x\lor \lnot x)$ $x$ $(x\lor x)$ $(\lnot x\lor \lnot x)$

A Krom le preocupaba principalmente la integridad de los sistemas de reglas de inferencia, más que la eficiencia de los algoritmos. Sin embargo, su método conduce a un tiempo polinomial limitado para resolver problemas de 2-satisfacibilidad. Al agrupar todas las cláusulas que usan la misma variable y aplicar la regla de inferencia a cada par de cláusulas, es posible encontrar todas las inferencias posibles a partir de una instancia determinada de 2-CNF y probar si es consistente. en tiempo total $O(n 3)$ , donde $n$ es el número de variables en la instancia. Esta fórmula surge de multiplicar el número de variables por el número $O(n 2)$ de pares de cláusulas que involucran una variable determinada, a las que se les puede aplicar la regla de inferencia. Por lo tanto, es posible determinar si una determinada instancia de 2-CNF es satisfactoria en el tiempo $O(n 3)$ . Debido a que encontrar una tarea satisfactoria usando $el$ método de Krom implica una secuencia de $O(n)$ comprobaciones de consistencia, tomaría tiempo $O(n4)$ . Incluso, Itai y Shamir (1976) citan un límite de tiempo más rápido de $O(n 2)$ para este algoritmo, basado en un ordenamiento más cuidadoso de sus operaciones. Sin embargo, incluso este límite de tiempo más pequeño fue mejorado enormemente por los algoritmos de tiempo lineal posteriores de Even, Itai y Shamir (1976) y Aspvall, Plass y Tarjan (1979).

En términos del gráfico de implicaciones de la instancia de 2-satisfacibilidad, la regla de inferencia de Krom puede interpretarse como la construcción del cierre transitivo del gráfico. Como observa Cook (1971), también puede verse como un ejemplo 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 polinómico se deriva del hecho de que cada paso de resolución aumenta el número de cláusulas en la instancia, que está limitado superiormente 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 a una variable se le puede dar 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, sólo se puede retroceder la elección más reciente. Todas las decisiones tomadas antes de la más reciente son permanentes. ^[5]

Inicialmente, no hay ningún punto de elección y todas las variables están desasignadas. 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 realizó desde esa elección, y revierte la decisión tomada en esa elección. Si no hay ningún punto de elección, o si el algoritmo ya ha retrocedido sobre el punto de elección más reciente, cancela la búsqueda e informa que la fórmula 2-CNF de entrada no es satisfactoria.
Si hay una cláusula en la que una de sus dos variables ya se ha establecido, y la cláusula aún podría volverse verdadera o falsa, entonces la otra variable se establece de manera que obligue a que la cláusula se vuelva verdadera.
En el caso restante, se garantiza que cada cláusula será 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 deduce que la elección fue correcta y que conduce a una tarea satisfactoria. Por lo tanto, el algoritmo encuentra correctamente una asignación satisfactoria o determina correctamente que la entrada es insatisfactoria. ^[5]

Incluso et al. no describió en detalle cómo implementar este algoritmo de manera eficiente. Sólo afirman que al "utilizar 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, realizando cada vez muchos pasos antes de retroceder, por lo que su complejidad general puede ser no lineal. Para evitar este problema, modifican el algoritmo de modo que, después de alcanzar cada punto de elección, comience a probar simultáneamente ambas asignaciones para la variable establecida en el punto de elección, empleando el mismo número de pasos en cada una de las dos asignaciones. Tan pronto como la prueba para una de estas dos asignaciones crea otro punto de elección, la otra prueba se detiene, de modo que en cualquier etapa del algoritmo solo quedan dos ramas del árbol de retroceso que aún se están probando. De esta forma, el tiempo total dedicado a 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 están asignados permanentemente. Como resultado, el algoritmo requiere un tiempo lineal total. ^[5]

Componentes fuertemente conectados

Aspvall, Plass y Tarjan (1979) encontraron un procedimiento de tiempo lineal más simple para resolver casos 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 de un grafo dirigido están fuertemente conectados entre sí si hay un camino dirigido de uno al 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. Existen varios algoritmos de tiempo lineal eficientes para encontrar los componentes fuertemente conectados de un gráfico, basados en la búsqueda en profundidad : el algoritmo de componentes fuertemente conectados de Tarjan ^[7] y el algoritmo de componentes fuertes basado en rutas ^[8] realizan cada uno una única búsqueda en profundidad. buscar. El algoritmo de Kosaraju realiza dos 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 al 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 puede satisfacerse, porque es imposible asignar a ambos literales el mismo valor. Como Aspvall et al. Como se demostró, esta es una condición necesaria y suficiente : una fórmula 2-CNF es satisfactoria si y sólo si no hay ninguna 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 de 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. Como también se demostró, 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 fuerte.
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 implicación, un gráfico más pequeño que tenga un vértice para cada componente fuertemente conectado y una arista del componente $i$ al componente $j$ siempre que el gráfico de implicación 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 implicación a partir del cual se formó, es sesgado-simétrico .
Ordenar topológicamente los vértices de la condensación. En la práctica, esto se puede lograr de manera eficiente como 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 del 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 a la simetría sesgada, cuando un literal se establece en verdadero, todos los literales a los que se puede llegar desde él 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 lo tanto, la asignación de verdad construida mediante 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. Como se muestra, también se puede utilizar un procedimiento similar que implica ordenar topológicamente los componentes fuertemente conectados del gráfico de implicaciones para evaluar fórmulas booleanas completamente cuantificadas en las que la fórmula que se cuantifica es una fórmula de 2-CNF. ^[4]

Aplicaciones

Colocación sin conflictos de objetos geométricos.

Varios algoritmos exactos y aproximados para el problema de colocación automática de etiquetas se basan en la 2-satisfacibilidad. Este problema se refiere a la colocación de etiquetas textuales en las características de un diagrama o mapa. Normalmente, el conjunto de posibles ubicaciones para cada etiqueta está muy limitado, no sólo 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 superponerse. entre sí, porque de lo contrario se volverían ilegibles. En general, encontrar una ubicación de etiqueta que obedezca estas restricciones es un problema NP-difícil . Sin embargo, si cada característica tiene solo dos ubicaciones posibles para su etiqueta (por ejemplo, extendiéndose hacia la izquierda y hacia la derecha de la característica), entonces 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 podrían 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 tiene solo muchas restricciones lineales, lo que lleva a algoritmos de tiempo casi lineales para encontrar una etiqueta. ^[10] Poon, Zhu y Chin (1998) describen un problema de etiquetado de mapas 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 una 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 la satisfacibilidad 2 como parte de un algoritmo de aproximación para 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 tenga una de sus esquinas en el punto que lo etiqueta. Para encontrar una etiqueta con un tamaño determinado, eliminan cuadrados que, si se duplicaran, se superpondrían a otro punto, y eliminan puntos que pueden etiquetarse de una manera que no es posible que se superpongan con la etiqueta de otro punto. Muestran que estas reglas de eliminación hacen que los puntos restantes tengan solo dos ubicaciones de etiquetas posibles por punto, lo que permite encontrar una ubicación de etiqueta válida (si existe) como solución a una instancia de 2-satisfacibilidad. Al buscar el tamaño de etiqueta más grande que conduzca 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. Es decir, la 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-satisfacibilidad para encontrar el tamaño de etiqueta más grande para el cual hay 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 para evitar cruces es un problema de 2-satisfacibilidad con una variable para cada borde y una restricción para cada par de ubicaciones que conducirían 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 el gráfico implícitamente . ^[14] En el diseño de circuitos integrados VLSI , si una colección de módulos debe conectarse mediante cables que cada uno pueda doblarse 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 puedan enrutarse en una sola capa del circuito, se puede resolver como una instancia de 2-satisfacibilidad. ^[15]

Boros et al. (1999) consideran otro problema de diseño de VLSI: la cuestión de si invertir o no 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 et al. Considere una versión simplificada del problema en el que los módulos ya se han colocado a lo largo de un único canal lineal, en el que los cables entre módulos deben enrutarse y existe un límite fijo en la densidad del canal (el número máximo de señales que debe pasar por cualquier sección transversal del canal). Observan que esta versión del problema puede resolverse como un caso de 2-satisfacibilidad, en el que las restricciones relacionan las orientaciones de pares de módulos que están directamente frente al 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 2-satisfacibilidad. ^[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 distancia más grande entre cualquier grupo. dos de sus puntos. Esto es preferible a minimizar el tamaño máximo del grupo, lo que puede llevar a que se asignen puntos muy similares a diferentes grupos. Si se conocen los diámetros objetivo de los dos grupos, se puede encontrar un grupo 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 grupo, 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 suma dada de diámetros sin conocer los diámetros individuales del grupo, 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 puede realizarse mediante una agrupación. Para encontrar la suma óptima de diámetros se puede realizar una búsqueda binaria en la que cada paso sea una prueba de viabilidad de este tipo. El mismo enfoque también funciona para encontrar agrupaciones que optimicen otras combinaciones además de las sumas de los diámetros de las 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 límite de tiempo 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 unos de otros, lo que lleva a un límite de tiempo total de $O (n 3)$ para el problema de agrupamiento de suma de diámetros. ^[18]

Planificación

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

Miyashiro y Matsui (2005) aplican la 2-satisfacibilidad a un problema de programación deportiva, en el que los emparejamientos de un torneo de todos contra todos ya han sido elegidos y los juegos deben asignarse a los estadios de los equipos. En este problema, es deseable alternar partidos en casa y fuera de casa en la medida de lo posible, evitando "descansos" en los que un equipo juega dos partidos seguidos en casa o dos partidos fuera de casa seguidos. Como máximo, dos equipos pueden evitar los descansos por completo, alternando partidos en casa y fuera; Ningún otro equipo puede tener el mismo calendario de local y visitante que estos dos, porque entonces no podría jugar contra el equipo con el que tenía el mismo calendario. Por lo tanto, un calendario óptimo tiene dos equipos sin descanso y un solo descanso para cada otro equipo. Una vez que se elige uno de los equipos inquebrantables, se puede plantear un problema de satisfacibilidad 2 en el que cada variable representa la asignación de local-fuera para un solo equipo en un solo juego, y las restricciones imponen las propiedades de que dos equipos cualesquiera tengan un juego consistente. asignación para sus juegos, que cada equipo tenga 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 tenga dos descansos. Por lo tanto, se puede comprobar 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 descanso. Una técnica similar también permite encontrar horarios en los que cada equipo tenga un único 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

La tomografía es el proceso de recuperar formas a partir de sus cortes transversales. En tomografía discreta , una versión simplificada del problema que se ha estudiado con frecuencia, la forma a recuperar es un poliominó (un subconjunto de los cuadrados en la red cuadrada bidimensional ), y las secciones transversales proporcionan información agregada sobre los conjuntos. de cuadrados en filas y columnas individuales de la red. Por ejemplo, en los populares rompecabezas de nonogramas , también conocidos como pintura por números o griddlers, el conjunto de cuadrados a determinar representa los píxeles oscuros en una imagen binaria , y la entrada dada al solucionador del rompecabezas le indica cuántos bloques consecutivos de píxeles oscuros a incluir en cada fila o columna de la imagen, y qué longitud 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: sólo 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 polinómico 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 identidad de 2 × 2 puede complementarse sin afectar la exactitud 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 las 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 y más fácil de resolver es que la forma es ortogonalmente convexa : tiene un único bloque contiguo de cuadrados en cada fila y columna. Mejorando varias soluciones anteriores, Chrobak y Dürr (1999) mostraron cómo reconstruir formas ortogonalmente convexas 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 satisfacibilidad 2 que pruebe si existe una forma consistente con estas conjeturas y con las sumas de filas y columnas dadas. Usan cuatro variables de satisfacibilidad 2 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 un tiempo $O(m 3 n)$ donde $m$ es la menor de las dos dimensiones de la forma de entrada y $n$ es la mayor de las dos dimensiones. Posteriormente, el mismo método se amplió a formas ortogonalmente convexas que podían conectarse sólo diagonalmente en lugar de requerir conectividad ortogonal. ^[23]

Como parte de un solucionador de acertijos de nonogramas completos, 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 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 en la misma fila o columna pueden estar conectados por una relación de implicación. También transforman el nonograma en un problema de tomografía digital reemplazando la secuencia de longitudes de bloques en cada fila y columna por su suma, y usan una formulación de flujo máximo para determinar si este problema de tomografía digital que combina todas las filas y columnas tiene algún cuadrado cuyo Se puede determinar el estado o pares de cuadrados que se pueden conectar mediante 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 utiliza un solucionador de 2 satisfacibilidad para encontrar cuadrados cuyo valor está fijado por el problema, después de lo cual el procedimiento es nuevamente repetido. Este procedimiento puede o no lograr encontrar una solución, pero se garantiza que se ejecutará en tiempo polinomial. Batenburg y Kosters informan que, aunque la mayoría de los acertijos periodísticos no necesitan toda su potencia, tanto este procedimiento como un procedimiento más potente pero más lento que combina este enfoque de 2 satisfacibilidad con el retroceso limitado de Even, Itai y Shamir (1976) ^[5] son significativamente más efectivos que la programación dinámica y las heurísticas de flujo sin satisfacibilidad 2 cuando se aplican a nonogramas generados aleatoriamente más difíciles. ^[24]

Satisfacibilidad del cuerno renombrable

Junto a la satisfacibilidad 2, la otra subclase importante de problemas de satisfacibilidad que se pueden resolver en tiempo polinómico 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, renombrada satisfacibilidad de Horn , que todavía se puede resolver en tiempo polinómico mediante una instancia auxiliar de 2-satisfacibilidad. Una fórmula es renombrable Horn cuando es posible ponerla en forma 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 variables de Horn renombrables correspondientes. Para producir una instancia de Horn, no deben aparecer positivamente en esa cláusula dos variables que aparezcan en la misma cláusula de la instancia de Horn renombrable; 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 múltiples 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

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

Complejidad y extensiones

NL-integridad

Es fácil de describir un algoritmo no determinista para determinar si una instancia de 2-satisfacibilidad no es satisfacible, usando sólo una cantidad logarítmica de memoria grabable: simplemente elija (de manera no determinista) una variable v y busque (de manera no determinista) una cadena de implicaciones que partan de v. a su negación y luego de regreso al v . Si se encuentra dicha 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 satisfactible de 2 satisfacibilidad es satisfacible.

La satisfacibilidad 2 es NL-completa , ^[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 un espacio logarítmico. La completitud aquí significa que una máquina de Turing determinista que utiliza sólo espacio logarítmico puede transformar cualquier otro problema en NL en un problema equivalente de 2-satisfacibilidad. De manera análoga a resultados similares para la clase de complejidad más conocida NP , esta transformación junto con el teorema de Immerman-Szelepcsényi permiten representar cualquier problema en NL como una fórmula lógica de segundo orden con un único predicado existencialmente cuantificado con cláusulas limitadas a una longitud de 2. Estas 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 cierre transitivo . ^[31]

El conjunto de todas las soluciones.

El conjunto de todas las soluciones a una instancia de 2-satisfacibilidad tiene la estructura de un gráfico de mediana , en el que una arista 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 las aristas 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 a un caso de 2-satisfacibilidad de esta manera. La mediana de tres soluciones cualesquiera se forma estableciendo cada variable al valor que tiene en la mayoría de las tres soluciones. Esta mediana siempre forma otra solución al caso. ^[32]

Feder (1994) describe un algoritmo para enumerar eficientemente 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 distancia máxima de Hamming entre sí. ^[34]

Contando el número de tareas satisfactorias

#2SAT es el problema de contar el número de asignaciones satisfactorias a una fórmula 2-CNF determinada. 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 totalmente polinomial para #2SAT a menos que NP = RP y esto se cumple incluso cuando la entrada está restringida a fórmulas 2-CNF monótonas, 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] $O(1,2377^{n})$

Instancias aleatorias de 2 satisfacibilidad

Se puede formar una instancia de 2-satisfactibilidad al azar, para un número dado n de variables y m de cláusulas, eligiendo cada cláusula uniformemente al azar del conjunto de todas las posibles cláusulas de dos variables. Cuando m es pequeño en relación con n , tal instancia probablemente será satisfactoria, pero valores más grandes de m tienen menores probabilidades de ser satisfactorias. Más precisamente, si m / n se fija como una constante α ≠ 1, la probabilidad de satisfacibilidad tiende a un límite cuando n tiende al infinito: si α < 1, el límite es uno, mientras que si α > 1, el límite es cero . Por 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 satisfacerse simultáneamente mediante una asignación. . Al igual que el problema de máxima satisfacibilidad más general , MAX-2-SAT es NP-duro . La prueba es por reducción del 3SAT . ^[41]

Formulando 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 semidefinida 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 MAX 2-SAT equilibrada es una instancia de MAX 2-SAT donde cada variable aparece positiva y negativamente con el mismo peso. Para este problema, Austrian ha mejorado la relación de aproximación a . ^[43] $\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, equilibrado o no, con una constante de aproximación mejor que 0,943... en tiempo polinómico. ^[44] Bajo el supuesto más débil de que P ≠ NP , solo se sabe que el problema es inaproximable 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]

Satisfabilidad ponderada 2

En el problema de satisfacibilidad 2 ponderado ( W2SAT ), la entrada es una instancia de 2SAT con variable y un número entero $k$ , y el problema es decidir si existe una asignación satisfactoria en la que exactamente $k$ de las variables sean verdaderas. ^[47] $n$

El problema W2SAT incluye como caso especial el problema de cobertura de vértices , de encontrar un conjunto de $k$ vértices que juntos toquen 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 un gráfico. Cada borde $uv$ del gráfico puede representarse mediante una cláusula 2SAT $u \lor v$ que solo puede satisfacerse incluyendo $u$ o $v$ entre las variables verdaderas de la solución. Entonces, 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 $k$ variables verdaderas si y solo si hay una cobertura de vértices con $k$ vértices. Por lo tanto, al igual que la cobertura de vértices, W2SAT es NP-completo .

Además, en 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 tome la forma $f (k) \cdot n O (1)$ . Aún más claramente, W2SAT no puede resolverse 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 polinomial para la satisfacibilidad de 2, Krom (1967) también formuló el problema de evaluar fórmulas booleanas completamente cuantificadas en las que la fórmula que se cuantifica es una fórmula de 2-CNF. El problema de 2-satisfacibilidad es el caso especial de este problema cuantificado de 2-CNF, 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 multivalor

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

Referencias

^ ab Prestwich, Steven (2009), "2. Codificaciones CNF", en Biere, Armin; Heule, Marijn ; van Maaren, Hans; Walsh, Toby (eds.), Manual de satisfacción , Fronteras en inteligencia artificial y aplicaciones, vol. 185, IOS Press, págs. 75–98, doi :10.3233/978-1-58603-929-5-75, ISBN 978-1-58603-929-5, S2CID 31666330.
^ abcdef 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.
^ Russell, Estuardo Jonathan; Norvig, Peter (2010), Inteligencia artificial: un enfoque moderno , serie de Prentice Hall sobre inteligencia artificial, Prentice Hall, p. 282, ISBN 978-0-13-604259-4.
^ abcdefg 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.
^ abcdefg Incluso, S .; Itaí, A.; Shamir, A. (1976), "Sobre la complejidad de los horarios y los problemas de flujo de múltiples productos", SIAM Journal on Computing , 5 (4): 691–703, doi :10.1137/0205048.
^ Cook, Stephen A. (1971), "La complejidad de los procedimientos de demostración de teoremas", Proc. 3er Simposio ACM. Teoría de la Computación (STOC) , págs. 151–158, doi : 10.1145/800157.805047 , S2CID 7573663.
^ Tarjan, Robert E. (1972), "Algoritmos de gráficos lineales y búsqueda en profundidad", SIAM Journal on Computing , 1 (2): 146–160, doi :10.1137/0201010, S2CID 16467262.
^ 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, S2CID 8930091. 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: manual de teoría de grafos , vol. 25, CRC Press, págs. 953–984.
^ Harrison, Paul, Clasificación topológica robusta y algoritmo de Tarjan en Python , consultado el 9 de febrero de 2011.
^ ab Formann, M.; Wagner, F. (1991), "Un problema de embalaje con aplicaciones al rotulado de mapas", Proc. Séptimo Simposio ACM sobre Geometría Computacional , págs. 281–288, doi :10.1145/109648.109680, ISBN 978-0-89791-426-0, S2CID 15740667.
^ 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.
^ Wagner, franco; 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.
^ Doddi, Srinivas; Marathe, Madhav V.; Mirzaian, Andy; Moret, Bernard ME; Zhu, Binhai (1997), "Etiquetado de mapas y sus generalizaciones", Proc. VIII Simposio ACM-SIAM. Algoritmos discretos (SODA), Soda '97, págs. 148-157, ISBN 978-0-89871-390-9.
^ Efrat, Alon; Erten, Cesim; Kobourov, Stephen G. (2007), "Dibujo de arco circular de ubicación fija de gráficos planos" (PDF) , Journal of Graph Algorithms and Applications , 11 (1): 145–164, doi :10.7155/jgaa.00140.
^ Raghavan, Raghunath; Cohoon, James; Sahni, Sartaj (1986), "Cableado de curva única", Journal of Algorithms , 7 (2): 232–237, doi :10.1016/0196-6774(86)90006-4.
^ Boros, Endre; Martillo, Peter Ladislaw ; Minoux, Michel; Rader, David J. Jr. (1999), "Inversión de celda óptima para minimizar la densidad de canales en el diseño VLSI y optimización pseudobooleana", Matemáticas Aplicadas Discretas , 90 (1–3): 69–88, doi :10.1016/S0166- 218X(98)00114-0.
^ Hansen, P.; Jaumard, B. (1987), "Agrupación de suma mínima de diámetros", Journal of Classification , 4 (2): 215–226, doi :10.1007/BF01896987, S2CID 120583429.
^ Ramnath, Sarnath (2004), "La conectividad dinámica de dígrafos acelera la agrupación mínima de sumas de diámetros", Revista SIAM de Matemáticas Discretas , 18 (2): 272–286, doi :10.1137/S0895480102396099.
^ Miyashiro, Ryuhei; Matsui, Tomomi (2005), "Un algoritmo de tiempo polinomial para encontrar una asignación equitativa entre casa y fuera", Operations Research Letters , 33 (3): 235–241, CiteSeerX 10.1.1.64.240 , doi :10.1016/j.orl .2004.06.004 .
^ Brualdi, RA (1980), "Matrices de ceros y unos con vectores de suma de filas y columnas fijos", Aplicación de álgebra lineal. , 33 : 159–231, doi : 10.1016/0024-3795(80)90105-6.
^ Woeginger, GJ (1996), La reconstrucción de poliominós a partir de sus proyecciones ortogonales , Informe técnico SFB-65, Graz, Austria: TU Graz.
^ Chrobak, Marek; Dürr, Christoph (1999), "Reconstrucción de poliominós hv-convexos a partir de proyecciones ortogonales", Cartas de procesamiento de información , 69 (6): 283–289, arXiv : cs/9906021 , Bibcode : 1999cs.......6021D, doi :10.1016/S0020-0190(99)00025-3, S2CID 6799509.
^ Kuba, Atila; Balogh, Emese (2002), "Reconstrucción de conjuntos discretos 2D convexos en tiempo polinomial", Ciencias de la Computación 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órica , 304 (1–3): 35–57, doi :10.1016/S0304-3975(03)00050-1, S2CID 2803842.
^ Batenburg, K. Joost; Kosters, Walter A. (2008), "Un marco de razonamiento para resolver nonogramas", Análisis combinatorio de imágenes, 12º taller internacional, IWCIA 2008, Buffalo, NY, EE. UU., 7 al 9 de abril de 2008, Actas , Apuntes de conferencias en informática, vol. 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, Bibcode :2009PatRe..42.1672B, CiteSeerX 10.1.1.177.76 , doi :10.1016/j. patcog.2008.12.003 .
^ Lewis, Harry R. (1978), "Cambiar el nombre de un conjunto de cláusulas a un conjunto de bocinas", Journal of the ACM , 25 (1): 134–135, doi : 10.1145/322047.322059 , MR 0468315, S2CID 3071958.
^ Aspvall, Bengt (1980), "Reconocimiento de instancias disfrazadas de NR (1) del problema de satisfacibilidad", Journal of Algorithms , 1 (1): 97–103, doi :10.1016/0196-6774(80)90007-3, SEÑOR 0578079.
^ Brandstädt, Andreas ; Martillo, Peter Ladislaw ; Le, Van Bang; Lozin, Vadim V. (2005), "Gráficos bisplit", Matemáticas discretas , 299 (1–3): 11–32, doi : 10.1016/j.disc.2004.08.046.
^ 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ª Conferencia Internacional IEEE sobre Protocolos de Red (ICNP'05) , págs. 16-29, CiteSeerX 10.1.1.106.7345 , doi : 10.1109/ICNP.2005.39, ISBN 978-0-7695-2437-5, S2CID 4332805.
^ Eskin, Eleazar; Halperin, Eran; Karp, Richard M. (2003), "Reconstrucción eficiente de la estructura del haplotipo mediante una filogenia perfecta", Journal of Bioinformatics and Computational Biology , 1 (1): 1–20, doi :10.1142/S0219720003000174, PMID 15290779.
^ Papadimitriou, Christos H. (1994), Complejidad computacional , Addison-Wesley, págs. capítulo 4.2, ISBN 978-0-201-53082-7., Thm. 16.3.
^ ab Cook, Stephen ; Kolokolova, Antonina (2004), "Una teoría de segundo orden para NL", 19º Simposio anual del IEEE sobre lógica en informática (LICS'04) , págs. 398–407, doi :10.1109/LICS.2004.1319634, ISBN 978-0-7695-2192-3, S2CID 9936442.
^ Bandelt, Hans-Jürgen; Chepoi, Victor (2008), "Teoría y geometría de grafos métricos: un estudio", Encuestas sobre geometría discreta y computacional , Matemáticas Contemporáneas, vol. 453, Providence, RI: Sociedad Matemática Estadounidense, págs. 49–86, doi :10.1090/conm/453/08795, ISBN 978-0-8218-4239-3, SEÑOR 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, S2CID 5419897. Feder, T. (1995), Redes estables y gráficos de productos , Memorias de la Sociedad Matemática Estadounidense, vol. 555.
^ Feder, Tomás (1994), "Flujo de red y 2-satisfacibilidad", Algorithmica , 11 (3): 291–319, doi :10.1007/BF01240738, S2CID 34194118.
^ Marca de ángeles, Ola; Thapper, Johan (2005), "Algoritmos para el problema de la distancia máxima de Hamming", Avances recientes en restricciones, Lecture Notes in Computer Science, vol. 3419, Springer-Verlag, págs. 128-141, doi :10.1007/11402763_10, ISBN 978-3-540-25176-7.
^ 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
^ 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 siguientes, Teorema 57.
^ Dahllöf, Vilhelm; Jonsson, Peter; Wahlström, Magnus (2005), "Modelos de conteo para fórmulas 2SAT y 3SAT", Ciencias de la Computación Teórica , 332 (1–3): 265–291, doi :10.1016/j.tcs.2004.10.037
^ Fürer, 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, vol. 4508, Springer-Verlag, págs. 47–57, CiteSeerX 10.1.1.634.4498 , doi :10.1007/978-3-540-72870-2_5, ISBN 978-3-540-72868-9.
^ Wahlström, Magnus (2008), "Un límite más estricto para contar soluciones de peso máximo para instancias de 2sat", Taller internacional sobre computación exacta y parametrizada , Lecture Notes in Computer Science, vol. 5018, págs. 202–213, CiteSeerX 10.1.1.129.9232 , doi :10.1007/978-3-540-79723-4_19, ISBN 978-3-540-79722-7
^ Bollobás, Béla ; Borgs, cristiano; Chayes, Jennifer T .; Kim, Jeong Han; Wilson, David B. (2001), "La ventana de escala de la transición 2-SAT", Algoritmos y estructuras aleatorias , 18 (3): 201–256, arXiv : math/9909031 , doi :10.1002/rsa.1006, S2CID 9954684; Chvátal, V .; Reed, B. (1992), "Mick consigue algo (las probabilidades están de su lado)", Actas., 33º Simposio anual sobre los fundamentos de la informática , págs. 620–627, doi :10.1109/SFCS.1992.267789, ISBN 978-0-8186-2900-6, S2CID 5575389; Goerdt, A. (1996), "Un umbral de insatisfacibilidad", Journal of Computer and System Sciences , 53 (3): 469–486, doi : 10.1006/jcss.1996.0081.
^ Señor Garey; DS Johnson; LJ Stockmeyer (1976), "Algunos problemas simplificados de gráficos NP completos", Ciencias de la Computación Teórica , 1 (3): 237–267, doi :10.1016/0304-3975(76)90059-1, ISSN 0304-3975; ver págs. 4–6
^ 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 novena conferencia internacional IPCO sobre programación entera y optimización combinatoria , Springer-Verlag, págs. 67–82, ISBN 978-3-540-43676-8
^ 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 informática (STOC '07) , Nueva York, NY, EE. UU.: ACM, págs. 189–197, dirección : 10.1145/1250790.1250818, ISBN. 978-1-59593-631-8, S2CID 2353625.
^ Khot, Subhash ; Kindler, chico; Mossel, Eljanán; O'Donnell, Ryan (2004), "¿Resultados óptimos de inaproximabilidad para MAX-CUT y otros CSP de 2 variables?", FOCS '04: Actas del 45º Simposio anual del IEEE sobre fundamentos de la informática , IEEE, págs. , CiteSeerX 10.1.1.126.2295 , doi :10.1109/FOCS.2004.49, ISBN 978-0-7695-2228-9, S2CID 2090495
^ Håstad, Johan (2001), "Algunos resultados óptimos de inaccesibilidad", Journal of the ACM , 48 (4): 798–859, CiteSeerX 10.1.1.638.2808 , doi :10.1145/502090.502098, S2CID 5120748 .
^ Bansal, N.; Raman, V. (1999), "Límites superiores de MaxSat: mejorado aún más", en Aggarwal, A.; Pandu Rangan, C. (eds.), Proc. Décima Conferencia. Algoritmos y Computación, ISAAC'99 , Apuntes de conferencias en Ciencias de la Computación, vol. 1741, Springer-Verlag, págs. 247-258; abuela, Jens; Hirsch, Edward A.; Niedermeier, Rolf ; Rossmanith, Peter (2003), "Límites superiores en el peor de los casos para MAX-2-SAT con una aplicación a MAX-CUT", Matemáticas aplicadas discretas , 130 (2): 139–155, doi :10.1016/S0166-218X(02 )00402-X; Kojevnikov, Arist; Kulikov, Alexander S. (2006), "Un nuevo enfoque para demostrar los límites superiores de MAX-2-SAT", Proc. XVII Simposio ACM-SIAM. Algoritmos discretos , págs. 11-17, doi :10.1145/1109557.1109559, ISBN 978-0-89871-605-4, S2CID 10194873
^ ab Flum, Jörg; Grohe, Martin (2006), Teoría de la complejidad parametrizada , Springer, págs. 69–70, doi :10.1007/3-540-29953-X, ISBN 978-3-540-29952-3
^ Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge (2006), "Fuertes límites computacionales inferiores mediante complejidad parametrizada", Journal of Computer and System Sciences , 72 (8): 1346–1367, doi : 10.1016/j.jcss.2006.04.007
^ Hähnle, Reiner (2001), "Lógicas avanzadas de muchos valores", en Gabbay, Dov M.; Günthner, Franz (eds.), Manual de lógica filosófica , vol. 2, Springer, págs. 297–395, doi :10.1007/978-94-017-0452-6_5, ISBN 978-94-017-0452-6(ver en particular pág. 373); Hähnle, Reiner (2003), "Complejidad de lógicas multivaluadas", en apropiado, Melvin; Orlowska, Ewa (eds.), Más allá de dos: teoría y aplicaciones de la lógica de valores múltiples , Estudios sobre borrosidad y computación blanda, vol. 114, Springer, págs. 211–233, doi :10.1007/978-3-7908-1769-0_9, ISBN 978-3-7908-1541-2