MAXEkSAT

MAXEkSAT es un problema de la teoría de la complejidad computacional que consiste en una versión de maximización del problema de satisfacibilidad booleana 3SAT . En MAXEkSAT, cada cláusula tiene exactamente k literales, cada uno con variables distintas, y está en forma normal conjuntiva . Estas fórmulas se denominan k-CNF. El problema consiste en determinar el número máximo de cláusulas que pueden ser satisfechas mediante una asignación de valores de verdad a las variables de las cláusulas.

Decimos que un algoritmo A proporciona una α - aproximación a MAXEkSAT si, para algún α positivo fijo menor o igual a 1, y para cada fórmula kCNF φ , A puede encontrar una asignación de verdad a las variables de φ que satisfaga al menos una α -fracción del número máximo de cláusulas satisfacibles de φ .

Debido a que el problema k -SAT NP-difícil (para k ≥ 3) es equivalente a determinar si la instancia MAXEkSAT correspondiente tiene un valor igual al número de cláusulas, MAXEkSAT también debe ser NP-difícil, lo que significa que no hay un algoritmo de tiempo polinomial a menos que P=NP . Una pregunta natural siguiente, entonces, es la de encontrar soluciones aproximadas: ¿cuál es el mayor número real α < 1 tal que algún algoritmo explícito P (complejidad) siempre encuentra una solución de tamaño α·OPT , donde OPT es la asignación maximizadora (potencialmente difícil de encontrar)? Si bien el algoritmo es eficiente, no es obvio cómo eliminar su dependencia de la aleatoriedad. Hay problemas relacionados con la satisfacibilidad de fórmulas booleanas de forma normal conjuntiva.

Algoritmo de aproximación

Existe un algoritmo simple aleatorio de tiempo polinomial que proporciona un $\textstyle \left(1-{\frac {1}{2^{k}}}\right)$ -aproximación a MAXEkSAT: establezca cada variable de forma independiente como verdadera con una probabilidad de 1/2 , de lo contrario , establézcala como falsa.

Una cláusula c dada se considera insatisfecha solo si todos sus k literales constituyentes se evalúan como falsos. Debido a que cada literal dentro de una cláusula tiene una probabilidad de 1/2 de evaluarse como verdadero independientemente del valor de verdad de cualquiera de los otros literales, la probabilidad de que todos sean falsos es $\textstyle ({\frac {1}{2}})^{k}={\frac {1}{2^{k}}}$ Por lo tanto, la probabilidad de que c se cumpla es $\textstyle 1-{\frac {1}{2^{k}}}$ , por lo tanto, la variable indicadora $\textstyle 1_ {c}$ (es decir, 1 si c es verdadero y 0 en caso contrario) tiene esperanza $\textstyle 1-{\frac {1}{2^{k}}}$ . La suma de todas las variables indicadoras sobre todo $\textstyle |C|$ cláusulas es $(\textstyle 1-{\frac {1}{2^{k}}})|C|$ , por lo tanto, por linealidad de la esperanza satisfacemos una $\textstyle \left(1-{\frac {1}{2^{k}}}\right)$ fracción de las cláusulas en expectativa. Porque la solución óptima no puede satisfacer más que todas $\textstyle |C|$ de las cláusulas, tenemos que ${\textit {ALG}}=\left(1-{\frac {1}{2^{k}}}\right)\cdot |C|>\left(1-{\frac {1}{2^{k}}}\right)\cdot {\textit {OPT}}$ , por lo que el algoritmo encuentra un $\textstyle \geq \left(1-{\frac {1}{2^{k}}}\right)$ aproximación a la verdadera solución óptima en promedio.

A pesar de su alta expectativa, este algoritmo puede ocasionalmente encontrar soluciones de valor inferior a la expectativa que calculamos anteriormente. Sin embargo, en un gran número de ensayos, la fracción promedio de cláusulas satisfechas tenderá a $\textstyle \left(1-{\frac {1}{2^{k}}}\right)$ Esto implica dos cosas:

Debe existir una asignación que satisfaga al menos una $\textstyle \left(1-{\frac {1}{2^{k}}}\right)$ fracción de las cláusulas. Si no las hubiera, nunca podríamos alcanzar un valor tan grande en promedio en un gran número de ensayos.
Si ejecutamos el algoritmo un gran número de veces, al menos la mitad de los ensayos (en promedio) satisfarán alguna condición. $\textstyle (1-{\frac {2}{2^{k}}})$ fracción de las cláusulas. Esto se debe a que cualquier fracción menor reduciría el promedio lo suficiente como para que el algoritmo deba ocasionalmente satisfacer más del 100% de las cláusulas para volver a su expectativa de $\textstyle \left(1-{\frac {2}{2^{k}}}\right)$ , lo cual no puede suceder. Extendiendo esto usando la desigualdad de Markov , al menos algunos $\textstyle 1-\left({\frac {1}{1+2^{k}\epsilon }}\right)$ -fracción de los ensayos (en promedio) satisfará al menos una $\textstyle \left(1-{\frac {1}{2^{k}}}-\epsilon \right)$ -fracción de las cláusulas. Por lo tanto, para cualquier positivo $\textstyle \epsilon$ , solo se necesita un número polinomial de ensayos aleatorios hasta que esperamos encontrar una asignación que satisfaga al menos una $\textstyle \left(1-{\frac {1}{2^{k}}}-\epsilon \right)$ fracción de las cláusulas.

