Karachi   ->   Sweden   ->   Karachi, again   ->   Dubai   ->   Bahrain   ->   Karachi, once more   ->   London and Leeds

Tuesday, February 08, 2005

Minesweeper is NP-Complete

Surprising but it's true that Minesweeper is NP Complete. If you remember the definitions from your Algorithms/ Complexity Theory course, to prove that a problem X is NP-Complete you need to reduce a well-known NP-Complete problem (usually satisfiability problem) to X in polynomial time. Solving any NP-Complete problem in polynomial time means that all Non Polynomial time problems would be solved.

And if you can't recall what NP was, let me remind you that problems which require exhaustive analysis of all possibilities to find the best solution are Non Polynomial time. And if you are as dumb as me you will need an example to understand this: Suppose you want to check if a string A is a substring of B and assume that the only possible method is to generate all possible substrings of B and match A against each one of them, then string matching would have been an NP problem.

Some Sokoban addicts seem to be interested in proving that their game is even more complex.

With this comes the "Is P=NP?" question. It's one of the Millennium Questions; there is $1 million award for the person who answers it with mathematical precision.

To this day, I fail to comprehend the difference between NP Complete and NP Hard. Also, some problems are said to be NP Complete in the strong sense. Can any enlightened reader shed some light?

Today, we have CHARM day at Chalmers. The industry comes to interact with the students. After many days of inactivity, once again, I am starting exercise and better time management from today.

No comments:

Post a Comment