# 2-satisfactibilidad

En informática, la 2-satisfactibilidad, 2-SAT o simplemente 2SAT es un problema computacional de asignación de valores a variables, cada una de las cuales tiene dos valores posibles, con el fin de satisfacer un sistema de restricciones sobre pares de variables. Es un caso especial del problema general de satisfacción booleana, que puede incluir restricciones sobre más de dos variables, y de los problemas de satisfacción de restricciones, que pueden permitir más de dos opciones para el valor de cada variable. Pero a diferencia de estos problemas más generales, que son NP-completos, la 2-satisfacción puede resolverse en tiempo polinómico.
Las instancias del problema de la 2-satisfactibilidad se expresan normalmente como fórmulas booleanas de un tipo especial, llamadas forma normal conjuntiva (2-CNF) o fórmulas de Krom. También 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 de 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 backtracking o utilizando los componentes fuertemente conectados del grafo de implicación. La resolución, un método para combinar pares de restricciones con el fin de obtener restricciones válidas adicionales, también conduce a una solución en tiempo polinómico. Los problemas de 2-satisfactibilidad proporcionan una de las dos subclases principales de las fórmulas de forma normal conjuntiva que pueden resolverse en tiempo polinómico; la otra de las dos subclases es la Horn-satisfactibilidad.
La 2-satisfiability puede aplicarse 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 colocación para cada objeto que evite solapamientos 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 clases 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 2-satisfactibilidad es un ejemplo de problema NL-completo, que puede resolverse de forma no determinista utilizando una cantidad logarítmica de almacenamiento y que se encuentra entre los problemas más difíciles de resolver con este límite de recursos. El conjunto de todas las soluciones a una instancia de 2 satisfacciones puede tener la estructura de un grafo mediano, pero contar estas soluciones es #P-completo y, por tanto, no se espera que tenga una solución en tiempo polinómico. Las instancias aleatorias experimentan una transición de fase brusca de instancias resolubles a instancias irresolubles a medida que la proporción entre restricciones y variables aumenta más allá de 1, un fenómeno conjeturado pero no demostrado para formas más complicadas del problema de la satisfacibilidad. Una variación computacionalmente difícil de la 2-satisfactibilidad, encontrar una asignación de verdad que maximice el número de restricciones satisfechas, tiene un algoritmo de aproximación cuya optimalidad depende de la conjetura de juegos únicos, y otra variación difícil, encontrar una asignación satisfactoria que minimice el número de variables verdaderas, es un importante caso de prueba para la complejidad parametrizada.

## Representaciones del problema

