Impossible Math Question?

[Tps222]

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.

[Kilgamayan]

You want FFR to solve the P=NP problem? Why not ask us to prove the Riemann Hypothesis while you're at it? >_>

[Tps222]

I already said I don't know what it is. I also said I realize that mathematicians globally can't solve it. I was just wondering your thoughts on it.

[Kilgamayan]

My thoughts are that it (along with the other six Clay Millennium Problems) aren't worth my time because they're all too far over my head, and $1mil isn't nearly enough to compensate for all the aggravation one would need to put into solving one.

[Doug31]

It's impossible. I've set it up so that almost the entire thing was mines, and I got the number 8 to appear after the first place I clicked. gg, unless you get really lucky with another guess.

[Wilkin]

The game determines where the mines are at the first click. Then you can never immediately lose.

[Tokzic]

I tried one of the Clay million dollar problems - the one about finding a pattern between prime numbers, I think it was?

In any case I jotted out like ten pages before saying, "Hell with this."

[Kains_Avenger_Killer]

Just help him, it sounds confusing. When did FFR=Math?

[spyke252]

Eh.
It seems CompSci would help a lot as well.
But anyways.
Eh.

[Reach]

Ah, P=NP

Firstly, noone has even shown that it is possible or impossible to solve (in polynomial time). So, it seems wasteful that one might spend time on it if it isn't actually solvable. P might not = NP. Though, if you could prove P didn't equal NP you could probably get the prize as well.


You're going to have to develop a new algorithm in order to solve it. No current method gives any type of real solution. It requires the use of superpolynomial time (imperfect solution).

[Tasselfoot]

lol... the math genius in Numb3rs spends some of his free time in a few of the season 1 episodes trying to solve P=NP and can't.

[Vests]

Anything can be solved at some point, just takes a lot of work . Hell we have thousands of computers working on finding a end to Pi, why not start a endless calculation string on this equation?

[8Shade8]

If this is possible to solve, then there is only one person in the universe who can solve it without a computer:
Steven Hawkins

I suggest that you write him a letter, have one of his nursing home people wipe the drool off of it every five seconds and have him solve the problem. If there is anyone in the world who can solve it he can.

N=NP

This calculation can work if N=2 and P=1. LOL. It also works if all of the variables are denoted as zero. Actually, it will always work if P=1. LOL whatever.
I am a huge mathmatics person, and I also used to watch numbers. If they cant solve it even as actors, then screw that, I wont even try. I was in Calc 2 before I left texas (I am now going to the army to interrogat people) and I cant even come close to understanding the complex concept behind that calculation.

[8Shade8]

They offer a million dollars knowing that it is an unanswered question. Thats like asking the FFR community (with a million dollars at steak) what came first the chicken or the egg. It can't be answered without some huge debate. We would need a few super computers to run that, and FFR's server couldn't cut it. LOL.

[Tasselfoot]

1. don't double post.
2. this is CT... don't be stupid. Steven HawkinG is a physicist, not a mathematician.
3. your absolutely basic grasp of the concept is not helpful towards any kind of discussion
4. That's. stake. which. interrogate. mathematics. etc, etc, etc...

[Tps222]

I'm unsure of the "him" some of you are referring to in regards of helping "him" solve it. What I was looking for was something similar to Reach's explanation of what it is and why it hasn't been solved. I really don't care if it can be solved or not, because it's way over my head.

[Billydude]

hmm... I dont really even understand the question. What is P and N and NP? And I dont know how to play minesweeper. lol. Try translating it in a B+ kind of guy term.

[Reach]

Well alright, since most people don't understand what P=NP is, I'll explain it.

It has to do with computer type algorithms and how computers solve problems. P is essentially talking about positive solutions, more specifically ones that can be solved quickly in polynomial time, and the answer has to be Yes or no (non yes and no answers are reffered to as FP=FNP). NP is essentially saying that, if P is true, then they can also be computed quickly (by computer algorithms) in polynomial time.

I suppose to understand this you would have to imagine a problem which the solution is obvious, but that would be very hard to compute a perfect proof of it. So, imagine a group of numbers of some size, all integers. Could they add up to zero? Of course, the answer is yes, however, it could take a computer a very long time to prove this is possible, depending on the size of the group.

So a proof of P=NP would say any positive yes or no solution to a problem would say that it is also possible to compute this quickly in polynomial time. So if I say, it is possible to crack a military cryptogram(the answer is yes), if P=NP is true then it should also be possible to compute this and crack the password in polynomial time.

It does get considerably more complex, but most of the problem is in NP. Yes or no solutions are easy, but an NP solution in polynomial time is not. Noone has been able to find an algorithm that is able to do this.

However, that doesn't mean it's impossible. It is most likely very much a possibility, but people like to say it's impossible because...well, mostly because we havn't made any progress on it. That doesn't prove anything though, other than that we arn't smart enough to do it.



A proof of P=NP, in my opinion, is worth far more than a million dollars. If it was proved things would change very quickly. The consequences of such an algorithm would change the computational world quite a bit. Imagine how easy it would be to crack a code, for example in cryptography. Password key safety would immediately become an enormous problem...because anyone would bea ble to crack your key. However, the benefits would outweigh that negative aspect

[RandomPscho]

Thank you for the explanation Reach

[RB_Dreamscanner]

wow reach dats a..weird avatar u got there and i dont under stand how the he;ll u did thta math problem =/