¿Cuál es la definición precisa de Random K-SAT?

12

Hay 4 restricciones diferentes que podemos tener al definir Random K-SAT.
1) El número total de literales en una cláusula dada es exactamente K o como máximo K
2) Un literal dado se puede usar con o sin reemplazo en la misma cláusula (A o A o A)
3) Una variable dada se puede usar con o sin reemplazo en la misma cláusula (A o ~ A o ~ A)
4) Una cláusula dada se puede usar con o sin reemplazo en una fórmula dada
¿Cuál sería la definición más "correcta"? ¿Cuáles son las desventajas y las ventajas de usar estas diferentes definiciones?

Tayfun Pay
fuente
17
No creo que haya una única definición universalmente aceptada.
Tsuyoshi Ito
55
Otra opción diferente que puede hacer es elegir un número fijo de cláusulas (con o sin reemplazo) o elegir una muestra de Poisson (cada cláusula se incluye independientemente con una probabilidad fija).
David Eppstein
44
@ Tsuyoshi, Geekster: Estoy de acuerdo con Tsuyoshi, por lo que sé, los solucionadores de SAT no necesitan ninguna definición de k-SAT aleatorio, independientemente de la técnica que utilicen (DPLL, búsqueda local, propagación de encuestas). Estoy 100% seguro de que cualquier solucionador SAT serio eliminará cláusulas duplicadas, cláusulas tautológicas y literales duplicados antes de comenzar la búsqueda. Algunos solucionadores también eliminan cláusulas subsumidas.
Giorgio Camerani
44
No creo que haya una respuesta a la pregunta en la forma actual porque no hay definiciones que parezcan "más correctas" que otras y "contras y pros" probablemente dependan de para qué desea utilizar los resultados en k-SAT aleatorio. He votado para cerrarlo como una pregunta no real.
Tsuyoshi Ito
44
Supongo que la pregunta se puede volver a plantear, eliminar la parte "más correcta" y concentrarse en las desventajas y ventajas de algunos resultados específicos. (O la respuesta puede pasar por cada resultado posible). Dado que esta pregunta es de alguna manera similar a una pregunta sobre el corte más espaciado que parece estar dentro del alcance sin ningún argumento, personalmente me gustaría ver que la pregunta permanezca abierta.
Hsien-Chih Chang 張顯 之

Respuestas:

15

k

k k

Dos modelos principales:

El modelo aleatorio de Selman : se permiten cláusulas repetidas . Kyle dio esta buena referencia en los comentarios a su respuesta, pero asumió incorrectamente que el modelo rechazaba cláusulas repetidas. La versión enlazada (ligeramente diferente) del documento contiene una discusión más detallada del modelo aleatorio en la Sección 3: "Este método de generación permite cláusulas duplicadas en una fórmula ... Sin embargo, a medida que N obtiene duplicados grandes, será raro porque generalmente seleccione solo un número lineal de cláusulas ".

m2k(nk)

Equivalencia de ubicaciones de transición de fase :

Sin embargo, la transición de fase (umbral de satisfacción del 50%) ocurre en la misma relación de cláusula a variable, independientemente de cuál de estos modelos se elija esencialmente por la razón que Selman et al. señalado en su papel.

Supongamos que denota el número esperado de pares idénticos de cláusulas en una instancia aleatoria de Selman -SAT. La probabilidad de que un par de cláusulas sea idéntico es , mientras que el número total de pares de cláusulas es . Por la linealidad de la expectativa, .A(n,m,k)(n,m,k)p=1/(2k(nk))N=(m2)A(n,m,k)=pN=(m2)/2k(nk)

Según el Teorema 3 en [1], el límite superior demostrable en la ubicación de la transición de fase -SAT, usando el modelo Achlioptas, ocurre cuando . Al fijar y establecer obtenemoskm=O(2kn)k3m=O(2kn)

A(n,m,k)=(m2)/2k(nk)=O(m2)/O(nk)=O(n2)/O(nk) .

Entonces, porque , , lo que significa que en la expectativa habrá cero cláusulas repetidas alrededor del -SAT transición de fase al generar fórmulas SAT aleatorias utilizando el modelo Selman.k3limnO(n2)/O(nk)=0k

Auto promoción desvergonzada: discuto estos temas brevemente en la Sección 4.1 de mi tesis de maestría .

QBF aleatorio

Como resultado, la situación es mucho más interesante para QBF aleatorio. ¿Cuáles son AFAIK? Los primeros tres documentos sobre QBF aleatorio propusieron cada uno un nuevo modelo aleatorio, criticando a su predecesor.

Ver los siguientes documentos:

  • Cadoli y col. "Análisis experimental del costo computacional de la evaluación de fórmulas booleanas cuantificadas". AI * IA 1997
  • Gent + Walsh "Más allá de NP: la transición de fase QSAT". AAAI / IAAI 1999
  • Chen + Interian "Un modelo para generar fórmulas booleanas cuantificadas al azar". IJCAI 2005
Huck Bennett
fuente
14

[Editado para mayor claridad]

La definición más utilizada en la literatura de investigación es la que requiere exactamente k variables distintas por cláusula, y no cláusulas duplicadas. Si relaja la restricción de las distintas variables, gran parte de la investigación existente no tendrá sentido para usted porque sus resultados no coincidirán con los suyos. La conocida transición de fase sat / unsat ocurrirá en una relación de cláusula a variable diferente (si la transición existe) y no encontrará las instancias difíciles de SAT donde esperaría de la literatura.

Kyle Jones
fuente
3
Generando problemas difíciles de satisfacción por Mitchell, Selman y Levesque. La Sección 4 describe lo que ellos llaman "Random K-SAT". El periódico no habla de relajar las restricciones; eso viene de modificar un generador aleatorio 3SAT y alimentar muchas instancias en un solucionador SAT basado en DPLL típico.
Kyle Jones
55
"La definición más correcta es la que produce la transición de fase sat / unsat en alrededor de 4.26 cláusulas por variable para 3SAT aleatorio". Debes estar bromeando.
Tsuyoshi Ito
1
@ Tsuyoshi: Si bien "lo más correcto" es definitivamente una exageración, creo que el argumento es que esta versión es estándar y una de las mejor estudiadas.
Huck Bennett
2
Está haciendo una afirmación extraña de que 4.26 es el número mágico que distingue una definición particular del término "k-SAT aleatorio" como la más correcta. Si esto no es una broma, no sé qué decir.
Tsuyoshi Ito
44
No, estoy afirmando que el descubrimiento de la transición de fase y toda la investigación posterior y los documentos que siguieron están de acuerdo con la definición predeterminada de k-SAT aleatorio, que es la definición que di. Si usa una definición diferente, muchos documentos no tendrán sentido porque sus resultados no coincidirán con los suyos. Si está trabajando en un solucionador SAT, encontrará instancias fáciles en las que todos los trabajos relacionados que he leído dicen que debería encontrar los difíciles. No tiene nada de mágico, solo una convención establecida en este momento. Si quieres citar contraejemplos, hazlo.
Kyle Jones