Un problema de 2 satisfacciones puede describirse mediante una expresión booleana con una forma restringida especial. Se trata de una conjunción (una operación booleana) de cláusulas, donde cada cláusula es una disyunción (una operación booleana) de dos variables o variables negadas. Las variables o sus negaciones que aparecen en esta fórmula se conocen como literales.Por ejemplo, la siguiente fórmula está en forma normal conjuntiva, con siete variables, once cláusulas y 22 literales:
${\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 la 2-satisfacción 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 cada una de las variables verdaderas o falsas, de modo que al menos un literal en cada cláusula se convierte en verdadero. Para la expresión mostrada arriba, una posible asignación satisfactoria es la que hace que las siete variables sean verdaderas. Cada cláusula tiene al menos una variable no negativa, por lo que esta asignación satisface todas las cláusulas. También hay otras 15 formas de asignar todas las variables para que la fórmula sea verdadera. Por lo tanto, la instancia de 2 satisfacciones representada por esta expresión es satisfactible.
Las fórmulas de esta forma se conocen como fórmulas 2-CNF. El "2" en este nombre significa el número de literales por cláusula, y "CNF" significa forma normal conjuntiva, un tipo de expresión booleana en forma de conjunción de disyunciones. También se llaman fórmulas Krom, por el trabajo del matemático de la UC Davis Melven R. Krom, cuyo artículo de 1967 fue uno de los primeros trabajos sobre el problema de la 2-satisfactibilidad.
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 tres formas equivalentes:
$(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 distintos tipos de operación, una instancia de 2-satisfactible también puede escribirse en forma normal implicativa, en la que sustituimos cada cláusula o de la forma normal conjuntiva por las dos implicaciones a las que es equivalente.
Una tercera forma, más gráfica, de describir una instancia de 2-satisfactible es como un grafo de implicación. Un grafo de implicación es un grafo dirigido en el que hay un vértice por variable o variable negada, y una arista 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 grafo de implicación debe ser un grafo 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.

## Algoritmos

Se conocen varios algoritmos para resolver el problema de la 2-satisfacción. Los más eficientes tardan un tiempo lineal.

### Resolución y cierre transitivo

Krom (1967) describió el siguiente procedimiento de decisión en tiempo polinómico para resolver instancias de 2-satisfactibilidad.
Supongamos que una instancia de 2 satisfacciones contiene dos cláusulas que utilizan la misma variable x, pero que x está negada en una cláusula y no en la otra. Entonces las dos cláusulas se pueden combinar para producir una tercera cláusula, que tiene los otros dos literales en las dos cláusulas; esta tercera cláusula también debe ser satisfecha siempre que las dos primeras cláusulas sean satisfechas. Esto se llama resolución. Por ejemplo, podemos combinar las cláusulas $(a\lor b)$ y $(\lnot b\lor \lnot c)$ para obtener la cláusula $(a\lor \lnot c)$, En términos de la forma implicativa de una fórmula 2-CNF, esta regla equivale a encontrar dos implicaciones $\lnot a\Rightarrow b$ y $b\Rightarrow \lnot c$ e inferir por transitividad una tercera implicación $\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 las dos cláusulas $(x\lor x)$ y $(\lnot x\lor \lnot x)$ para cualquier variable $x$. Como él demuestra, una fórmula 2-CNF es satisfacible si y sólo si es consistente. Porque, si una fórmula no es consistente, no es posible satisfacer las dos cláusulas $(x\lor x)$ y $(\lnot x\lor \lnot x)$simultáneamente. Y, si es coherente, entonces la fórmula puede ampliarse añadiendo repetidamente una cláusula de la forma $(x\lor x)$ o $(\lnot x\lor \lnot x)$cada vez, manteniendo la coherencia en cada paso, hasta que incluya una cláusula de este tipo para cada variable. En cada uno de estos pasos de ampliación, siempre se puede añadir una de estas dos cláusulas preservando la coherencia, ya que si no, la otra cláusula se podría generar 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 $x$ a verdadero si la fórmula contiene la cláusula $(x\lor x)$ y poniéndola en falso si la fórmula contiene la cláusula $(\lnot x\lor \lnot x)$.
Krom se ocupaba principalmente de la completitud de los sistemas de reglas de inferencia, más que de la eficacia de los algoritmos. Sin embargo, su método lleva a un límite de tiempo polinómico para resolver problemas de 2 satisfacciones. Agrupando todas las cláusulas que utilizan la misma variable y aplicando la regla de inferencia a cada par de cláusulas, es posible encontrar todas las inferencias posibles a partir de una instancia 2-CNF dada, y comprobar si es consistente, en un tiempo total O(n$^3$), donde n es el número de variables de la instancia. Esta fórmula resulta de multiplicar el número de variables por el número O(n$^2$) de pares de cláusulas que implican una variable dada, a los que se puede aplicar la regla de inferencia. Así, es posible determinar si una instancia 2-CNF dada es satisfacible en tiempo O(n$^3$). Dado que encontrar una asignación satisfactoria utilizando el método de Krom implica una secuencia de comprobaciones de consistencia O(n), llevaría un tiempo O(n$^4$). Incluso, Itai & Shamir (1976) citan un límite de tiempo más rápido deO(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 en gran medida por los algoritmos de tiempo lineal posteriores de Even, Itai y Shamir (1976) y Aspvall, Plass y Tarjan (1979).
En términos del grafo de implicación de la instancia de 2-satisfacciones, la regla de inferencia de Krom puede interpretarse como la construcción del cierre transitivo del grafo. Como observa Cook (1971), también puede verse como una instancia del algoritmo Davis-Putnam para resolver problemas de satisfacibilidad utilizando el principio de resolución. Su corrección se deduce 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 de la instancia, que está limitado superiormente por una función cuadrática del número de variables.

### Backtracking limitado

Even, Itai y Shamir (1976) describen una técnica que implica un backtracking 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 de aulas, pero también observan que se aplica a otros problemas, incluido 2-SAT.
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 una variable puede recibir cualquiera de los dos valores de verdad diferentes, y los pasos posteriores en el algoritmo puede hacer que se retroceda a uno de estos puntos de elección. Sin embargo, sólo se puede volver sobre la elección más reciente. Todas las elecciones anteriores a la más reciente son permanentes.
Inicialmente, no hay ningún punto de elección, y todas las variables están sin asignar. En cada paso, el algoritmo elige la variable cuyo valor establecer, como sigue:
* Si hay una cláusula cuyas dos variables ya están fijadas, de manera que se falsifica la cláusula, entonces el algoritmo retrocede a 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 ningún punto de elección, o si el algoritmo ya ha retrocedido hasta el punto de elección más reciente, entonces aborta la búsqueda e informa de que la fórmula 2-CNF de entrada es insatisfactible.
* Si hay una cláusula en la que una de las dos variables de la cláusula ya se ha establecido, y la cláusula todavía podría ser verdadera o falsa, entonces la otra variable se establece de una manera que obliga a la cláusula a ser verdadera.
* En el resto de los casos, se garantiza que cada cláusula será verdadera independientemente de cómo se asignen las variables restantes, o bien no se ha asignado todavía ninguna de sus dos variables. En este caso, el algoritmo crea un nuevo punto de elección y establece cualquiera de las variables sin asignar a un valor elegido arbitrariamente.
Intuitivamente, el algoritmo sigue todas las cadenas de inferencia después de hacer 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 conduce a una asignación satisfactoria. Por lo tanto, el algoritmo o bien encuentra correctamente una asignación satisfactoria o bien determina correctamente que la entrada es insatisfactible.
Even et al. no describen en detalle cómo implementar este algoritmo de forma eficiente. Sólo afirman que «utilizando estructuras de datos apropiadas para encontrar las implicaciones de cualquier decisión», cada paso del algoritmo (excepto el retroceso) puede realizarse 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 global puede ser no lineal. Para evitar este problema, modifican el algoritmo para que, después de alcanzar cada punto de elección, comience a probar simultáneamente las dos asignaciones para el conjunto de variables en el punto de elección, invirtiendo el mismo número de pasos en cada una de las dos asignaciones. Tan pronto como la prueba de una de estas dos asignaciones crearía otro punto de elección, la otra prueba se detiene, de modo que en cualquier etapa del algoritmo sólo hay dos ramas del árbol de retroceso que todavía se están probando. De este modo, 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 tarda un tiempo lineal en total.

### Componentes fuertemente conectados

Aspvall, Plass y Tarjan (1979) encontraron un procedimiento de tiempo lineal más sencillo para resolver instancias de 2 satisfacciones, basado en la noción de componentes fuertemente conectados de la teoría de grafos.
Se dice que dos vértices de un grafo dirigido están fuertemente conectados entre sí si existe un camino dirigido de uno a otro y viceversa. Se trata de una relación de equivalencia, y los vértices del grafo pueden dividirse en componentes fuertemente conectados, subconjuntos dentro de los cuales cada dos vértices están fuertemente conectados. Existen varios algoritmos eficientes en tiempo lineal para hallar las componentes fuertemente conectadas de un grafo, basados en la búsqueda por profundidad: El algoritmo de componentes fuertemente conectados de Tarjan y el algoritmo de componentes fuertemente conectados basado en rutasrealizan cada uno una única búsqueda en profundidad. El algoritmo de Kosaraju realiza dos búsquedas en profundidad, pero es muy sencillo.
En términos del grafo de implicación, 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-satisfacciones 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 demostraron Aspvall et al., se trata de una condición necesaria y suficiente: una fórmula 2-CNF es satisfacible si y sólo si no hay ninguna variable que pertenezca al mismo componente fuertemente conectado que su negación.
Esto conduce inmediatamente a un algoritmo de tiempo lineal para probar la satisfabilidad de las fórmulas 2-CNF: basta con realizar un análisis de conectividad fuerte en el grafo de implicación y comprobar que cada variable y su negación pertenecen a componentes diferentes. Sin embargo, como también demostraron Aspvall et al., también conduce a un algoritmo de tiempo lineal para encontrar una asignación satisfactoria, cuando existe. Su algoritmo realiza los siguientes pasos:
* Construir el grafo de implicación de la instancia y encontrar sus componentes fuertemente conectados utilizando cualquiera de los algoritmos conocidos de tiempo lineal para el análisis de conectividad fuerte.
* Comprobar si algún componente fuertemente conectado contiene tanto una variable como su negación. En caso afirmativo, informe de que la instancia no es satisfactoria y deténgase.
* Construir la condensación del grafo de implicación, un grafo más pequeño que tiene un vértice por cada componente fuertemente conectado, y una arista del componente i al componente j siempre que el grafo de implicación contenga una arista uv tal que u pertenezca al componente i y v pertenezca al componente j. La condensación es automáticamente un grafo acíclico dirigido y, como el grafo de implicación a partir del cual se formó, es asimétrico.
* Ordenar topológicamente los vértices de la condensación. En la práctica, esto puede lograrse eficientemente 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.
* Para cada componente en el orden topológico inverso, si sus variables no tienen ya asignaciones de verdad, establece todos los literales del componente como verdaderos. Esto también hace que todos los literales en el componente complementario sean falsos.
Debido a la ordenación topológica inversa y a la simetría oblicua, cuando se asigna el valor verdadero a un literal, todos los literales a los que se puede llegar desde él a través de una cadena de implicaciones ya se habrán asignado el valor verdadero. Simétricamente, cuando un literal x se establece como falso, todos los literales que conducen a él a través de una cadena de implicaciones ya se habrán establecido como falsos. Por lo 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.
Como muestran Aspvall et al., un procedimiento similar que implica ordenar topológicamente los componentes fuertemente conectados del grafo de implicación también se puede utilizar para evaluar fórmulas booleanas totalmente cuantificadas en las que la fórmula cuantificada es una fórmula 2-CNF.

## 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 2-satisfacción. Este problema consiste en colocar etiquetas textuales en las características de un diagrama o mapa. Normalmente, el conjunto de ubicaciones posibles para cada etiqueta está muy limitado, no sólo por el propio mapa (cada etiqueta debe estar cerca de la característica que etiqueta y no debe ocultar otras características), sino también entre sí: cada dos etiquetas deben evitar superponerse, ya que de lo contrario se volverían ilegibles. En general, encontrar una colocación de etiquetas que respete estas restricciones es un problema NP-difícil. Sin embargo, si cada característica sólo tiene dos ubicaciones posibles para su etiqueta (por ejemplo, a la izquierda y a la derecha de la característica), la colocación de la etiqueta puede resolverse en tiempo polinómico. En este caso, se puede crear una instancia de 2 satisfacciones que tenga una variable para cada etiqueta y una cláusula para cada par de etiquetas que puedan solaparse, evitando que se les asignen posiciones solapadas. Si todas las etiquetas son rectángulos congruentes, puede demostrarse que la instancia de 2-satisfacciones correspondiente sólo tiene un número lineal de restricciones, lo que conduce a algoritmos de tiempo casi lineal para encontrar un etiquetado. 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 uno de sus lados o puede estar centrado en el segmento. Representan estas tres posiciones utilizando dos variables binarias de tal forma que, de nuevo, comprobar la existencia de un etiquetado válido se convierte en un problema de 2 satisfacciones.
Formann y Wagner (1991) utilizan la 2-satisfiability 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 tiene una de sus esquinas en el punto que etiqueta. Para encontrar un etiquetado con un tamaño dado, eliminan los cuadrados que, si se duplican, se solaparían con otro punto, y eliminan los puntos que pueden etiquetarse de forma que no puedan solaparse con la etiqueta de otro punto. Demuestran que estas reglas de eliminación hacen que los puntos restantes sólo tengan dos posibles colocaciones de etiquetas por punto, lo que permite encontrar una colocación de etiqueta válida (si existe) como solución a una instancia de 2 satisfacciones. Buscando el mayor tamaño de etiqueta que conduzca a una instancia de 2 satisfacciones resoluble, encuentran una colocación de etiquetas válida cuyas etiquetas son al menos la mitad de grandes que la solución óptima. Es decir, el ratio de aproximación de su algoritmo es como máximo dos. De forma similar, si cada etiqueta es rectangular y debe colocarse de forma que el punto que etiquete esté en algún lugar de su borde inferior, el uso de la 2-satisfiability para encontrar el mayor tamaño de etiqueta para el que exista una solución en la que cada etiqueta tenga el punto en una esquina inferior conduce a un ratio de aproximación de como máximo dos.
Se han hecho aplicaciones similares de la 2-satisfacción para otros problemas geométricos de colocación. En el dibujo de grafos, si las ubicaciones de los vértices son fijas y cada arista debe dibujarse como un arco circular con una de dos ubicaciones posibles (por ejemplo, como un diagrama de arcos), entonces el problema de elegir qué arco usar para cada arista con el fin de evitar cruces es un problema de 2 satisfacibilidades con una variable para cada arista y una restricción para cada par de colocaciones que llevarí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 grafo de implicación, buscando el grafo implícitamente.En el diseño de circuitos integrados VLSI, si una colección de módulos debe estar conectada por cables que pueden doblarse cada uno como máximo una vez, entonces de nuevo hay dos rutas posibles para los cables, y el problema de elegir cuál de estas dos rutas utilizar, de tal manera que todos los cables puedan enrutarse en una sola capa del circuito, puede resolverse como una instancia de 2 satisfacciones.
Boros et al. (1999) consideran otro problema de diseño VLSI: la cuestión de si invertir o no cada módulo en un diseño de circuito. Esta inversión en 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 lo bien que el módulo encaja en el resto del diseño. Boros et al. consideran una versión simplificada del problema en la que los módulos ya se han colocado a lo largo de un único canal lineal, en el que deben enrutarse los cables entre módulos, y existe un límite fijo en la densidad del canal (el número máximo de señales que deben pasar por cualquier sección transversal del canal). Observan que esta versión del problema puede resolverse como una instancia de 2 satisfacciones, en la que las restricciones relacionan las orientaciones de los pares de módulos que están directamente uno frente al otro en el canal. Como consecuencia, la densidad óptima también puede calcularse eficientemente, realizando una búsqueda binaria en la que cada paso implica la solución de una instancia de 2 satisfacciones.

### Agrupación de datos

Una forma de agrupar un conjunto de puntos de datos en un espacio métrico en dos conglomerados es elegir los conglomerados de forma que se minimice la suma de los diámetros de los conglomerados, donde el diámetro de cualquier conglomerado es la mayor distancia entre dos de sus puntos. Esto es preferible a minimizar el tamaño máximo del conglomerado, que puede llevar a asignar puntos muy similares a conglomerados diferentes. Si se conocen los diámetros objetivo de los dos conglomerados, se puede encontrar un conglomerado que alcance esos objetivos resolviendo una instancia de 2 satisfacciones. La instancia tiene una variable por punto, que indica si ese punto pertenece al primer conglomerado o al segundo. Cuando dos puntos están demasiado alejados entre sí como para que ambos pertenezcan al mismo conglomerado, se añade una cláusula a la instancia que impide esta asignación.
El mismo método también puede utilizarse como subrutina cuando se desconocen los diámetros individuales de los conglomerados. Para comprobar si una suma dada de diámetros puede alcanzarse 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 satisfacciones y utilizando un algoritmo de 2 satisfacciones 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 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 los conglomerados, y que utilicen números de disimilitud arbitrarios (en lugar de distancias en un espacio métrico) para medir el tamaño de un conglomerado. El límite de tiempo para este algoritmo está dominado por el tiempo para resolver una secuencia de instancias de 2-satisfacciones 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 unas de otras, lo que lleva a un límite de tiempo total de O(n$^3$)para el problema de agrupación por suma de diámetros.

### Programación

Even, Itai & Shamir (1976) consideran un modelo de programación de aulas en el que un conjunto de n profesores deben ser programados para enseñar a cada una de las m cohortes de estudiantes. El número de horas semanales que el profesor $i$ dedica a la cohorte $j$ se describe mediante la entrada $R_{ij}$ de una matriz $R$ dada como entrada al problema, y cada profesor tiene también 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 se puede resolver como una instancia de 2-satisfiability cuando cada profesor sólo tiene dos horas disponibles. (Los profesores con una sola hora disponible pueden eliminarse fácilmente del problema). En este problema, cada variable $v_{ij}$ corresponde a una hora que el profesor $i$ debe dedicar a la cohorte $i$ la asignación a la variable especifica si esa hora es la primera o la segunda de las horas disponibles del profesor, y existe una cláusula de 2-satisfactibilidad que impide cualquier conflicto de cualquiera de los dos tipos: dos cohortes asignadas a un profesor al mismo tiempo entre sí, o una cohorte asignada a dos profesores al mismo tiempo.
Miyashiro y Matsui (2005) aplican la 2-satisfiability a un problema de programación deportiva, en el que los emparejamientos de un torneo de ida y vuelta ya se han elegido y los partidos deben asignarse a los estadios de los equipos. En este problema, es deseable alternar los partidos en casa y fuera en la medida de lo posible, evitando "descansos" en los que un equipo juegue dos partidos seguidos en casa o dos partidos seguidos fuera. Como máximo, dos equipos pueden evitar totalmente las interrupciones, alternando partidos en casa y fuera; ningún otro equipo puede tener el mismo calendario de partidos en casa y fuera que estos dos, porque entonces no podría jugar contra el equipo con el que tuviera el mismo calendario. Por lo tanto, un calendario óptimo tiene dos equipos sin descanso y un único descanso para todos los demás equipos. Una vez elegido uno de los equipos sin descanso, se puede plantear un problema de 2 satisfacciones en el que cada variable representa la asignación de un equipo como local y otro como visitante en un único partido, y las restricciones cumplen las propiedades de que dos equipos cualesquiera tienen una asignación coherente para sus partidos, que cada equipo tiene como máximo un descanso antes y como máximo un descanso después del partido con el equipo sin descanso, y que ningún equipo tiene dos descansos. Por lo tanto, para comprobar si un calendario admite una solución con el número óptimo de descansos se puede resolver un número lineal de problemas de 2 satisfacciones, uno para cada elección del equipo sin descanso. Una técnica similar también permite encontrar horarios en los que cada equipo tiene un único descanso, y maximizar en lugar de minimizar el número de descansos (para reducir el kilometraje total recorrido por los equipos).

### Tomografía discreta

La tomografía es el proceso de recuperación de formas a partir de sus secciones transversales. En la tomografía discreta, una versión simplificada del problema que se ha estudiado con frecuencia, la forma que hay que recuperar es un poliominó (un subconjunto de los cuadrados de la red cuadrada bidimensional), y las secciones transversales proporcionan información agregada sobre los conjuntos de cuadrados de las filas y columnas individuales de la red. Por ejemplo, en los populares rompecabezas de nonogramas, también conocidos como "pintar por números" o "cuadrícula", el conjunto de cuadrados que hay que determinar representa los píxeles oscuros de una imagen binaria, y la información que se da al que resuelve el rompecabezas le indica cuántos bloques consecutivos de píxeles oscuros debe 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 da 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 sólo 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 que tenga las sumas de filas y columnas dadas,la solución puede estar lejos de ser única: cualquier submatriz en forma de matriz identidad 2 × 2 puede complementarse sin afectar a la corrección de la solución. Por lo tanto, los investigadores han buscado restricciones sobre la forma a reconstruir que puedan utilizarse para restringir el espacio de soluciones. Por ejemplo, se podría suponer que la forma está conectada; sin embargo, comprobar si existe una solución conectada es NP-completo. Una versión aún más restringida y más fácil de resolver es que la forma sea ortogonalmente convexa: que tenga un único bloque contiguo de cuadrados en cada fila y columna. Chrobak y Dürr (1999), mejorando varias soluciones anteriores, mostraron cómo reconstruir formas ortogonalmente convexas conectadas de forma eficiente, utilizando 2-SAT. La idea de su solución es adivinar los índices de las filas que contienen las casillas más a la izquierda y más a la derecha de la forma que se va a reconstruir y, a continuación, plantear un problema de 2-satisfacción que compruebe si existe una forma coherente con estas conjeturas y con las sumas de filas y columnas dadas. Utilizan cuatro variables de 2 satisfacciones para cada cuadrado que podría formar parte de la forma dada, una para indicar si pertenece a cada una de las cuatro posibles "regiones de esquina" de la forma, y utilizan restricciones que obligan a estas regiones a ser disjuntas, a tener las formas deseadas, a formar una forma global con filas y columnas contiguas, y a tener las sumas de filas y columnas deseadas. Su algoritmo tarda 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. El mismo método se extendió posteriormente a formas ortogonalmente convexas que podrían estar conectadas sólo diagonalmente en lugar de requerir conectividad ortogonal.
Batenburg y Kosters (2008, 2009), que forman parte de un solucionador de rompecabezas de nonogramas completos, utilizaron la 2-satisfiability para combinar la información obtenida de varias otras heurísticas. Dada una solución parcial del 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 que cualquiera de sus casillas sea blanca o negra, y si dos casillas de la misma fila o columna pueden conectarse mediante una relación de implicación. También transforman el nonograma en un problema de tomografía digital sustituyendo la secuencia de longitudes de bloque en cada fila y columna por su suma, y utilizan una formulación de flujo máximo para determinar si este problema de tomografía digital que combina todas las filas y columnas tiene alguna casilla cuyo estado pueda determinarse o pares de casillas que puedan conectarse mediante una relación de implicación. Si cualquiera 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 consiguen fijar ningún cuadrado, las implicaciones encontradas por ambas se combinan en un problema de 2 satisfacciones y se utiliza un solucionador de 2 satisfacciones para encontrar los cuadrados cuyo valor fija el problema, tras lo cual se repite de nuevo el procedimiento. Este procedimiento puede tener éxito o no a la hora de encontrar una solución, pero se garantiza que se ejecuta en tiempo polinómico. Batenburg y Kosters informan de que, aunque la mayoría de los rompecabezas de periódicos no necesitan toda su potencia, tanto este procedimiento como un procedimiento más potente pero más lento que combina este enfoque de 2-satisfactibilidad con el backtracking limitado de Even, Itai y Shamir (1976)son significativamente más eficaces que la programación dinámica y la heurística de flujo sin 2-satisfactibilidad cuando se aplican a nonogramas generados aleatoriamente más difíciles.

### Satisfactibilidad renombrable de Horn

Junto a la 2-satisfactibilidad, la otra subclase principal de problemas de satisfactibilidad que puede resolverse en tiempo polinómico es la Horn-satisfactibilidad. En esta clase de problemas, la entrada es una fórmula en forma normal conjuntiva. Puede tener un número arbitrario de literales por cláusula, pero como máximo un literal positivo. Lewis (1978) encontró una generalización de esta clase, la satisfabilidad renombrable de Horn, que aún puede resolverse en tiempo polinómico mediante una instancia auxiliar de 2 satisfacibilidades. Una fórmula es renombrable Horn cuando es posible ponerla en forma Horn sustituyendo algunas variables por sus negaciones. Para ello, Lewis crea una instancia de 2-satisfactibilidad con una variable por cada variable de la instancia de Horn renombrable, donde las variables de 2-satisfactibilidad indican si hay que negar o no las correspondientes variables de Horn renombrables. Para producir una instancia de Horn, ninguna de las dos variables que aparecen en la misma cláusula de la instancia de Horn renombrable debe aparecer positivamente en esa cláusula; esta restricción sobre un par de variables es una restricción de 2-satisfactibilidad. Al encontrar una asignación satisfactoria a la instancia de 2-satisfactibilidad resultante, Lewis muestra cómo convertir cualquier instancia de Horn renombrable en una instancia de Horn en tiempo polinómico.Al dividir cláusulas largas en múltiples cláusulas más pequeñas y aplicar un algoritmo de 2-satisfactibilidad en tiempo lineal, es posible reducir esto a tiempo lineal.

### Otras aplicaciones

La 2-satisfactibilidad también se ha aplicado a problemas de reconocimiento de grafos no dirigidos que pueden dividirse en un conjunto independiente y un pequeño número de subgrafos bipartitos completos,inferencia de relaciones comerciales entre subsistemas autónomos de Internet,y reconstrucción de árboles evolutivos.

## Complejidad y ampliaciones
### NL-completitud

Es fácil describir un algoritmo no determinista para determinar si un caso de 2 satisfacibilidades no es satisfacible, utilizando sólo una cantidad logarítmica de memoria escribible: basta con elegir (de forma no determinista) una variable v y buscar (de forma no determinista) una cadena de implicaciones que lleve de v a su negación y luego de vuelta a v. Si se encuentra tal cadena, el caso no puede ser satisfacible. Por el teorema de Immerman-Szelepcsényi, también es posible verificar en el espacio logarítmico no determinista que una instancia de 2-satisfactible es satisfactible.
La 2-satisfactibilidad es NL-completa, lo que significa que es uno de los problemas "más difíciles" o "más expresivos" de la clase de complejidad NL de problemas resolubles de forma no determinista en el espacio logarítmico. Completitud significa aquí que una máquina de Turing determinista que utilice sólo espacio logarítmico puede transformar cualquier otro problema de NL en un problema de 2 satisfacciones equivalente. De forma 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, permite representar cualquier problema en NL como una fórmula lógica de segundo orden con un único predicado cuantificado existencialmente con cláusulas limitadas a longitud 2. Tales fórmulas se conocen como SO-Krom. De forma similar, la forma normal implicativa puede expresarse en lógica de primer orden con la adición de un operador de cierre transitivo.

### El conjunto de todas las soluciones

El conjunto de todas las soluciones de una instancia de 2 satisfacciones tiene la estructura de un grafo mediano, en el que una arista corresponde a la operación de voltear los valores de un conjunto de variables que están obligadas a ser iguales o desiguales entre sí. En concreto, siguiendo las aristas de esta forma se puede ir de cualquier solución a cualquier otra solución. A la inversa, cualquier grafo mediano puede representarse como el conjunto de soluciones a una instancia de 2 satisfacciones. La mediana de tres soluciones cualesquiera se forma poniendo cada variable en el valor que tiene en la mayoría de las tres soluciones. Esta mediana siempre forma otra solución de la instancia.
Feder (1994) describe un algoritmo para listar eficientemente todas las soluciones a una instancia dada de 2-satisfacciones, y para resolver varios problemas relacionados. También existen algoritmos para encontrar dos asignaciones satisfactorias que tengan la máxima distancia Hamming entre sí.

### Contar el número de asignaciones satisfactorias

#2SAT es el problema de contar el número de asignaciones que satisfacen una fórmula 2-CNF dada. Este problema de recuento es #P-completo, lo que implica que no es resoluble en tiempo polinómico a menos que P = NP. Además, no existe ningún esquema de aproximación aleatoria completamente polinómico para #2SAT a menos que NP = RP y esto es así incluso cuando la entrada se restringe 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.
El algoritmo más rápido conocido para calcular el número exacto de asignaciones satisfactorias de una fórmula 2SAT se ejecuta en tiempo $O(1.2377^{n})$

### Casos aleatorios de 2 satisfacciones

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 cláusulas posibles de dos variables. Cuando m es pequeño en relación con n, es probable que dicha instancia sea satisfactible, pero valores mayores de m tienen menores probabilidades de serlo. Más concretamente, si m/n se fija como una constante α ≠ 1, la probabilidad de satisfacción tiende a un límite a medida que n se hace infinito: si α < 1, el límite es uno, mientras que si α > 1, el límite es cero. Así, el problema exhibe una transición de fase en α = 1.

### Máxima-2-satisfactible

En el problema de máxima-2-satisfacción (MAX-2-SAT), la entrada es una fórmula en forma normal conjuntiva con dos literales por cláusula, y la tarea consiste en determinar el número máximo de cláusulas que pueden ser satisfechas simultáneamente por una asignación. Al igual que el problema más general de máxima satisfabilidad, MAX-2-SAT es NP-difícil. La prueba se obtiene por reducción a partir de 3SAT.
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 grafo relacionado con el grafo de implicación, y aplicando métodos de programación semidefinida a este problema de corte, es posible encontrar en tiempo polinomial una solución aproximada que satisface al menos 0. 940... veces el número óptimo de cláusulas.Una instancia MAX 2-SAT equilibrada es una instancia de MAX 2-SAT en la que cada variable aparece positiva y negativamente con igual peso. Para este problema, Austrin ha mejorado la relación de aproximación a $\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 polinomial. Bajo el supuesto más débil de que P ≠ NP, sólo se sabe que el problema es inaproximable dentro de una constante mejor que 21/22 = 0,95454...
Varios autores también han explorado límites exponenciales de tiempo en el peor de los casos para la solución exacta de instancias MAX-2-SAT.

### 2-satisfacción ponderada

En el problema de la 2-satisfiability ponderada (W2SAT), la entrada es un $n$ 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 son verdaderas.
El problema W2SAT incluye como caso especial el problema de cobertura de vértices, que consiste en encontrar un conjunto de k vértices que juntos toquen todas las aristas de un grafo 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 grafo. Cada arista uv del grafo puede representarse mediante una cláusula 2SAT uv que sólo puede satisfacerse incluyendo u ∨ 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 existe una asignación satisfactoria con k variables verdaderas si y sólo si existe 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, lo que implica que W2SAT no es tractable con parámetros fijos a menos que esto se cumpla para todos los problemas en W[1]. Es decir, es improbable que exista un algoritmo para W2SAT cuyo tiempo de ejecución tenga la formaf(k)·n$^{O(1)}$. Más aún, W2SAT no puede resolverse en tiempon$^{o(k)}$ a menos que falle la hipótesis del tiempo exponencial.

### Fórmulas booleanas cuantificadas

Además de encontrar el primer algoritmo de tiempo polinómico para la 2-satisfactibilidad, Krom (1967) también formuló el problema de evaluar fórmulas booleanas totalmente cuantificadas en las que la fórmula cuantificada es una fórmula 2-CNF. El problema de la 2-satisfactibilidad 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 puede resolverse en tiempo lineal, mediante una extensión de su técnica de componentes fuertemente conectados y ordenación topológica.

### Lógicas multivaluadas

El problema de la 2-satisfacción también puede plantearse para lógicas proposicionales multivaluadas. Los algoritmos no suelen ser lineales, y para algunas lógicas el problema es incluso NP-completo. Véanse los estudios de Hähnle (2001, 2003).