# 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