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

18

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{1n,1¯n¯}m × m 1 × mk k{1n}m2k¯k{1n}m2m×m1×mse 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 0111nnnn=10101my 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 (enT0000T0001T0011T0101T0111 T 0000 + T 0001 + T 0011 + T 0101 + T 0111 + T 1111 = m 2 m mT1111T0000+T0001+T0011+T0101+T0111+T1111=m2mm) 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)

Steven Stadnicki
fuente
2
No puede ser NP completo, ya que solo hay entradas posibles, y según el teorema de Mahaney, necesita más que eso para hacer un problema NP completo (a menos que P = NP). Pero si usa un marco, esta obstrucción desaparece. Por lo tanto, puede ser NP-completo con un marco. θ(m10)
Peter Shor
1
Un paso intermedio sería demostrar que el problema de decidir si un rompecabezas de 6 fichas parcialmente lleno (es decir, algunas de las piezas ya están en el tablero y no se pueden mover) se puede completar correctamente es NP-complete.
Vor

Respuestas:

3

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

DW
fuente
Estoy de acuerdo en que esto parece un medio razonable para resolver el problema, pero estoy menos interesado en resolver casos específicos del problema que en comprender su complejidad. (Por ejemplo, si está en P, entonces es casi seguro que hay algún tipo de enfoque de programación dinámica que superaría fácilmente a los solucionadores de programación lineal / SAT abstractos sobre el problema)
Steven Stadnicki
n
nm
@StevenStadnicki, ¡ah, mi error! Lo siento, no leí con suficiente atención. Eso tiene sentido, gracias.
DW
No se preocupe, debería haberlo considerado por adelantado; Cuando llegue a casa, intentaré editar la pregunta para usar una parametrización más 'tradicional'.
Steven Stadnicki