¿Los rompecabezas 'cero-uno' son NP completos?

Estoy interesado en una pequeña variante de mosaico, el rompecabezas: cada borde de un mosaico (cuadrado) está etiquetado con un símbolo de , y se pueden colocar dos mosaicos adyacentes uno al otro si el símbolo en el borde frontal de un mosaico es y el símbolo en el borde frontal de otro mosaico es , para algunos . Luego, dado un conjunto de fichas, ¿se pueden colocar en un (girando pero no volteando las fichas) con todos los bordes coincidentes correctamente? (También hay una variante sobre este problema en la que cuatro$\{1\ldots n, \bar{1}\ldots\bar{n}\}$m × m 1 × $k$ k∈{1…n}m$\bar{k}$$k\in\{1\ldots n\}$$m^2$$m\times m$$1\times m$se proporcionan bordes de 'enmarcado' y las piezas deben encajar correctamente en ese marco).

Sé que este problema es NP-completo para suficientemente grande , pero los límites que he visto en parecen ser bastante grandes; Estoy interesado en el problema para valores pequeños de y en particular para , el caso 'cero uno' (donde cada borde está etiquetado como o y los bordes con un deben coincidir con los bordes con un ) Aquí hay (con simetría rotacional) solo seis tipos de mosaico (el mosaico de todos los ceros, el mosaico de todos, el mosaico con tres ceros y uno, el mosaico con tres unos y un cero, y dos mosaicos distintos con dos ceros y dos, '0011' y '0101'), por lo que una instancia de problema es solo una especificación den n n = 1 0 1 0 1 m T 0000 T 0001 T 0011 T 0101 T $n$$n$$n$$n=1$$0$$1$$0$$1$$m$y un conjunto de cinco números , , , , y (que representan el recuento de cada tipo de mosaico) con . El problema está obviamente en NP (con dado en unario) ya que una solución simplemente se puede exhibir y luego verificar en polinomio (en$T_{0000}$$T_{0001}$$T_{0011}$$T_{0101}$$T_{0111}$ T 0000 + T 0001 + T 0011 + T 0101 + T 0111 + T 1111 = m 2 m $T_{1111}$$T_{0000}+T_{0001}+T_{0011}+T_{0101}+T_{0111}+T_{1111}=m^2$$m$$m$) tiempo, pero ¿se sabe que es NP completo, o hay algún algoritmo de programación dinámica que se pueda aplicar aquí? ¿Qué pasa con el caso 'enmarcado' en el que la especificación del problema también incluye los cuatro bordes del cuadrado que deben coincidir? (Obviamente, si el caso no enmarcado es NP-completo, el caso enmarcado seguramente también lo es)

Como mencionó que está interesado en resolver este problema para valores pequeños de , le sugiero que intente implementar esto en un solucionador SAT o como un programa lineal entero (ILP). Cualquiera de los dos podrá codificar las restricciones, pero de una manera ligeramente diferente:$n$

• Para SAT, hay una codificación muy limpia de la elección de qué mosaico va en cada cuadrado, y una codificación un poco menos limpia de la restricción con respecto al número de cada tipo de mosaico (usando aritmética de bits).

• Para ILP, hay una codificación muy limpia de la restricción con respecto al número de cada tipo de mosaico disponible, y una codificación un poco menos limpia de las restricciones en las que los mosaicos pueden ser adyacentes entre sí (pero aún es expresable, ya que puede expresar fórmulas booleanas arbitrarias en ILP).

Yo esperaría que por pequeña o mediana , este enfoque podría funcionar de manera eficiente.$n$