(This is based on my earlier MSE question that has been stagnant for just over a week, since the
best answer only addresses the case of two mines and does not even completely resolve that.)

What is the computational complexity of playing 1-dimensional Minesweeper in a way that
maximizes the probability of winning, where the board length is given in unary, the number
of mines is known, and their position is chosen uniformly from among all possibilities?

I believe the reasoning used in the proof of $\:$IP $\subseteq$ PSPACE
shows that the complexity is at most PSPACE.

  • 2
    $\begingroup$ Don't cross-post. $\endgroup$ – Dukeling Mar 13 '14 at 0:07
  • $\begingroup$ Given an oracle for SAT, you can estimate the fraction of positions where there is a mine in position $i$. This doesn't solve the full problem, though (it's enough to choose a move that is approximately locally optimal, but I don't know how to choose the global optimum). Comment: Are you sure you're asking for the exact optimum, or would approximately optimal play be sufficient? I suspect the latter might be easier. $\endgroup$ – D.W. Mar 13 '14 at 0:18
  • $\begingroup$ @Dukeling : $\;\;\;\;$ Huh. $\;\;$ Is the $\:$math.SE $\rightarrow$ mathoverflow$\:$ route mostly shut down or an exception? $\hspace{.47 in}$ $\endgroup$ – user12859 Mar 13 '14 at 0:22
  • $\begingroup$ I don't know about MO (they may be a special case; you'd have to ask them on their Meta). In general, it's fine to flag your post and ask it to be migrated, but as far as I know cross-posting is almost always verboten. That said, you might be able to make an argument that this question isn't a cross-post, because this question asks for the computational complexity and your MSE question asks for a simple strategy. If that's your intent, you might want to edit this question to link to the MSE question and give the explanation how this differs. $\endgroup$ – D.W. Mar 13 '14 at 0:32
  • 2
    $\begingroup$ While crossposts after a waiting period can be okay, please make sure to relate to what you have learned from the question on Mathematics. What is missing from the answers? $\endgroup$ – Raphael Mar 13 '14 at 1:43