Qual é a complexidade do Nurikabe (possivelmente sucinto)?

11

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 1n×nΘ(n)n1 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.116Θ(n2)O(1)Θ(log(n))nkk

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 )Θ(n2)Θ(n2)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)

Steven Stadnicki
fonte
Stadnick: talvez você possa esclarecer sua pergunta à luz da resposta abaixo ou aceitar a resposta? (Também: obrigado por postar isso, pensando na pergunta me ajudou a entender a minha inquietação sobre problemas de decisão com base em quebra-cabeças.)
András Salamon

Respostas:

6

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?

mnmn

(m2)(n2)m×nmn1Θ(logm+logn)

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.

András Salamon
fonte