MAX-3SAT

MAX-3SAT es un problema del 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 3-CNF Φ (es decir, con como máximo 3 variables por cláusula), encuentre una asignación que satisfaga el mayor número de cláusulas.

MAX-3SAT es un problema canónico completo para la clase de complejidad MAXSNP (mostrado completo en Papadimitriou pág. 314).

Aproximabilidad

La versión de decisión de MAX-3SAT es NP-completa . Por lo tanto, solo se puede lograr una solución en tiempo polinómico si P = NP . Sin embargo, se puede lograr una aproximación dentro de un factor de 2 con este algoritmo simple:

Genere la solución en la que se satisfacen la mayoría de las cláusulas, cuando todas las variables son VERDADERAS o todas las variables son FALSAS.
Cada cláusula se satisface mediante 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. Si bien este algoritmo es aleatorio, se puede desaleatorizar utilizando, por ejemplo, las técnicas de ^[1] para producir un algoritmo determinista (en tiempo polinomial) con las mismas garantías de aproximación.

Teorema 1 (inaproximabilidad)

El teorema PCP implica que existe un ε > 0 tal que la aproximación (1- ε ) de MAX-3SAT es NP-dura .

Prueba:

Cualquier problema NP-completo ⁠ ⁠ $L\in {\mathsf {PCP}}(O(\log(n)),O(1))$ por el teorema PCP . Para x ∈ L , se construye una fórmula 3-CNF Ψ _{x de modo que}

x ∈ L ⇒ Ψ _x es satisfacible
x ∉ L ⇒ no más de (1- ε ) m cláusulas de Ψ _x son satisfacibles.

El verificador V lee todos los bits requeridos a la vez, es decir, realiza consultas no adaptativas. Esto es válido porque la cantidad 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 es . $r(x)=O(\log |x|)$
Para cada R _i
- V elige q posiciones i ₁ ,..., i _q y una función booleana f _R : {0,1} ^q ->{0,1} y acepta si y solo si f _R (π(i ₁ ,...,i _q )). Aquí π se refiere a la prueba obtenida del Oráculo.

A continuación, tratamos de encontrar una fórmula booleana para simular esto. Introducimos las variables booleanas x ₁ ,..., x _l , donde l es la longitud de la prueba. Para demostrar que el Verificador se ejecuta en tiempo polinomial probabilístico , necesitamos una correspondencia entre el número de cláusulas satisfacibles 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 a longitud 3 agregando nuevas variables (auxiliares) p. ej. x ₂ ∨ x ₁₀ ∨ x ₁₁ ∨ x ₁₂ = ( x ₂ ∨ x ₁₀ ∨ y _R ) ∧ ( y_R ∨ x ₁₁ ∨ x ₁₂ ). Esto requiere un máximo de q 2 ^q 3 cláusulas SAT .
Si z ∈ L entonces
- Hay una prueba π tal que V ^π ( z ) se acepta para cada R _i .
- Todas las cláusulas se satisfacen si x _i = π ( i ) y las variables auxiliares se agregan correctamente.
Si la entrada z ∉ L entonces
- Para cada asignación a x ₁ ,..., x _{l e} y R _'s , la prueba correspondiente π( i ) = x _i hace que el Verificador rechace para 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. ${\frac {1}{2}}{\frac {1}{q2^{q}}}$

Se puede concluir que si esto es válido para todo problema NP-completo , entonces el teorema PCP debe ser verdadero.

Teorema 2

Håstad ^[2] demuestra un resultado más estricto que el Teorema 1, es decir, el mejor valor conocido para ε .

Construye un verificador PCP para 3-SAT que lee sólo 3 bits de la prueba.

Para cada ε > 0, hay un verificador PCP M para 3-SAT que lee una cadena aleatoria r de longitud ⁠ ⁠ $O(\log(n))$ y calcula las posiciones de 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 completitud (1− ε ) y solidez 1/2 + ε (consulte PCP (complejidad) ). El verificador satisface

