«

»

Nov 16

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)

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>