¿Cuál es la complejidad de (posiblemente sucinta) Nurikabe?

Nurikabe es un rompecabezas de relleno de cuadrícula basado en restricciones, más o menos similar al Buscaminas / Nonogramas; los números se colocan en una cuadrícula que se debe llenar con valores de activación / desactivación para cada celda, con cada número que indica una región de celdas conectadas 'encendidas' de ese tamaño, y algunas restricciones menores en la región de celdas 'apagadas' ( debe estar conectado y no puede contener ninguna región contigua de 2x2). La página de Wikipedia tiene reglas más explícitas y ejemplos de rompecabezas.

Genéricamente, los rompecabezas de este tipo tienden a ser NP-completos, y Nurikabe no es una excepción; caen en NP porque la solución en sí misma sirve como testigo (polinomialmente verificable) del problema. Pero a diferencia de la mayoría de los acertijos similares, las instancias de Nurikabe pueden ser concisas: el Sudoku en una cuadrícula requiere que ns ( n ) se resuelva (si se ofrecen menos de n - 1 , entonces no hay forma de distinguir entre los símbolos que faltan) , Los Nonogramas obviamente requieren al menos uno dado para cada fila o columna, y el Buscaminas debe tener rendimientos en al menos $n\times n$$\Theta(n)$$n-1$ de las celdas o habrá celdas que no estén al lado de un determinado (y cuyo estado, por lo tanto, no se puede determinar). Pero mientras que los dados de un rompecabezas Nurikabe tienen que sumar aΘ(n2), es posible tenerO(1)givens cada uno de ese tamaño, por lo quetheta(log(n))los bits podrían ser suficientes para especificar un rompecabezas Nurikabe de tamañon, o invertidos,kbits pueden ser suficientes para especificar una instancia de Nurikabe de tamaño exponencial enk, lo que significa que la única garantía es que el problema radica en NEXP.$1\over16$$\Theta(n^2)$$\mathrm{O}(1)$$\Theta(\log(n))$$n$$k$$k$

Desafortunadamente, las pruebas de la dureza de Nurikabe He encontrado que todas las construcciones de uso con dan un tamaño constante, por lo que sus instancias son polinomiales en el tamaño de la cuadrícula en lugar de logarítmicas, y no puedo descartar que todo sea 'sucinto' solucionable 'Los acertijos Nurikabe tienen una estructura adicional de tal manera que las soluciones pueden describirse y verificarse de la misma manera; Por ejemplo, el único ejemplo que conozco de un rompecabezas con 2 valores de tamaño Θ ( n 2 ) conduce a regiones de celdas tanto dentro como fuera que son la unión de O ( 1 $\Theta(n^2)$$\Theta(n^2)$$\mathrm{O}(1)$rectángulos, y así tienen una descripción sucinta propia. ¿Alguien sabe de investigaciones adicionales que se hayan realizado en este rompecabezas más allá del resultado básico de completitud de NP, y en particular de cualquier resultado de complejidad adicional para los casos posiblemente sucintos?

(nota: esto se preguntó originalmente en mates.SE , pero aún no ha habido ninguna respuesta allí y esto parece apropiado a nivel de investigación para este sitio)

Parece que realmente estás preguntando: ¿está Nurikabe en NP?

Nurikabe es NP-hard, ya que uno puede construir dispositivos de tamaño polinómico que se pueden usar para reducir un problema de NP completo a un problema de decisión de Nurikabe. Esto es lo que hacen Holzer, Klein y Kutrib, y también McPhail y Fix en su póster (ambos referenciados en el artículo de Wikipedia).

Ambos grupos de autores suponen que el problema es trivial en NP, y descartan la cuestión de la membresía. Su inquietud por las instancias sucintas parece acertada: no creo que el problema esté en NP. Considere la siguiente forma de formalizar el problema de decisión:

NURIKABE BINARIO
Entrada: enteros myn en binario , que representan un tablero Nurikabe y una lista de triples, cada uno de los cuales indica una posición en el tablero y un entero positivo escrito en esa posición.
Pregunta: ¿ pueden las posiciones restantes del tablero colorearse con dos colores, respetando las restricciones de Nurikabe?

$m$$n$$mn$

$(m-2)(n-2)$$m \times n$$mn-1$$\Theta(\log\, m + \log\, n)$

Entonces su pregunta es: ¿existen certificados de tamaño polinómico para todas las instancias binarias de Nurikabe, que pueden verificarse en tiempo polinómico?

No es obvio para mí que tales certificados existan necesariamente. Tampoco es obvio cómo se probaría que no pueden existir certificados sucintos y rápidamente verificables.

Sin embargo, la restricción a soluciones únicas significa que el problema es en realidad duro en los EE. UU. El punto es que si uno considera que "tiene una solución única" como una restricción de Nurikabe (en oposición a una característica deseable de instancias que se presentan a los humanos), entonces no es suficiente demostrar que hay una solución, pero también se debe demostrar que no hay otras soluciones posibles. Este requisito por sí solo es suficiente para garantizar que el problema probablemente no esté en NP. Esto es cierto incluso para la versión unaria del problema.

En resumen: si uno relaja el requisito de soluciones únicas y especifica el tamaño del tablero en unario, entonces el problema de decisión está en NP; con soluciones no únicas y tamaño de placa binaria, no está claro si el problema de decisión está en NP; y con soluciones únicas, el problema de decisión es difícil en los Estados Unidos y, por lo tanto, es poco probable que esté en NP, ya sea para la codificación del tamaño de la placa.