MAX-3SAT es un problema en el subcampo de complejidad computacional de la informática . Generaliza el problema de satisfacibilidad booleano (SAT) que es un problema de decisión considerado en la teoría de la complejidad . Se define como:
Dada una fórmula de 3-CNF Φ (es decir, con un máximo de 3 variables por cláusula), encuentre una asignación que satisfaga la mayor cantidad de cláusulas.
MAX-3SAT es un problema completo canónico para la clase de complejidad MAXSNP (se muestra completo en Papadimitriou pág. 314).
Aproximabilidad
La versión de decisión de MAX-3SAT es NP-complete . Por lo tanto, una solución de tiempo polinomial solo se puede lograr si P = NP . Sin embargo, se puede lograr una aproximación dentro de un factor de 2 con este algoritmo simple:
- Muestra la solución en la que se satisfacen la mayoría de las cláusulas, cuando todas las variables = VERDADERO o todas las variables = FALSO.
- Cada cláusula se satisface con una de las dos soluciones, por lo tanto, una solución satisface al menos la mitad de las cláusulas.
El algoritmo de Karloff-Zwick se ejecuta en tiempo polinomial y satisface ≥ 7/8 de las cláusulas.
Teorema 1 (inaproximación)
El teorema de PCP implica que existe un ε > 0 tal que (1- ε ) -aproximación de MAX-3SAT es NP-duro .
Prueba:
Cualquier -NP completa problemapor el teorema de PCP . Para x ∈ L , se construye una fórmula 3-CNF Ψ x de modo que
- x ∈ L ⇒ Ψ x es satisfactoria
- x ∉ L ⇒ no más de (1- ε ) m cláusulas de Ψ x son satisfactorias.
El Verificador V lee todos los bits necesarios a la vez, es decir, realiza consultas no adaptables. Esto es válido porque el número de consultas permanece constante.
- Sea q el número de consultas.
- Enumerando todas las cadenas aleatorias R i ∈ V , obtenemos cadenas poli ( x ) ya que la longitud de cada cadena.
- Para cada R i
- V elige q posiciones i 1 , ..., i q y una función booleana f R : {0,1} q -> {0,1} y acepta si y solo si f R (π (i 1 , ... , yo q )). Aquí π se refiere a la prueba obtenida del Oracle.
A continuación, intentamos encontrar una fórmula booleana para simular esto. Introducimos variables booleanas x 1 , ..., x l , donde l es la longitud de la demostración. Para demostrar que el Verificador se ejecuta en tiempo polinomial probabilístico , necesitamos una correspondencia entre el número de cláusulas satisfactorias y la probabilidad que acepta el Verificador.
- Para cada R , agregue cláusulas que representen f R ( x i1 , ..., x iq ) usando 2 q cláusulas SAT . Las cláusulas de longitud q se convierten en longitud 3 agregando nuevas variables (auxiliares), por ejemplo, x 2 ∨ x 10 ∨ x 11 ∨ x 12 = ( x 2 ∨ x 10 ∨ y R ) ∧ ( y R ∨ x 11 ∨ x 12 ) . Esto requiere un máximo de q 2 q 3 cláusulas SAT .
- Si z ∈ L entonces
- hay una prueba π tal que V π ( z ) acepta para cada R i .
- Todas las cláusulas se cumplen si x i = π ( i ) y las variables auxiliares se agregan correctamente.
- Si ingresa z ∉ L entonces
- Para cada asignación ax 1 , ..., x l y y R 's, la prueba correspondiente π ( i ) = x i hace que el Verificador rechace la mitad de todos los R ∈ {0,1} r (| z | ) .
- Para cada R , falla una cláusula que representa f R.
- Por lo tanto una fracción de cláusulas falla.
- Para cada asignación ax 1 , ..., x l y y R 's, la prueba correspondiente π ( i ) = x i hace que el Verificador rechace la mitad de todos los R ∈ {0,1} r (| z | ) .
Se puede concluir que si esto se cumple para cada problema NP-completo , entonces el teorema de PCP debe ser cierto.
Teorema 2
Håstad [1] demuestra un resultado más ajustado que el Teorema 1, es decir, el valor más conocido para ε.
Construye un verificador PCP para 3-SAT que lee solo 3 bits de la prueba.
Para cada ε > 0, hay un verificador PCP M para 3-SAT que lee una cadena aleatoria r de longitudy calcula las posiciones de la consulta i r , j r , k r en la prueba π y un bit b r . Acepta si y solo si
- π ( i r ) ⊕ π ( j r ) ⊕ π ( k r ) = b r .
El Verificador tiene integridad (1-ε) y solidez 1/2 + ε (consulte PCP (complejidad) ). El Verificador satisface
Si la primera de estas dos ecuaciones se equiparara a "= 1" como de costumbre, se podría encontrar una prueba π resolviendo un sistema de ecuaciones lineales (ver MAX-3LIN-EQN ) que implica P = NP .
- Si z ∈ L , se satisface una fracción ≥ (1- ε ) de cláusulas.
- Si z ∉ L , entonces para una fracción (1 / 2- ε ) de R , las cláusulas de 1/4 se contradicen.
Esto es suficiente para demostrar la dureza de la relación de aproximación.
Problemas relacionados
MAX-3SAT (B) es el caso especial restringido de MAX-3SAT donde cada variable ocurre en la mayoría de las cláusulas B. Antes de que se probara el teorema de PCP , Papadimitriou y Yannakakis [2] demostraron que para alguna constante B fija , este problema es MAX SNP-hard. En consecuencia, con el teorema de PCP, también es APX-hard. Esto es útil porque MAX-3SAT (B) a menudo se puede usar para obtener una reducción que conserva PTAS de una manera que MAX-3SAT no puede. Las pruebas de valores explícitos de B incluyen: todo B ≥ 13 , [3] [4] y todo B ≥ 3 [5] (que es lo mejor posible).
Además, aunque el problema de decisión 2SAT se puede resolver en tiempo polinomial, MAX-2SAT (3) también es APX-hard. [5]
La mejor relación de aproximación posible para MAX-3SAT (B), en función de B, es al menos y como mucho , [6] a menos que NP = RP . Se conocen algunos límites explícitos sobre las constantes de aproximabilidad para ciertos valores de B. [7] [8] [9] Berman, Karpinski y Scott demostraron que para las instancias "críticas" de MAX-3SAT en las que cada literal aparece exactamente dos veces, y cada cláusula es exactamente de tamaño 3, el problema es difícil de aproximación para algunos factor constante. [10]
MAX-EkSAT es una versión parametrizada de MAX-3SAT donde cada cláusula tiene exactamente literales, para k ≥ 3. Se puede aproximar de manera eficiente con una relación de aproximaciónutilizando ideas de la teoría de la codificación .
Se ha demostrado que las instancias aleatorias de MAX-3SAT se pueden aproximar dentro del factor. [11]
Referencias
- ^ Håstad, Johan (2001). "Algunos resultados óptimos de inaproximación". Revista de la ACM . 48 (4): 798–859. CiteSeerX 10.1.1.638.2808 . doi : 10.1145 / 502090.502098 .
- ^ Christos Papadimitriou y Mihalis Yannakakis, Clases de optimización, aproximación y complejidad, Actas del vigésimo simposio anual de ACM sobre teoría de la computación, p.229-234, 02-04 de mayo de 1988.
- ^ Rudich et al., "Teoría de la complejidad computacional", IAS / Park City Mathematics Series, 2004 página 108 ISBN 0-8218-2872-X
- ^ Sanjeev Arora, " Comprobación probabilística de pruebas y dureza de problemas de aproximación ", versión revisada de una disertación presentada en CS Division, UC Berkeley, en agosto de 1994. CS-TR-476-94. Sección 7.2.
- ↑ a b Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti Spaccamela, A. y Protasi, M. (1999), Complexity and Approximation. Problemas de optimización combinatoria y sus propiedades de aproximación, Springer-Verlag, Berlín. Sección 8.4.
- ^ Luca Trevisan. 2001. Resultados de no aproximabilidad para problemas de optimización en instancias de grado acotado. En Actas del trigésimo tercer simposio anual de ACM sobre teoría de la computación (STOC '01). ACM, Nueva York, NY, EE. UU., 453-461. DOI = 10.1145 / 380752.380839 http://doi.acm.org/10.1145/380752.380839
- ^ Sobre algunos resultados de inaproximabilidad más estrictos, Piotr Berman y Marek Karpinski, Proc. ICALP 1999, páginas 200--209.
- ^ P. Berman y M. Karpinski, Límites inferiores de aproximación mejorada en optimización de ocurrencia pequeña, ECCC TR 03-008 (2003)
- ^ P. Berman, M. Karpinski y AD Scott, Aproximación de dureza y satisfacción de instancias de ocurrencia limitada de SAT, ECCC TR 03-022 (2003) .
- ^ P. Berman, M. Karpinski y AD Scott, Dureza de aproximación de instancias simétricas cortas de MAX-3SAT, ECCC TR 03-049 (2003).
- ^ WFde la Vega y M.Karpinski, algoritmo de aproximación 9/8 para MAX-3SAT aleatorio, ECCC TR 02-070 (2002) ; RAIRO-Operations Research 41 (2007), págs. 95-107]
Lecture Notes de la Universidad de California, Berkeley Notas de la teoría de la codificación en la Universidad de Buffalo