November 16, 2007

Minesweeper is NP-Complete

The Traveling Salesman problem. The backpack problem. Public Key encryption. All examples of the NP-Complete family of algorithms - are they non-polynomial? Are they polynomial w/a really brilliant algorithm that we haven’t yet found? Nobody knows.

It turns out that humble Minesweeper is of the same family. The proof of this is absolutely brilliant.

Thus, every time you’ve solved a game of Minesweeper, you’ve solved an NP-Complete problem. Yay, wetware.

Having said this, since Quantum Computers can solve Public Key Encryption in Polynomial time, assume that they can solve Minesweeper in polynomial time too.

Next up: Sudoku is solved using the Riemann Hypothesis (heh)

No Comments »

No comments yet.

RSS feed for comments on this post. | TrackBack URI
You can also bookmark this on del.icio.us or check the cosmos

Leave a comment

XHTML ( You can use these tags): <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> .