Qual é a complexidade do Nurikabe (possivelmente sucinto)?

Nurikabe é um quebra-cabeça de preenchimento de grade baseado em restrições, muito semelhante ao Campo Minado / Nonogramas; os números são colocados em uma grade que deve ser preenchida com valores ativados / desativados para cada célula, com cada número indicando uma região de células 'on' conectadas desse tamanho e algumas restrições menores na região das células 'off' ( deve estar conectado e não pode conter regiões 2x2 contíguas). A página da Wikipedia possui regras mais explícitas e exemplos de quebra-cabeças.

Genericamente, quebra-cabeças desse tipo tendem a ser NP-completos, e Nurikabe não é uma exceção; eles se enquadram no NP porque a solução em si serve como uma testemunha (polinomialmente verificável) do problema. Mas ao contrário da maioria puzzles semelhantes, os casos Nurikabe pode ser sucinto: Sudoku em um grade requer Θ ( n ) givens ser resolvidas (se menos de n - 1 Givens são oferecidos, então não há nenhuma maneira de distinguir entre os símbolos que faltam) , Os nonogramas obviamente exigem pelo menos um dado para cada linha ou coluna, e o Campo Minado deve ter dados em pelo menos $n\times n$$\Theta(n)$$n-1$ das células ou haverá células não próximas a uma determinada (e cujo status, portanto, não pode ser determinado). Mas enquanto os dados de um quebra-cabeça de Nurikabe precisam somarΘ(n2), é possível queO(1)dê cada um desse tamanho, para que osbits deΘ(log(n))sejam suficientes para especificar um quebra-cabeça de Nurikabe de tamanhon- ou invertendo,kbits pode ser suficiente para especificar uma instância Nurikabe de tamanho exponencial emk, o que significa que a única garantia é que o problema está no NEXP.$1\over16$$\Theta(n^2)$$\mathrm{O}(1)$$\Theta(\log(n))$$n$$k$$k$

Infelizmente, as provas da dureza de Nurikabe que encontrei usam construções com dados de tamanho constante, de modo que suas instâncias são polinomiais no tamanho da grade em vez de logarítmicas, e não posso descartar que todas as soluções solúveis sejam sucintas. Os quebra-cabeças de Nurikabe têm uma estrutura adicional, de forma que as soluções podem ser descritas e verificadas da mesma forma sucinta; por exemplo, o único exemplo que conheço de um quebra-cabeça com 2 dados de tamanho Θ ( n 2 ) leva a regiões de células ligadas e desligadas que são cada uma a união de O ( 1 $\Theta(n^2)$$\Theta(n^2)$$\mathrm{O}(1)$retângulos e, portanto, têm uma descrição sucinta própria. Alguém sabe de pesquisas adicionais que foram realizadas nesse quebra-cabeça além do resultado básico da completude do PN e, em particular, de outros resultados de complexidade para os casos possivelmente sucintos?

(observação: isso foi perguntado originalmente em math.SE , mas ainda não há respostas lá e isso parece o nível de pesquisa adequado para este site)

Você parece estar realmente perguntando: Nurikabe está em NP?

Nurikabe é difícil para o NP, pois é possível criar gadgets de tamanho polinomial que podem ser usados ​​para reduzir um problema de NP completo a um problema de decisão do Nurikabe. É isso que Holzer, Klein e Kutrib fazem, e também McPhail e Fix em seu pôster (ambos referenciados no artigo da Wikipedia).

Ambos os grupos de autores assumem que o problema é trivial em NP e afastam a questão da associação. Seu desconforto com instâncias sucintas parece evidente - não acredito que o problema esteja em NP. Considere a seguinte maneira de formalizar o problema de decisão:

Entrada BINARY NURIKABE : números inteiros m e n em binários , representando uma placa de Nurikabe e uma lista de triplos, cada um indicando uma posição na placa e um número inteiro positivo escrito nessa posição.
Pergunta: as posições restantes do tabuleiro podem ser coloridas com duas cores, respeitando as restrições de Nurikabe?

$m$$n$$mn$

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

Sua pergunta se torna: existem certificados de tamanho polinomial para todas as instâncias binárias do Nurikabe, que podem ser verificadas em tempo polinomial?

Não é óbvio para mim que tais certificados existam necessariamente. Também não é óbvio como alguém provaria que certificados sucintos e rapidamente verificáveis ​​não podem existir.

No entanto, a restrição a soluções exclusivas significa que o problema é realmente norte-americano , tão difícil de co-NP e, portanto, improvável que esteja no NP. O ponto é que, se considerarmos "ter uma solução única" como uma restrição de Nurikabe (em oposição a um recurso desejável de instâncias que são apresentadas aos seres humanos), então não é suficiente demonstrar que existe uma solução, mas é preciso também demonstrar que nenhuma outra solução é possível. Somente esse requisito é suficiente para garantir que o problema provavelmente não esteja no NP. Isso é verdade mesmo para a versão unária do problema.

Em resumo: se alguém relaxa o requisito de soluções exclusivas e especifica o tamanho da placa em unário, o problema da decisão está no NP; com soluções não exclusivas e tamanho de placa binária, não está claro se o problema de decisão está no NP; e com soluções exclusivas, o problema de decisão é difícil para os EUA e, portanto, improvável que esteja no NP, para qualquer codificação do tamanho da placa.