# Grover's algorithm and Battleship solution

I have read that quantum computers are not known to be able to solve NP-complete problems in polynomial time. However, if you consider a game of Battleship with grid size $$X, Y$$ and represent this by a binary string $$01100\cdots$$ of size $$X \times Y$$ where the $$1$$s represents ship locations, wouldn't Grover's algorithm be able to solve this in $$\mathcal{O}(\sqrt{XY})$$?

Battleship is considered NP-complete. Why isn't this considered polynomial time?

• Can you include the reference where you read that? – cnada Mar 9 at 9:04
• You might want to double check the difference between the game played between 2 people and the decision problem (pdf link)/puzzle - in both, you want to find all the ships but while the former involves large amounts of guesswork, the latter is a very different problem where the solution can be found without guesswork – Mithrandir24601 Mar 9 at 9:07
• cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf – QCQCQC Mar 9 at 9:12
• @QCQCQC How's that PDF relevant? – Sanchayan Dutta Mar 9 at 9:40
• I was asked to provide reference to where I read that QCs are not known to be able to solve np-complete problems in polynomial time. Guess I replied to the wrong post. @Mithrandir24601 I will look into that article, thanks – QCQCQC Mar 9 at 10:29

I think you've simplified the problem too much. The way your question is framed it sounds like you expect a square-root speedup of a small problem, which doesn't seem that impressive. In actuality there may be a Grover-style speedup not of $$O(\sqrt{X Y})$$ but of $$O(\sqrt{2^X 2^Y})$$.
Let's let your opponent's battleship grid be of size $$X\times Y$$. It is populated with $$s\in\{0,1\}$$ binary numbers, where $$1$$ is "ship" and $$0$$ is "sea". Thus you can think of your opponent's grid as an element $$S$$ of $$\{0,1\}^{XY}$$.
The size of and placement of ships further constrains what $$S$$ can be; for example, there must be two consecutive $$1$$'s for a destroyer, four consecutive $$1$$'s for a battleship, etc.
Nonetheless your goal is to guess the location of all of your opponent's $$1$$'s with fewest number of guesses.
Thus, you are trying to determine $$S\in \{0,1\}^{XY}$$. When properly framed this can be a $$\mathsf{3SAT}$$ instance and Grover's algorithm can get the polynomial speedup of an exponential problem.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 19, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.7970789074897766, "perplexity": 594.9308910892423}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2019-26/segments/1560627998475.92/warc/CC-MAIN-20190617123027-20190617145027-00140.warc.gz"}