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

Question

Nurikabe es una restricción basada en la cuadrícula de llenado de rompecabezas, vagamente similar al Buscaminas/Nonograms; los números son colocados en una cuadrícula llena de encendido/apagado de valores para cada celda, con cada número que indica una región de conectado 'en' las células de ese tamaño, y algunas pequeñas limitaciones en la región de 'off' (células debe estar conectado y no puede contener ningún contiguos 2x2 regiones). La página de la Wikipedia tiene más reglas explícitas y muestra los puzzles, si alguien tiene curiosidad.

Hay algunos NP-completitud de las pruebas para el Nurikabe, pero todas se basan en un "unario' presentación del rompecabezas, con una cantidad de datos que se ajusta aproximadamente con el tamaño de la cuadrícula; pero una de las características peculiares de Nurikabe como diferencia de la mayoría de otros similares puzzles es que los casos pueden ser potencialmente 'lapidaria'. La suma de los números debe ser proporcional al área de la cuadrícula (ya que la densidad de las células es, al menos,$1/4$), pero si el tamaño de la cuadrícula es$n$, entonces es posible que un rompecabezas para el uso de $\mathrm{O}(1)$ números de cada uno de tamaño $\Theta(n^2)$ (en lugar de, por ejemplo $\Theta(n)$ números de cada uno de tamaño $\Theta(n)$), para un total de puzzle tamaño de la instancia de $\mathrm{O}(\log(n))$ bits - o, visto de otra manera, dado $n$ bits podemos codificar al menos algunos Nurikabe rompecabezas de tamaño de la cuadrícula exponencial en $n$.

Lo que no sabemos, sin embargo, es si estos sucinta de puzzles pueden codificar cómputo de los problemas duros; las construcciones de la NP-completitud reducciones he visto todo uso $\Theta(n^2)$ números de delimitada tamaño (de hecho, la mayor parte de $1$s y $2$s), y es posible que los rompecabezas con $\mathrm{O}(1)$ números son más simples en cierto modo fundamental (por ejemplo, que en sus regiones son la unión de $\mathrm{O}(1)$ rectángulos, lo que implicaría que exponencialmente tamaño de los testigos todavía existen). ¿Alguien sabe de alguna NEXP-integridad resultados para sucinta Nurikabe (o para el caso cualquier otro relativamente rompecabezas natural), o de una prueba de que incluso este binario codificado versión todavía es NP-completo?

(actualización: me he hecho esta pregunta en más de cstheory.SE como bien, como parece apropiado).

Answer 1

No tengo una prueba de NEXP-integridad, pero me puede ofrecer alguna evidencia de que la sucinta Nurikabe no está en NP y que se puede codificar computacionalmente difíciles problemas. Considerar este 17 x 16 Nurikabe rompecabezas:

y su (creo) solución única:

Este puzzle se basa en la cuarta iteración de la curva de Hilbert de la construcción se describe en el artículo de Wikipedia sobre el espacio de llenado de curvas, ligeramente modificado para producir un rompecabezas con una solución única. Yo no veo ninguna manera de codificar un certificado para esta solución con menos de la 272 bits de la ingenuidad de la codificación. Y yo no veo ninguna manera de resolver el rompecabezas corto exponencial de ensayo y error.

Answer 2

Mi sospecha es que esto es NP-completo-en concreto uno puede crear instancias de Nurikabe casi a lo largo de sus directrices (O(1) los números de tamaño \Theta(n^2) + O(n) números de tamaño S(1)) que se va a codificar cualquier SAT problema. Esta sería la prueba de que el Buscaminas es NP-completo, usted utilizar los cuadros negros para diseñar un circuito de tamaño O(n), y el Nurikabe problema tiene una solución, si el correspondiente SAT problema tiene una solución.