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.^[1]​Por ejemplo, la siguiente fórmula está en forma normal conjuntiva, con siete variables, once cláusulas y 22 literales:

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

El problema de 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.^[1]​ 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.^[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 tres formas equivalentes:

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

Debido a esta equivalencia entre estos 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.^[3]​

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.^[4]​

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

Krom (1967) describió el siguiente procedimiento de decisión en tiempo polinómico para resolver instancias de 2-satisfactibilidad.^[2]​

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 ${\displaystyle (a\lor b)}$  y ${\displaystyle (\lnot b\lor \lnot c)}$  para obtener la cláusula ${\displaystyle (a\lor \lnot c)}$ , En términos de la forma implicativa de una fórmula 2-CNF, esta regla equivale a encontrar dos implicaciones ${\displaystyle \lnot a\Rightarrow b}$  y ${\displaystyle b\Rightarrow \lnot c}$  e inferir por transitividad una tercera implicación ${\displaystyle \lnot a\Rightarrow \lnot c}$ .^[2]​

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 ${\displaystyle (x\lor x)}$  y ${\displaystyle (\lnot x\lor \lnot x)}$  para cualquier variable ${\displaystyle 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 ${\displaystyle (x\lor x)}$  y ${\displaystyle (\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 ${\displaystyle (x\lor x)}$  o ${\displaystyle (\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 ${\displaystyle x}$  a verdadero si la fórmula contiene la cláusula ${\displaystyle (x\lor x)}$  y poniéndola en falso si la fórmula contiene la cláusula ${\displaystyle (\lnot x\lor \lnot x)}$ .^[2]​

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³), 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²) 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³). 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⁴). Incluso, Itai & Shamir (1976) citan un límite de tiempo más rápido deO(n²) 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.^[6]​

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.^[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 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.^[5]​

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.^[5]​

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.^[5]​

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.^[4]​

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^[7]​ y el algoritmo de componentes fuertemente conectados basado en rutas^[8]​realizan 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.^[4]​

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.^[9]​
• 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.^[4]​

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.^[4]​

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.^[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 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.^[11]​

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.^[10]​^[12]​ 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.^[13]​

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.^[14]​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.^[15]​

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.^[16]​

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. ^[17]​ 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³)para el problema de agrupación por suma de diámetros.^[18]​

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 ${\displaystyle i}$  dedica a la cohorte ${\displaystyle j}$  se describe mediante la entrada ${\displaystyle R_{ij}}$  de una matriz ${\displaystyle 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 ${\displaystyle v_{ij}}$  corresponde a una hora que el profesor ${\displaystyle i}$  debe dedicar a la cohorte ${\displaystyle 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.^[5]​

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).^[19]​

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,^[20]​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.^[21]​ 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.^[22]​ 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³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.^[23]​

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)^[5]​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.^[24]​

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.^[25]​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.^[26]​

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,^[27]​inferencia de relaciones comerciales entre subsistemas autónomos de Internet,^[28]​y reconstrucción de árboles evolutivos.^[29]​

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,^[30]​ 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.^[31]​ 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.^[31]​

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.^[32]​

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

#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,^[35]​ 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.^[36]​

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 ${\displaystyle O(1.2377^{n})}$ ^[37]​^[38]​^[39]​

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.^[40]​

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.^[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 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.^[42]​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 ${\displaystyle \min \left\{(3-\cos \theta )^{-1}(2+(2/\pi )\theta )\,:\,\pi /2\leq \theta \leq \pi \right\}=0.943...}$ .^[43]​

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.^[44]​ 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...^[45]​

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.^[46]​

En el problema de la 2-satisfiability ponderada (W2SAT), la entrada es un ${\displaystyle 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.^[47]​

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,^[47]​ 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.^[48]​

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.^[2]​^[4]​

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).^[49]​

1. ↑ ^{a b} 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 a 98, doi : 10.3233/978-1-58603-929-5-75 , ISBN 978-1-58603-929-5, Número de identificación del sujeto 31666330 .
2. ↑ ^{a b c d e f} Krom, Melven R. (1967), "El problema de decisión para una clase de fórmulas de primer orden en las que todas las disyunciones son binarias", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , 13 ( 1– 2): 15– 20, doi : 10.1002/malq.19670130104.
3. ↑ Russell, Stuart Jonathan; Norvig, Peter (2010), Inteligencia artificial: un enfoque moderno , serie Prentice Hall sobre inteligencia artificial, Prentice Hall, pág. 282, ISBN 978-0-13-604259-4.
4. ↑ ^{a b c d e f g} Aspvall, Bengt; Plass, Michael F.; Tarjan, Robert E. (1979), "Un algoritmo de tiempo lineal para probar la verdad de ciertas fórmulas booleanas cuantificadas" (PDF) , Information Processing Letters , 8 (3): 121– 123, doi : 10.1016/0020-0190(79)90002-4.
5. ↑ ^{a b c d e f g} Even, S .; Itai, A.; Shamir, A. (1976), "Sobre la complejidad de los problemas de flujo de múltiples productos y tablas de tiempos", SIAM Journal on Computing , 5 (4): 691– 703, doi : 10.1137/0205048.
6. ↑ Cook, Stephen A. (1971), "La complejidad de los procedimientos de demostración de teoremas", Proc. 3rd ACM Symp. Theory of Computing (STOC) , págs. 151– 158, doi : 10.1145/800157.805047 , S2CID 7573663  
7. ↑ Tarjan, Robert E. (1972), "Algoritmos de búsqueda en profundidad y de grafos lineales", SIAM Journal on Computing , 1 (2): 146– 160, doi : 10.1137/0201010 , S2CID 16467262 .
8. ↑ Publicado por primera vez por Cheriyan, J.; Mehlhorn, K. (1996), "Algoritmos para gráficos densos y redes 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.), Discrete Math. and its Applications: Handbook of Graph Theory , vol. 25, CRC Press, págs. 953– 984 .
9. ↑ Harrison, Paul, Ordenamiento topológico robusto y algoritmo de Tarjan en Python , consultado el 9 de febrero de 2011
10. ↑ ^{a b} Formann, M.; Wagner, F. (1991), "Un problema de empaquetamiento con aplicaciones a la rotulación de mapas", Proc. 7th ACM Symposium on Computational Geometry , págs. 281– 288, doi : 10.1145/109648.109680 , ISBN 978-0-89791-426-0, Número de identificación del sujeto 15740667 .
11. ↑ Poon, Chung Keung; Zhu, Binhai; Chin, Francis (1998), "Una solución de tiempo polinomial para etiquetar un mapa rectilíneo", Information Processing Letters , 65 (4): 201– 207, doi : 10.1016/S0020-0190(98)00002-7.
12. ↑ Wagner, Frank; Wolff, Alexander (1997), "Un algoritmo práctico de etiquetado de mapas", Computational Geometry: Theory and Applications , 7 ( 5–6 ): 387–404 , doi : 10.1016/S0925-7721(96)00007-7.
13. ↑ Doddi, Srinivas; Marathe, Madhav V.; Mirzaian, Andy; Moret, Bernard ME; Zhu, Binhai (1997), "Etiquetado de mapas y sus generalizaciones" , Proc. 8th ACM-SIAM Symp. Algoritmos discretos (SODA) , Soda '97, págs. 148– 157, ISBN 978-0-89871-390-9.
14. ↑ Efrat, Alon; Erten, Cesim; Kobourov, Stephen G. (2007), "Dibujo de arcos circulares de ubicación fija de grafos planos" (PDF) , Journal of Graph Algorithms and Applications , 11 (1): 145– 164, doi : 10.7155/jgaa.00140.
15. ↑ Raghavan, Raghunath; Cohoon, James; Sahni, Sartaj (1986), "Cableado de curva única", Journal of Algorithms , 7 (2): 232– 237, doi : 10.1016/0196-6774(86)90006-4.
16. ↑ Boros, Endre; Hammer, Peter Ladislaw ; Minoux, Michel; Rader, David J. Jr. (1999), "Cambio de celda óptimo para minimizar la densidad de canales en el diseño VLSI y la optimización pseudobooleana", Discrete Applied Mathematics , 90 ( 1–3 ): 69–88 , doi : 10.1016/S0166-218X(98)00114-0.
17. ↑ Hansen, P.; Jaumard, B. (1987), "Agrupamiento por suma mínima de diámetros", Journal of Classification , 4 (2): 215– 226, doi : 10.1007/BF01896987 , S2CID 120583429 .
18. ↑ Ramnath, Sarnath (2004), "La conectividad dinámica de dígrafos acelera la agrupación por suma mínima de diámetros", SIAM Journal on Discrete Mathematics , 18 (2): 272– 286, doi : 10.1137/S0895480102396099.
19. ↑ Miyashiro, Ryuhei; Matsui, Tomomi (2005), "Un algoritmo de tiempo polinomial para encontrar una asignación equitativa 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 .
20. ↑ Brualdi, RA (1980), "Matrices de ceros y unos con vectores de suma de filas y columnas fijos", Linear Algebra Appl. , 33 : 159– 231, doi : 10.1016/0024-3795(80)90105-6.
21. ↑ Woeginger, GJ (1996), La reconstrucción de poliominós a partir de sus proyecciones ortogonales , Informe técnico SFB-65, Graz, Austria: TU Graz.
22. ↑ Chrobak, Marek; Dürr, Christoph (1999), "Reconstrucción de poliominós hv-convexos a partir de proyecciones ortogonales", Information Processing Letters , 69 (6): 283– 289, arXiv : cs/9906021 , Bibcode : 1999cs........6021D , doi : 10.1016/S0020-0190(99)00025-3 , S2CID 6799509 .
23. ↑ Kuba, Attila; Balogh, Emese (2002), "Reconstrucción de conjuntos discretos 2D convexos en tiempo polinomial", Theoretical Computer Science , 283 (1): 223– 242, doi : 10.1016/S0304-3975(01)00080-9; Brunetti, Sara; Daurat, Alain (2003), "Un algoritmo que reconstruye conjuntos de redes convexas" (PDF) , Theoretical Computer Science , 304 ( 1– 3): 35– 57, doi : 10.1016/S0304-3975(03)00050-1 , S2CID 2803842 .
24. ↑ Batenburg, K. Joost; Kosters, Walter A. (2008), "Un marco de razonamiento para resolver nonogramas", Combinatorial Image Analysis, 12th International Workshop, IWCIA 2008, Buffalo, NY, EE. UU., 7-9 de abril de 2008, Actas , Lecture Notes in Computer Science, 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 .
25. ↑ Lewis, Harry R. (1978), "Renombrar un conjunto de cláusulas como un conjunto de Horn", Journal of the ACM , 25 (1): 134– 135, doi : 10.1145/322047.322059 , MR 0468315 , S2CID 3071958 .
26. ↑ Aspvall, Bengt (1980), "Reconocimiento de instancias NR(1) disfrazadas del problema de satisfacibilidad", Journal of Algorithms , 1 (1): 97– 103, doi : 10.1016/0196-6774(80)90007-3 , MR 0578079 .
27. ↑ Brandstädt, Andreas ; Hammer, Peter Ladislaw ; Le, Van Bang; Lozin, Vadim V. (2005), "Gráficos bisplit", Discrete Mathematics , 299 ( 1–3 ): 11–32 , doi : 10.1016/j.disc.2004.08.046.
28. ↑ Wang, Hao; Xie, Haiyong; Yang, Yang Richard; Silberschatz, Avi; Li, Li Erran; Liu, Yanbin (2005), "Selección de ruta de salida estable para ingeniería de tráfico entre dominios: modelo y análisis", 13.ª 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, Número de identificación del sujeto 4332805 .
29. ↑ Eskin, Eleazar; Halperin, Eran; Karp, Richard M. (2003), "Reconstrucción eficiente de la estructura del haplotipo a través de una filogenia perfecta", Journal of Bioinformatics and Computational Biology , 1 (1): 1– 20, doi : 10.1142/S0219720003000174 , PMID 15290779 .
30. ↑ Papadimitriou, Christos H. (1994), Computational Complexity , Addison-Wesley, págs. capítulo 4.2, ISBN 978-0-201-53082-7., Teoría. 16.3.
31. ↑ ^{a b} Cook, Stephen ; Kolokolova, Antonina (2004), "Una teoría de segundo orden para NL", 19.º Simposio anual 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, Número de identificación del sujeto 9936442 .
32. ↑ Bandelt, Hans-Jürgen; Chepoi, Victor (2008), "Teoría de grafos métricos y geometría: una encuesta", Encuestas sobre geometría discreta y computacional , Contemporary Mathematics, vol. 453, Providence, RI: American Mathematical Society, págs. 49– 86, doi : 10.1090/conm/453/08795 , ISBN 978-0-8218-4239-3, Sr. 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 American Mathematical Society, vol. 555.
33. ↑ Feder, Tomás (1994), "Flujo de red y 2-satisfacibilidad", Algorithmica , 11 (3): 291– 319, doi : 10.1007/BF01240738 , S2CID 34194118 .
34. ↑ Angelsmark, Ola; Thapper, Johan (2005), "Algoritmos para el problema de la distancia máxima de Hamming", Recent Advances in Constraints , Lecture Notes in Computer Science, vol. 3419, Springer-Verlag, págs. 128–141 , doi : 10.1007/11402763_10 , ISBN 978-3-540-25176-7.
35. ↑ Valiant, Leslie G. (1979), "La complejidad de los problemas de enumeración y confiabilidad", SIAM Journal on Computing , 8 (3): 410– 421, doi : 10.1137/0208032
36. ↑ Welsh, 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.
37. ↑ 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
38. ↑ Fürer, Martin; Kasiviswanathan, Shiva Prasad (2007), "Algoritmos para contar soluciones y coloraciones 2-SAT con aplicaciones", Algorithmic Aspects in Information and Management , 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.
39. ↑ Wahlström, Magnus (2008), "Un límite más estricto para contar soluciones de peso máximo para instancias 2sat", Taller internacional sobre computación parametrizada y exacta , 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
40. ↑ Bollobás, Béla ; Borgs, Christian; Chayes, Jennifer T .; Kim, Jeong Han; Wilson, David B. (2001), "La ventana de escala de la transición 2-SAT", Random Structures and Algorithms , 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 fundamentos de la informática , pp. 620– 627, doi : 10.1109/SFCS.1992.267789 , ISBN 978-0-8186-2900-6, Número de identificación del sujeto 5575389 ; Goerdt, A. (1996), "Un umbral para la insatisfacción", Journal of Computer and System Sciences , 53 (3): 469– 486, doi : 10.1006/jcss.1996.0081.
41. ↑ MR Garey; DS Johnson; LJ Stockmeyer (1976), "Algunos problemas simplificados de grafos NP-completos", Theoretical Computer Science , 1 (3): 237– 267, doi : 10.1016/0304-3975(76)90059-1 , ISSN 0304-3975 ; véanse las págs. 4–6
42. ↑ Lewin, Michael; Livnar, Dror; Zwick, Uri (2002), "Técnicas de redondeo mejoradas para los problemas MAX 2-SAT y MAX DI-CUT", Actas de la 9.ª Conferencia internacional IPCO sobre programación entera y optimización combinatoria , Springer-Verlag, págs. 67– 82, ISBN 978-3-540-43676-8
43. ↑ Austrin, Per (2007), "Balanced Max 2-sat Might Not Be the Hardest", Actas del Trigésimo Noveno Simposio Anual de la ACM sobre Teoría de la Computación (STOC '07) , Nueva York, NY, EE. UU.: ACM, págs. 189-197 , doi: 10.1145/1250790.1250818 ,]] ISBN 978-1-59593-631-8, Número de identificación del sujeto 2353625 .
44. ↑ Khot, Subhash ; Kindler, Guy; Mossel, Elchanan; O'Donnell, Ryan (2004), "¿Resultados de inaproximabilidad óptimos para MAX-CUT y otros CSP de 2 variables?", FOCS '04: Actas del 45.° Simposio anual IEEE sobre fundamentos de la informática , IEEE, págs. 146– 154, CiteSeerX 10.1.1.126.2295 , doi : 10.1109/FOCS.2004.49 , ISBN 978-0-7695-2228-9, S2CID2090495
45. ↑ Håstad, Johan (2001), "Algunos resultados de inaproximabilidad óptima", Journal of the ACM , 48 (4): 798– 859, CiteSeerX 10.1.1.638.2808 , doi : 10.1145/502090.502098 , S2CID 5120748 .
46. ↑ Bansal, N.; Raman, V. (1999), "Límites superiores para MaxSat: mejoras adicionales", en Aggarwal, A.; Pandu Rangan, C. (eds.), Proc. 10th Conf. Algorithms and Computation, ISAAC'99 , Lecture Notes in Computer Science, vol. 1741, Springer-Verlag, págs. 247– 258 ; Gramm, 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", Discrete Applied Mathematics , 130 (2): 139– 155, doi : 10.1016/S0166-218X(02)00402-X; Kojevnikov, Arist; Kulikov, Alexander S. (2006), "Un nuevo enfoque para demostrar límites superiores para MAX-2-SAT", Proc. 17th ACM-SIAM Symp. Discrete Algorithms , págs. 11– 17, doi : 10.1145/1109557.1109559 , ISBN 978-0-89871-605-4, Número de identificación del sujeto 10194873
47. ↑ ^{a b} 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
48. ↑ Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge (2006), "Límites inferiores computacionales fuertes a través de la complejidad parametrizada", Journal of Computer and System Sciences , 72 (8): 1346– 1367, doi : 10.1016/j.jcss.2006.04.007
49. ↑ Hähnle, Reiner (2001), "Lógicas avanzadas de múltiples valores", en Gabbay, Dov M.; Günthner, Franz (eds.), Handbook of Philosophical Logic , 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. 373 ); Hähnle, Reiner (2003), "Complejidad de lógicas multivaluadas", en Fitting, Melvin; Orlowska, Ewa (eds.), Más allá de dos: teoría y aplicaciones de lógica multivaluada , Studies in Fuzziness and Soft Computing, vol. 114, Springer, pp. 211– 233, doi : 10.1007/978-3-7908-1769-0_9 , ISBN 978-3-7908-1541-2