Este documento http://www.mountainvistasoft.com/docs/BattleshipsAsDecidabilityProblem.pdf diz que o problema de decisão "Dado um quebra-cabeça específico, existe uma solução?" é NP-completo. Não entendo por que isso não pode ser feito em tempo polinomial. Dadas as restrições de que dois navios não podem ser ortogonais ou diagonalmente adjacentes, por que não criar uma grade com duas vezes mais colunas do que "caixas" com linhas suficientes para colocar um "separador" entre cada navio. Vi a redução demonstrada dessa maneira e parece que isso poderia ser feito em tempo polinomial.
np-complete
np-hard
Derek
fonte
fonte
Respostas:
Como Andreas T menciona, o que você está perdendo é que a grade faz parte da instância.
A instância especifica a grade e os navios.
Por que o quebra-cabeça do Battleship não pode ser resolvido em tempo polinomial? Esta é a pergunta de um milhão de dólares (literalmente). Mas como o artigo que você menciona prova que o Battleship é NP-completo, a conjectura amplamente aceita P ≠ NP implica que o Battleship não pode ser resolvido em tempo polinomial.
O artigo continua provando que o encouraçado não pode ser resolvido em tempo polinomial, mesmo quando a solução é única, a menos que NP = RP, que também é considerado improvável. Esta é uma versão mais realista do problema, pois, na prática, os problemas dos navios de guerra têm uma solução única.
fonte