1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Minesweeper and P = NP

  1. Jun 24, 2008 #1
    Here is a great little article that talks about P=NP and the computer game that comes standard on most PCs with windows

    http://www.claymath.org/Popular_Lectures/Minesweeper/ [Broken]

    What do you think? Is minesweeper P or NP?
    Last edited by a moderator: May 3, 2017
  2. jcsd
  3. Jun 24, 2008 #2

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    The article doesn't talk about Minesweeper being NP. Showing what results when a user clicks on a Minesweeper square is easy -- and obviously in P.

    The article talks about the "Minesweeper Consistency Problem" being NP. This problem is one that Minesweeper itself doesn't play. Suppose the Minesweeper program was modified to lie. How would it be to determine whether the Minesweeper program had lied? This is the Minesweeper Consistency Problem.
  4. Jun 24, 2008 #3
    I don't think it's a matter of if Minesweeper is P or NP, but more of a question about WHY is it P or NP.

    Of course, if that were the case, I think it wouldn't be posted in here. :wink:
  5. Jun 24, 2008 #4

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    There should be no doubt that the Minesweeper Consistency Problem is NP; the article states this explicitly. The question, then, is whether this new problem helps determine whether or not P=NP. I doubt it. It might, however, help newbies understand the nature of the problem.
  6. Jun 24, 2008 #5
    So I don't know if this is what the Minesweeper Consistence Problem is, but

    Given a minesweeper board with some blank spaces, determining whether the blank spaces have an answer that can be found from the information given, the board is inconsistent, or the board has several possible solutions is an NP-Complete problem. My roommate actually had to prove this for one of his courses. The typical method of proof of that is reduction to 3-sat (which he tried to explain to me, but I couldn't figure out what he exactly it was)
  7. Jun 24, 2008 #6

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    That is exactly the Minesweeper Consistency Problem, and the approach taken by your roommate is exactly that taken in the article cited in the OP.

    The boolean satisfiability problem involves determining whether or not there exist assignments to variables in a boolean expression makes the expression true. For example, the expression [itex]x_1 \wedge x_2[/itex] is true if x1 and x2 are both true; this expression is satisfiable. On the other hand, [itex](x_1 \wedge \lnot x_1) \vee (x_2 \wedge \lnot x_2)[/itex] is false no matter what truth values one uses for x1 and x2; this expression is not satisfiable. Both of the expressions I gave as examples have two arguments in each clause. For example, [itex](x_1 \wedge \lnot x_1)[/itex] is an example of a clause with two arguments.

    The problem is a 2-satisfiability (2SAT) problem if every clause has exactly two arguments. The 2SAT problem is provably in P. The problem is a 3-satisfiability (3SAT) problem if every clause has exactly three arguments. The 3SAT problem cannot (as of date) be proven to be in P. It is provably in NP and even more importantly, is NP-complete.
  8. Jun 24, 2008 #7
    Learned something new today.
  9. Jun 27, 2008 #8
    Thanks, DH. Like Bryan, I also learned something new today. And interesting. And important (to me, anyway). It is such a simple and satisfying fact. One could say, "That'll teach!" -- i.e., that'd be a good example to use in a class. DJ
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Minesweeper and P = NP
  1. P vs NP (Replies: 15)

  2. P=np refuted (Replies: 3)

  3. P = np formula (Replies: 7)

  4. A proof for P vs NP (Replies: 8)

  5. P Versus NP Problem (Replies: 5)