Go Back   Flash Flash Revolution > General Discussion > Critical Thinking
Register FAQ Community Calendar Today's Posts Search

 
 
Thread Tools Display Modes
Prev Previous Post   Next Post Next
Old 12-14-2006, 05:57 PM   #1
Tps222
FFR Player
 
Tps222's Avatar
 
Join Date: Nov 2004
Age: 35
Posts: 6,168
Send a message via AIM to Tps222 Send a message via Yahoo to Tps222 Send a message via Skype™ to Tps222
Default Impossible Math Question?

Quote:
Originally Posted by www.minesweeper.com who took it from some other site
If you want a million dollars, the Clay Mathematics Institute is offering such to anyone who can
solve Minesweeper efficiently. Unfortunately, this is much harder than simply finishing a game.

Richard Kaye, of Birmingham University, proved that Minesweeper is an NP-complete problem.
If one NP-complete problem can be solved efficiently then all can be solved. Most mathematicians
do not believe this is possible. If you prove this to be the case you will also win the money.

P problems can be solved in polynomial time: when you increase the number of choices, the
solving time increases by a determined power. The goal is to prove P=NP.

A famous NP problem is a travelling salesman who must find the shortest route to visit several
cities. Simple at first, but the number of potential routes and the time to analyse them increases
drastically! After only 10 cities there are 3628800 routes to analyse. After 100 cities your
algorithm must scan 9.3 x 10157 possible routes. This is greater than the number of atoms in the
universe: the military uses NP codes because you will not live to find the solution!

However, if you could write a Minesweeper solver where the calculations, thus time, only
increased by a power, you would have created a very efficient solver.

Interestingly, this may still mean some problems will not be solveable in your lifetime. Yet, it
also means military codes can be cracked and you could earn a lot more than a million dollars!
I'm not in a high enough math to even attempt to think of the solution, but I know a lot of you are great at it. To me, it seems quite impossible and pointless, but if want to give it a go, I'd like to see your train of thought. Note:I realize many of the world's greatest mathematicians say there isn't a solution.

Last edited by Tps222; 12-14-2006 at 05:59 PM..
Tps222 is offline   Reply With Quote
 


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump



All times are GMT -5. The time now is 07:46 AM.


Powered by vBulletin® Version 3.8.1
Copyright ©2000 - 2026, Jelsoft Enterprises Ltd.
Copyright FlashFlashRevolution