In diesem Artikel http://www.mountainvistasoft.com/docs/BattleshipsAsDecidabilityProblem.pdf heißt es, dass das Entscheidungsproblem "Gibt es bei einem bestimmten Rätsel eine Lösung?" ist NP-vollständig. Ich verstehe nicht, warum dies nicht in Polynomzeit möglich ist. Angesichts der Einschränkungen, dass keine zwei Schiffe orthogonal oder diagonal benachbart sein können, können Sie einfach ein Raster erstellen, in dem doppelt so viele Spalten wie "Behälter" vorhanden sind und genügend Zeilen vorhanden sind, um zwischen jedem Schiff einen "Trenner" einzufügen. Ich habe gesehen, wie die Reduktion auf diese Weise demonstriert wurde, und es scheint, als könnte sie in Polynomzeit durchgeführt werden.
np-complete
np-hard
Derek
quelle
quelle
Antworten:
Wie Andreas T erwähnt, fehlt Ihnen, dass das Raster Teil der Instanz ist.
Die Instanz gibt sowohl das Raster als auch die Schiffe an.
Warum kann das Schlachtschiff-Rätsel nicht in Polynomzeit gelöst werden? Dies ist die 1-Millionen-Dollar-Frage (im wahrsten Sinne des Wortes). Da das von Ihnen erwähnte Papier jedoch beweist, dass das Schlachtschiff NP-vollständig ist, impliziert die weit verbreitete Vermutung P ≠ NP, dass das Schlachtschiff nicht in polynomieller Zeit gelöst werden kann.
Das Papier beweist weiterhin, dass das Schlachtschiff nicht in Polynomzeit gelöst werden kann, selbst wenn die Lösung eindeutig ist, es sei denn, NP = RP, was ebenfalls als unwahrscheinlich angesehen wird. Dies ist eine realistischere Version des Problems, da Schlachtschiffprobleme in der Praxis eine einzigartige Lösung haben.
quelle