Another Millennium Math Prize Problem Solved


#1

P != NP

Anybody know how this could affect the real world?

At least it wasn’t another insane russian mushroom picking idiot savante who solved it.


#2

That is the one to get solved? Get ready for for some crazy computing.

P versus NP problem - Wikipedia, the free encyclopedia


#3

yeah, it’s a 100 page proof, but it was published online already so people can try to take a crack at it. It will obviously take a fucking long time to verify it.


#4

Another one got solved? I haven’t actually looked at these problems but they’re aparently cake. I might just solve one of these things next week and get these student loans off my plate.


#5

holy shit this is big news

the cliff notes summary is that difficult problems that we suspected take a long ass time to solve actually do indeed take a long ass time to solve. so programmers can now stop wasting time trying to come up with a more efficient algorithm.

for example, the travelling salesman problem
Travelling salesman problem - Wikipedia, the free encyclopedia

edit:
btw, tons of people submit proofs for this all the time (award is a million dollars i think) but majority are bogus. so until its verified this isn’t newsworthy


#6

cool how many jobs will this technological advance cost us


#7

Not really. Big news would be proving P = NP.


#8

If the proof is legit, it is big news, because researchers have been trying to crack this one for a long time. Yes it’d be nice if P=NP, because that means we could solve a lot of the NP problems quickly, but oh well.


#9

What. I never thought this would be solved.


#10

What do you have against the Russian mushroom picking mathematician community?


#11

Looking forward to see if it pans out.


#12

Maybe it’s just me, but I still don’t see the significance behind this. Can someone explain this to me in LAYMAN’S terms. I’m not the brightest kid in the class; but that doesn’t mean that I can’t appreciate something for what it’s worth. The Travelling Sales Man problem doesn’t help either, because that’s hard to understand to begin with. WHY the hell weren’t I born smart enough (or why can’t I use my brain) to solve these problems or think of them to begin with. Ugh.


#13

i’m gonna read it.


#14

Interesting stuff, I remember my math teacher mentioning the Millenium Prize Problems


#15

Google to the rescue:


#16

From what I gather, this solution tells whether a problem is solvable in a reasonable amount of time or not. So researchers can now spend time solving problems that can be solved in a shorter time span versus ones that cannot. Their are implications on whether P = NP or P /= NP. We want P = NP because that means we can solve problems in a reasonable amount of time, or something like that.


#17

close

so here is what i posted in layman’s terms

and here’s the article you posted:

So its not that researchers aren’t going to try and solve these difficult NP problems. These problems still need to be solved, and there are some optimizations that can be done. Think of it this way. Lets say a typical NP problem took a computer an entire week of computation to solve. If P=NP, that means there exists an algorithm that would allow the computer to calculate the solution in seconds. If P is not NP, then there is no such efficient algorithm. HOWEVER, even if P is not NP, there are certain tricks that can be done to optimize the algorithm such that 30-40% of the time (based on certain special conditions), the computer can come up with a solution in a few seconds. Its still worth finding those kind of optimizations. But what this discovery buys us, is that researchers aren’t going to waste time trying to find an algorithm that would run in a few seconds 100% of the time - it does not exist. They’ll just look for optimizations in the special cases only.

Hope that helps.


#18

Yes, Elder God is right. If you have a proof for P = NP, then we can dream of having super fast computers and ALL of the other Millenium problems solved. The solution to this would be in the proof. However, this guy is providing a proof for P != NP. This says that we should stop wasting our time trying to solve hard problems thay may chew up a considerable time trying to solve. This DOES NOT mean that the problem is unsolvable however, and in fact many NP class problems are relatively simple to solve (or something like that).
It is also implied by some that a world where P = NP would be boring…

That’s it, i’m done with this thread. A nugget I did find during all of this is the MIT EXPLAINED Series which tries to take complex questions and provide layman term explanations. Thanks to the OP for posting this. Now back to SC2.

Also, thanks for the clarification fishjie. Now this stupid boy (me) can appreciate this proof or what exactly it means.