Muestreo de fórmulas 3-SAT satisfactorias

23

Considere la siguiente tarea computacional: Queremos muestrear una fórmula 3-SAT de variables (una variante: n variables m cláusulas) con respecto a la distribución de probabilidad uniforme, condicionada a que la fórmula sea satisfactoria:nnm

P1: ¿Se puede lograr esto de manera eficiente con una computadora clásica (con bits aleatorios)?

P2: ¿Se puede lograr esto de manera eficiente con una computadora cuántica?

También estoy interesado en las siguientes dos variantes:

V2: Muestra todas las fórmulas con una distribución de probabilidad que da fórmulas satisfactorias dos veces el peso de las fórmulas insatisfactorias.

V3: muestra donde el peso es el número de tareas satisfactorias (Aquí solo nos preocupamos por Q2).

Actualización: la respuesta de Colins demuestra un algoritmo simple para V3. (Me equivoqué al suponer que esto es clásicamente difícil). Permítanme mencionar otra variante de las tres preguntas:

Especifica de antemano cláusulas y necesita muestrear subconjuntos aleatorios satisfactorios de las cláusulas de entrada.m

Gil Kalai
fuente
66
Pregunta muy interesante Me sorprendería si hay un algoritmo conocido para realizar de manera eficiente cualquiera de estas tareas.
Giorgio Camerani

Respuestas:

12

Hay un algoritmo simple para V3. Usaré la convención de que hay cláusulas posibles, entonces 2 8 n 3 fórmulas. (Esto es solo por simplicidad: si no desea que todas las cláusulas 8 n 3 se consideren válidas, no afectará el siguiente argumento).(2n)328n38n3

{0,1}n7n31/2ϕmm7n3

Colin McQuillan
fuente
3
Esto se menciona en la introducción para generar instancias de problemas satisfactorios , por D Achlioptas, C Gomes, H Kautz, B Selman.
Colin McQuillan