2-satisfacibilidad
En informática , 2-satisfacibilidad , 2-SAT o simplemente 2SAT es un problema computacional de asignar valores a las 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 de satisfacibilidad booleano general , que puede involucrar restricciones en más de dos variables, y de problemas de satisfacción de restricciones , que pueden permitir más de dos opciones para el valor de cada variable. Pero a diferencia de los problemas más generales, que son NP-completo , la 2-satisfacibilidad se puede resolver en tiempo polinomial .
Las instancias del problema de 2-satisfacibilidad se expresan típicamente como fórmulas booleanas de un tipo especial, llamadas forma normal conjuntiva (2-CNF) o fórmulas de Krom . Alternativamente, pueden expresarse como un tipo especial de grafo dirigido , el grafo de implicación , que expresa las variables de una instancia y sus negaciones como vértices en un grafo, y las restricciones sobre pares de variables como aristas dirigidas. Ambos tipos de entradas pueden resolverse en tiempo lineal , ya sea mediante un método basado en el retroceso o utilizando los componentes fuertemente conectados del gráfico de implicaciones. Resolución, un método para combinar pares de restricciones para hacer restricciones válidas adicionales, también conduce a una solución de tiempo polinomial. Los problemas de 2-satisfacibilidad proporcionan una de las dos principales subclases de las fórmulas conjuntivas de forma normal que se pueden resolver en tiempo polinomial; la otra de las dos subclases es la satisfacibilidad de Horn .
2-la satisfacibilidad se puede aplicar a problemas de geometría y visualización en los que una colección de objetos tiene cada uno dos ubicaciones potenciales y el objetivo es encontrar una ubicación para cada objeto que evite superposiciones con otros objetos. Otras aplicaciones incluyen la agrupación de datos para minimizar la suma de los diámetros de los grupos, la programación del aula y los deportes, y la recuperación de formas a partir de la información sobre sus secciones transversales.
En la teoría de la complejidad computacional , la satisfacibilidad 2 proporciona un ejemplo de un problema NL completo , uno que puede resolverse de manera no determinista utilizando una cantidad logarítmica de almacenamiento y que se encuentra entre los problemas más difíciles que se pueden resolver en este límite de recursos. Al conjunto de todas las soluciones para una instancia de satisfacibilidad 2 se le puede dar la estructura de un gráfico de mediana , pero contar estas soluciones es # P-completoy por lo tanto no se espera que tenga una solución de tiempo polinomial. Las instancias aleatorias experimentan una transición de fase brusca de instancias con solución a instancias sin solución a medida que la proporción de restricciones a variables aumenta más allá de 1, un fenómeno conjeturado pero no probado para formas más complicadas del problema de satisfacibilidad. Una variación computacionalmente difícil de 2-satisfacibilidad, encontrar una asignación de verdad que maximiza el número de restricciones satisfechas, tiene un algoritmo de aproximación cuya optimización depende de la conjetura de juegos únicos , y otra variación difícil, encontrar una asignación satisfactoria que minimiza el número de variables verdaderas, es un caso de prueba importante para la complejidad parametrizada .
Un problema de 2-satisfacibilidad puede describirse usando una expresión booleana con una forma restringida especial. Es una conjunción (una operación booleana y ) de cláusulas , donde cada cláusula es una disyunción (una operación booleana o ) 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:
