Mathematical games

[vvvexation]

No doubt at least a few of y'all will find this interesting: Apparently Minesweeper is NP-complete. Not only that, but you can use it to build logic gates.

Comments

[stollman.livejournal.com]

I must say the title of the article annoys me.

Minesweeper, the game as usually played, is not NP complete.

The "minesweeper consistency problem" is, apparently.

The two are entirely different beasts. When one plays minesweeper, one assumes that the game is internally consistent and that you won't have to solve the consistency problem; in fact if one encounters evidence that the game is NOT consistent, one usually stops playing in disgust.

Likewise, my [arbitrary problem that's provably NOT NP-complete] software runs on a computer that performs computations using the same underlying boolean logic elements. That doesn't make my software NP-complete, either.

[vvvexation.livejournal.com]

Point. I appear to have been outgeeked, or at least out-nitpicked.

[stollman.livejournal.com]

Revelation!

I appear to have been outgeeked, or at least out-nitpicked.

Thank you! I now realize that there are a large number of people who equate the two, to one degree or another, and I've been confused on a number of occasions because they do and I don't, and didn't know what I didn't know.

Ok, Captain Morgan probably has something to do with it, if that makes no sense.

[vvvexation.livejournal.com]

Yow. Come to think of it, I hadn't really thought to make the distinction in those terms myself till just now.

We are enlightened! Yay!