Algoritmo de las Vegas para satisfacer la mayoría de las cláusulas en SAT

Question

Considere la posibilidad de una instancia de SAT con $m$ cláusulas, donde cada cláusula tiene exactamente $k$ literales. Dar Las Vegas algoritmo (es decir, un algoritmo que siempre da el resultado correcto), que encuentra una asignación satisfactoria, al menos, $m(1-2^{-k})$ cláusulas, y analizar sus previsiones de tiempo de ejecución.

Un posible algoritmo de Las Vegas es asignar en forma aleatoria de verdadero/falso a cada una de las variables, cada una con una probabilidad de $1/2$. Si la asignación satisface menos de $m(1-2^{-k})$ cláusulas, rerandomize todas las variables. Siga haciendo esto hasta que tengamos una asignación satisfactoria, al menos, $m(1-2^{-k})$ cláusulas.

Esto es válido en Las Vegas algoritmo, pero no estoy seguro de que es uno de los que cabría esperar por la pregunta. Asimismo, para analizar la espera de ejecución en el tiempo, es necesario calcular la probabilidad de que una asignación al azar de las obras. Esto significa que la asignación al azar satisface, al menos, $m(1-2^{-k})$ cláusulas, y no parece fácil de calcular. Lo que sería un mejor algoritmo de Las Vegas?

Answer 1

Una asignación al azar ha probabilidad de $1 - 2^{-k}$ de la satisfacción de una "o" cláusula de con $k$ literales, porque sólo es falso si todos los $k$ literales son falsas. Así, el número esperado de cláusulas satisfecho es $m (1 - 2^{-k})$. Para los problemas típicos que uno podría esperar que la probabilidad de que al menos $m (1-2^{-k})$ tipo de cláusulas satisfecho es acerca de $1/2$, pero este no siempre es el caso.

Por ejemplo, considere la posibilidad de $m = 2^k - 1$ cláusulas, que consta de todos, pero uno de los $2^k$ posibles cláusulas con $k$ literales formado a partir de $k$ distintas variables y sus negaciones. La probabilidad de satisfacer, al menos, $m (1-2^{-k})$ cláusulas sólo es $2^{-k}$ (con una probabilidad de $1 - 2^{-k}$ que va a satisfacer $m-1$ de las cláusulas, pero $m - 1 < m (1 - 2^{-k})$). En este ejemplo, se espera que el número de iteraciones de su algoritmo es $2^k$. Por otra parte, ningún algoritmo que busca sólo en los número de cláusulas satisfecho por los trabajos pueden hacerlo mejor que eso (porque este número siempre será bien $m-1$ o $m$, y sólo es $m$ para el asignación correcta).

EDIT: puede ser cierto que la probabilidad de éxito en una iteración es, al menos,$1/2^k$, pero no he sido capaz de demostrarlo. Lo mejor que puedo hacer con un simple argumento es este. Supongamos $r$ es el mínimo número de insatisfechos cláusulas que hace que el número de satisfechos a menos de $m (1 - 2^{-k})$, es decir,$r = \lfloor 1 + m/2^k \rfloor$, y $b = 2^k r - m$, por lo que el $1 \le b \le 2^k$. En el ejemplo anterior $r=1$$b = 1$. El número esperado de insatisfecho cláusulas es $m/2^k$. Si $P$ es la probabilidad de éxito en una iteración, es decir, tener en la mayoría de las $r-1$ insatisfecho cláusulas, tenemos $m/2^k \ge r (1-P)$, lo que hace que $$P \ge 1 - \dfrac{m}{2^{k} r} = \dfrac{b}{2^k r} \ge \dfrac{1}{2^k r}$$

Answer 2

Aquí está el ingenuo, derandomized algoritmo:

En primer lugar, podemos convertir entre asignaciones de las variables y los números binarios: se utiliza el número 1 para designar una verdadera asignación de variable, y de 0 a designar falso. n ahora Tenemos los medios de la asignación de un número binario a una asignación de variable. Entonces, la adopción de la convención que $x_i$ $i$th variable, el número de $000...000$ en binario corresponde a $x_1 = $ false, $x_2 = $ false, ... $x_n = $ falso. El número de $000...001$ corresponde a $x_1 = $ verdadera, $x_2 = $ false, ... $x_n = $ falso. $3=000...010$ corresponde a $x_1 = $ false, $x_2 = $ cierto, ... $x_n = $ falso. Y así sucesivamente...

Ahora establezca $c$, nuestro número máximo de clientes satisfechos cláusulas, a $0$. Nos hará un ciclo a través de cada número binario. En el bucle, simplemente calculamos la fórmula que el número binario de mapas, y contar el número de satisfechos cláusulas. Si este es mayor que el actual $c$ valor actual de nuestro máximo satisfecho cláusulas de actualización de $c$ y recuerde que el número binario (que podríamos llamar $b$).

Entonces, cuando el bucle termina, vamos a tener el recuento de la máxima satisfecho cláusulas, junto con las asignaciones de variables, las cuales se almacenan en $b$. Este algoritmo no requiere prácticamente ningún espacio, salvo para almacenar la fórmula e $b$$c$. Su tiempo de ejecución es de curso $2^n$, y va a encontrar la máxima cantidad de clientes satisfechos cláusulas posible.