¿Cómo uso el ordenamiento canónico para reducir la simetría en la codificación SAT del problema del casillero?

En el documento "Codificación eficiente de CNF para seleccionar 1 de N objetos", los autores presentan su técnica de "variable comandante" para codificar la restricción, y luego hablan sobre el problema del casillero.

Dado que mi error puede existir en la comprensión de nivel inferior, permítame declarar lo que creo que sé antes de plantear la pregunta:

Deje que y es el número de palomas y agujeros. La codificación ingenua utiliza una variable proposicional que es verdadera cuando la paloma debe colocarse en el agujero . La cláusula $m$ $n$ $X_{i,j}$ $i'th$ $j'th$ $ExactlyOne(X_{1,1}, X_{1,2}, ..., X_{1,n})$ impone que la paloma 1 debe ocupar exactamente un hoyo; Se añaden cláusulas idénticas para las otras palomas. La cláusula hace cumplir que no más de una paloma ocupa agujero 1; Se añaden cláusulas idénticas para los agujeros restantes. $AtMostOne(X_{1,1}, X_{2,1}, ..., X_{m,1})$

Cuando hay más palomas que agujeros (m> n), el problema es irresoluble (obvio para los humanos) pero el solucionador SAT no "ve" este hecho. Cuando no puede encontrar una manera de colocar las palomas buscará un intento con las palomas . No entiende que el orden de las palomas es irrelevante. El periódico, entre otros, llama a esto simetría. $1,2,3,..,m$ $2,1,3,...,m$

Instancias donde se utilizan como una prueba extenuante de la capacidad de un solucionador SAT para detectar la insatisfacción. $m=n+1$

El documento propone romper la simetría imponiendo el orden a las palomas. La paloma debe colocarse en un hoyo enfrente del hoyo de la paloma (es decir, la paloma en el hoyo debe tener un número menor que la paloma en el hoyo ). Luego dice decepcionantemente: "Debido a las limitaciones de espacio, no describimos explícitamente en detalle la codificación de ordenamiento canónico, pero el número de cláusulas generadas es de orden ". $i$ $i+1$ $j$ $j+1$ $O(n*log(n))$

Entonces mi pregunta es: ¿qué hicieron para obtener estos resultados?

Quiero tratar las variables como una cadena de bits que, numéricamente, identifica la elección de qué paloma entró en el hoyo 1, y así sucesivamente. Siga esto con comparadores para hacer cumplir la sugerencia del artículo. Sin embargo, mi ingenua construcción de comparación requiere m cláusulas, una para cada bit (de tamaño cada vez más feo). ¡Ayuda! :) $\{X_{1,1}, X_{2,1}, ..., X_{m,1}\}$ $n-1$

cc.complexity-theory sat proof-complexity Andrew Lamoureux
fuente

Respuestas:

Sea el número de palomas sea el número de agujeros. Supongamos que las variables proposicionales ... codifican la representación binaria de si la th pigeon se coloca en el hoyo . (Ejemplo, si la paloma 1 se colocara en el hoyo 10, , que es binario 1001. Entonces = verdadero, $m$ $n$ $B_{i,0}$ $B_{i,log(n)}$ $j-1$ $i$ $j$ $j - 1 = 9$ $B_{1,3}$ $B_{1,2}$ = falso, = falso y = verdadero.) $B_{1,1}$ $B_{1,0}$

Haga cumplir un orden particular de las palomas en los agujeros al exigir que el agujero codificado por las variables sea menor que el de . Las codificaciones se comparan como cabría esperar: $B_{i}$ $B_{i+1}$

< OR = Y < $B_{i,log(n)}$ $B_{i+1,log(n)}$

$B_{i,log(n)}$ $B_{i+1,log(n)}$ $B_{i,log(n)-1}$ OR = Y = Y $B_{i+1,log(n)-1}$

$B_{i,log(n)}$ $B_{i+1,log(n)}$ $B_{i,log(n)-1}$ $B_{i+1,log(n)-1}$ < O ... $B_{i,log(n)-2}$ $B_{i+1,log(n)-2}$

... siguiendo el patrón de permitir que los bits más significativos sean equivalentes siempre que el siguiente bit a la derecha sea menor que el de la próxima paloma. Habrá conjunciones por comparador y comparadores , dando las cláusulas adicionales esperadas . $O(log(n))$ $O(m)$ $O(m * log(n))$

Los valores de la variable deben estar implicados por los valores . Cada bit está implicado por cualquiera de un conjunto particular de las variables que se establecen. Ejemplo: suponiendo que , tendría: $B$ $X_{i,j}$ $B_{i,*}$ $X_{i,j}$ $n = 16$

$ExactlyOne(X_{1,9}, X_{1,10}, X_{1,11}, X_{1,12}, X_{1,13}, X_{1,14}, X_{1,15}, X_{1,16}, \overline{B_{1,3}})$

lo que fuerza a verdadero si la paloma 1 se coloca en cualquiera de los agujeros 9-16. De lo contrario, se establece como falso para satisfacer la cláusula. Estas cláusulas establecen los bits restantes . $B_{1,3}$ $B_{1,3}$ $B_{i}$

$ExactlyOne(X_{1,5}, X_{1,6}, X_{1,7}, X_{1,8}, X_{1,13}, X_{1,14}, X_{1,15}, X_{1,16}, \overline{B_{1,2}})$ $ExactlyOne(X_{1,3}, X_{1,4}, X_{1,7}, X_{1,8}, X_{1,11}, X_{1,12}, X_{1,15}, X_{1,16}, \overline{B_{1,1}})$ $ExactlyOne(X_{1,2}, X_{1,4}, X_{1,6}, X_{1,8}, X_{1,10}, X_{1,12}, X_{1,14}, X_{1,16}, \overline{B_{1,0}})$

Habrá de estas cláusulas para cada paloma. Como hay palomas, se añaden cláusulas . $log(n)$ $m$ $m * log(n)$

Kyle Jones
fuente

¡Gracias por su respuesta! ¿Pero no se requieren cláusulas adicionales para aplicar la codificación binaria en sí? Usando su ejemplo con la paloma 1 colocada en el hoyo 10, creo que se requieren cláusulas para obligar a

. Esto se expande a las cláusulas

en CNF. Y necesitamos uno para cada

, lo que resulta en

X_{1, 10} \to B_{1, 3} \land \bar{B_{1, 2}} \land \bar{B_{1, 1}} \land B_{1, 0}

$X_{1,10} \to B_{1,3} \land \overline{B_{1,2}} \land \overline{B_{1,1}} \land B_{1,0}$

l o g (n)

$log(n)$

X_{i, j}

$X_{i,j}$

crecimiento de nuevo.

m * n

$m*n$

Andrew Lamoureux

Editaré la respuesta para abordar esto.

Kyle Jones

Usando

para "comprimir" lo detallado "si la paloma va aquí, los bits deben ser estas" declaraciones es simplemente brillante. Dado que esta restricción es el tema de su trabajo, no hay duda de que su solución es lo que se omitió. Gracias kyle

E x a c t l y O n e ()

$ExactlyOne()$

Andrew Lamoureux