z\in L\implica \existe \pi Pr[V^{\pi }(z)=1]\geq 1-\epsilon

z\no \en L\implica \para todo \pi Pr[V^{\pi }(z)=1]\leq {\frac {1}{2}}+\epsilon

Si la primera de estas dos ecuaciones se equiparara a "=1" como de costumbre, se podría encontrar una prueba de π resolviendo un sistema de ecuaciones lineales (ver MAX-3LIN-EQN ) implicando 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 , se contradicen 1/4 cláusulas.

Esto es suficiente para demostrar la dureza de la relación de aproximación.

{\frac {1-{\frac {1}{4}}({\frac {1}{2}}-\epsilon )}{1-\epsilon }}={\frac {7}{8}}+\epsilon '

Problemas relacionados

MAX-3SAT(B) es el caso especial restringido de MAX-3SAT donde cada variable ocurre en, como máximo, cláusulas B. Antes de que se demostrara el teorema PCP , Papadimitriou y Yannakakis ^[3] demostraron que para alguna constante fija B, este problema es MAX SNP-hard. En consecuencia, con el teorema PCP, también es APX-hard. Esto es útil porque MAX-3SAT(B) a menudo se puede utilizar para obtener una reducción que preserve PTAS de una manera que MAX-3SAT no puede. Las pruebas para valores explícitos de B incluyen: todos los B ≥ 13, ^[4]^[5] y todos los B ≥ 3 ^[6] (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. ^[6]

La mejor razón de aproximación posible para MAX-3SAT(B), como función de B, es al menos y como máximo , ^[7] a menos que NP = RP . Se conocen algunos límites explícitos sobre las constantes de aproximabilidad para ciertos valores de B. ^[8]^[9]^[10] 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 aproximar para algún factor constante. ^[11] $7/8+\Omega (1/B)$ $7/8+O(1/{\sqrt {B}})$

MAX-EkSAT es una versión parametrizada de MAX-3SAT donde cada cláusula tiene exactamente $k$ literales, para k ≥ 3. Se puede aproximar de manera eficiente con una relación de aproximación usando ideas de la teoría de codificación . $Estilo de visualización 1-(1/2)^{k}}$

Se ha demostrado que las instancias aleatorias de MAX-3SAT se pueden aproximar dentro del factor ⁠8/9⁠ . ^[12]

Referencias

^ Sivakumar, D. (19 de mayo de 2002), "Desaleatorización algorítmica a través de la teoría de la complejidad", Actas del trigésimo cuarto simposio anual de la ACM sobre teoría de la computación , págs. 619-626, doi :10.1145/509907.509996, ISBN 1581134959, S2CID 94045
^ Håstad, Johan (2001). "Algunos resultados de inaproximabilidad óptima". Revista de la ACM . 48 (4): 798–859. CiteSeerX 10.1.1.638.2808 . doi :10.1145/502090.502098. S2CID 5120748.
^ Christos Papadimitriou y Mihalis Yannakakis, Optimización, aproximación y clases de complejidad, Actas del vigésimo simposio anual de la ACM sobre teoría de la computación, págs. 229-234, 2 al 4 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 dificultad de problemas de aproximación", versión revisada de una disertación presentada en la División de Ciencias de la Computación de la Universidad de California en Berkeley en agosto de 1994. CS-TR-476-94. Sección 7.2.
^ ab Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti Spaccamela, A. y Protasi, M. (1999), Complejidad y aproximación. 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 aproximación para problemas de optimización en instancias de grado acotado. En Actas del trigésimo tercer simposio anual de la 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 mejorados en la optimización de ocurrencias pequeñas, ECCC TR 03-008 (2003)
^ P. Berman, M. Karpinski y AD Scott, Dureza de aproximación y satisfacibilidad de instancias de ocurrencia acotada 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), pp.95-107]

Notas de clase de la Universidad de California, Berkeley Notas de teoría de codificación en la Universidad de Buffalo