Un análisis más robusto (como el de ^{[ 1 ]} ) muestra que, de hecho, satisfaremos al menos una $\textstyle \left(1-{\frac {1}{2^{k}}}\right)$ -fracción de las cláusulas una fracción constante del tiempo (dependiendo solo de k ), sin pérdida de $\textstyle \epsilon$ .

Desaleatorización

Si bien el algoritmo anterior es eficiente, no es obvio cómo eliminar su dependencia de la aleatoriedad. Probar todas las asignaciones aleatorias posibles es equivalente al enfoque ingenuo de fuerza bruta, por lo que puede llevar un tiempo exponencial. Una forma ingeniosa de desaleatorizar lo anterior en tiempo polinomial se basa en el trabajo con códigos de corrección de errores , que satisfacen una $\textstyle \left(1-{\frac {1}{2^{k}}}\right)$ fracción de las cláusulas en tiempo polinomial en el tamaño de entrada (aunque el exponente depende de k ).

Necesitamos una definición y dos hechos para encontrar el algoritmo.

Definición

$S\subseteq \{0,1\}^{n}$ es una fuente independiente de $ℓ si, para un conjunto aleatorio elegido uniformemente$ $(x 1, x 2, ..., x n) \in S,$ $x 1, x 2, ..., x n$ son variables aleatorias independientes de $ℓ$ .

Hecho 1

Nótese que dicha asignación puede encontrarse entre elementos de cualquier fuente independiente de $ℓ sobre$ n variables binarias . Esto es más fácil de ver una vez que se comprende que una fuente independiente de $ℓ$ es simplemente cualquier conjunto de vectores binarios sobre ${0, 1} n$ con la propiedad de que todas las restricciones de esos vectores a $ℓ$ coordenadas deben presentar las 2 ^ℓ posibles combinaciones binarias un número igual de veces.

Hecho 2

Recuerde que BCH _{2, m , d} es un $[n=2^{m},n-1-\lceil {d-2}/2\rceil m,d]_{2}$ código lineal .

Existe una fuente independiente de tamaño $ℓ$ $O(n^{\lfloor \ell /2\rfloor })$ , es decir, el dual de un código $BCH 2,log n, ℓ +1$ , que es un código lineal. Dado que todo código BCH puede presentarse como una restricción computable en tiempo polinomial de un código Reed Solomon relacionado , que a su vez es fuertemente explícito, existe un algoritmo en tiempo polinomial para encontrar dicha asignación a los x _i 's. La prueba del hecho 2 puede encontrarse en Dual of BCH es una fuente independiente .

Esquema del algoritmo

El algoritmo funciona generando $BCH 2,log n, ℓ +1$ , calculando su dual (que como conjunto es una fuente independiente de $ℓ elementos) y tratando cada elemento (palabra clave) de esa fuente como una asignación de verdad a las$ n variables en φ . Al menos una de ellas satisfará al menos $1 - 2 - ℓ$ de las cláusulas de φ , siempre que φ esté en forma kCNF, $k = ℓ$ .

Problemas relacionados

Existen muchos problemas relacionados con la satisfacibilidad de las fórmulas booleanas en forma normal conjuntiva.

Problemas de decisión :
- 2SAT
- 3SAT
Problemas de optimización, cuyo objetivo es maximizar el número de cláusulas satisfechas:
- MAX-SAT y la versión ponderada correspondiente, Max-SAT ponderada.
- MAX- k SAT, donde cada cláusula tiene exactamente k variables:
  - MÁXIMO-2SAT
  - MÁXIMO-3SAT
  - MAXEkSAT
- El problema de satisfacibilidad máxima parcial (PMAX-SAT) busca el número máximo de cláusulas que pueden satisfacerse mediante cualquier asignación de un subconjunto dado de cláusulas. El resto de las cláusulas deben satisfacerse.
- El problema de satisfacibilidad suave (soft-SAT), dado un conjunto de problemas SAT, pide el número máximo de conjuntos que pueden ser satisfechos por cualquier asignación. ^{[ 2 ]}
- El problema de la satisfacibilidad mínima.
El problema MAX-SAT puede extenderse al caso en que las variables del problema de satisfacción de restricciones pertenecen al conjunto de los números reales. El problema consiste en encontrar el q más pequeño tal que la intersección q - relajada de las restricciones no sea vacía. ^[³^]

Véase también

Referencias

↑ "Max-SAT" (PDF) . Archivado del original (PDF) el 23-09-2015 . Consultado el 01-09-2014 .
↑ Josep Argelich y Felip Manyà. "Solucionadores exactos de Max-SAT para problemas demasiado restringidos" . En Journal of Heuristics 12(4) págs. 375-392. Springer, 2006.
↑ Jaulin, L.; Walter, E. (2002). "Estimación minimax no lineal robusta garantizada" (PDF) . IEEE Transactions on Automatic Control . 47 (11): 1857– 1864. doi : 10.1109/TAC.2002.804479 .

Enlaces externos

Apuntes sobre teoría de la codificación en el MIT.

[1] "Max-SAT" (PDF) . Archivado del original (PDF) el 23-09-2015 . Consultado el 01-09-2014 .

[2] Josep Argelich y Felip Manyà. "Solucionadores exactos de Max-SAT para problemas demasiado restringidos" . En Journal of Heuristics 12(4) págs. 375-392. Springer, 2006.

[3] Jaulin, L.; Walter, E. (2002). "Estimación minimax no lineal robusta garantizada" (PDF) . IEEE Transactions on Automatic Control . 47 (11): 1857– 1864. doi : 10.1109/TAC.2002.804479 .

[ 1 ]

[ 2 ]

[