BATTLESHIPS AS A DECISION PROBLEM

Article type: Research Article

Authors: Sevenster, Merlijn¹

Affiliations: Amsterdam, The Netherlands

Note: [1] ILLC, Universiteit van Amsterdam, 1018 TV Amsterdam, The Netherlands. Email: sevenstr@science.uva.nl.

Abstract: We define the well-known puzzle of Battleships as a decision problem and prove it to be NP-complete, by means of a parsimonious reduction. By applying Valiant and Vazirani’s (1986) result we immediately obtain that the variant of this problem, viz. promising that there is a unique solution, is NP-complete as well, under randomized reductions. As this finding is in sheer contrast with the general experience of Battleship puzzles being well playable (i.e., effectively solvable), we arrive at a hypothetical explanation for this state of affairs.

DOI: 10.3233/ICG-2004-27303

Journal: ICGA Journal, vol. 27, no. 3, pp. 142-149, 2004