En la teoría de la complejidad computacional , el problema de máxima satisfacibilidad ( MAX-SAT ) es el problema de determinar el número máximo de cláusulas, de una fórmula booleana dada en forma normal conjuntiva , que puede hacerse verdadera mediante una asignación de valores de verdad a las variables de la formula. Es una generalización del problema de satisfacibilidad booleano , que pregunta si existe una asignación de verdad que hace que todas las cláusulas sean verdaderas.
no es satisfactorio: no importa qué valores de verdad se asignen a sus dos variables, al menos una de sus cuatro cláusulas será falsa. Sin embargo, es posible asignar valores de verdad de tal manera que tres de las cuatro cláusulas sean verdaderas; de hecho, cada asignación de la verdad hará esto. Por lo tanto, si esta fórmula se da como una instancia del problema MAX-SAT, la solución al problema es el número tres.
El problema MAX-SAT es NP-difícil , ya que su solución conduce fácilmente a la solución del problema de satisfacibilidad booleano , que es NP-completo .
También es difícil encontrar una solución aproximada del problema, que satisfaga una serie de cláusulas dentro de una relación de aproximación garantizada de la solución óptima. Más precisamente, el problema es APX -completo y, por lo tanto, no admite un esquema de aproximación de tiempo polinómico a menos que P = NP. [1] [2] [3]
De manera más general, se puede definir una versión ponderada de MAX-SAT de la siguiente manera: dada una fórmula de forma normal conjuntiva con pesos no negativos asignados a cada cláusula, encuentre valores de verdad para sus variables que maximicen el peso combinado de las cláusulas satisfechas. El problema MAX-SAT es una instancia de MAX-SAT ponderada donde todos los pesos son 1. [4] [5] [6]
Asignar aleatoriamente cada variable como verdadera con probabilidad 1/2 da una aproximación 2 esperada . Más precisamente, si cada cláusula tiene al menos k variables, entonces esto produce una aproximación (1 - 2 - k ). [7] Este algoritmo puede desaleatorizarse utilizando el método de probabilidades condicionales . [8]