Way OT- P/=Np proof!
A scientist at HP Labs has come forward with his proof of the P=NP / P/=NP mystery. Not only would this score him a million bucks, it would also pretty much lock him into the great modern math minds club. Question for my fellow CS/Math nerds: do you think this is really possible?
http://www.livemint.com/2010/08/10230113/Indian-scientist-offers-proof.html?h=B
August 10th, 2010 at 4:18 PM ^
probably not gonna happen. see lipton's blog for details:
August 10th, 2010 at 4:24 PM ^
but when I read that, I feel like I see the proof myself.
Given any multivariable equation and told to find for the variables, you have to take a long time taking it apart to find each variable. Ergo, P. But once you have found them all, all you have to do is put them all into the first equation and solve it once. If it works, it's gold. NP.
I'm sure what I've just come up with is NOT a good proof at all, but I'm not sure why not.
August 10th, 2010 at 4:35 PM ^
The issue comes up with multivariable exponential problems especially when the solution is irrational.
August 10th, 2010 at 4:43 PM ^
So now that he has proven it does this mean that he can no longer verify it?
August 10th, 2010 at 5:09 PM ^
Any verfication will be, at best, three FAKES out of five.
August 10th, 2010 at 4:33 PM ^
Aren't there like 7 of them or something? I remember one was solved a few years back by some guy that went crazy and refused the reward money. Something about proving a donut couldn't become a sphere without ripping the surface.
August 10th, 2010 at 4:37 PM ^
yep, the Poincare conjecture. Every simple connected 3-fold manifold is homeomorphic to the 3-sphere.
August 10th, 2010 at 4:46 PM ^
Is that the only one that has been solved so far?
August 10th, 2010 at 4:47 PM ^
yes; this would be the second if it's found to be correct.
August 10th, 2010 at 5:47 PM ^
Not if you believe Louis de Branges.
August 10th, 2010 at 7:07 PM ^
By the way, Perelman's solution is awesome. The use of Ricci Flow - although it wasn't initially his idea - is a really cool idea. I've often wondered if there are other problems that might benefit from such a smoothing/transforming technique.
August 10th, 2010 at 4:50 PM ^
Or the Clay prizes ...depending on your perspective.
-The topic at hand
-Hodge conjecture
-Yang/Mills ex/mass gap
-Naviar/Stokes existance/ smoothness
-Poincare
-Rieman Hypothesis
-Birch Swinnerton/Dyer conjecture
And anyone who has the capacity to solve these conundrums is surely teetering on the brink on insanity.
August 10th, 2010 at 5:18 PM ^
Yesterday's practice actually solved half of the Navier/Stokes Existence and Smoothness problem:
At :42, you can see that Je'Ron Stokes exists, and that he clearly exhibits smoothness.
August 10th, 2010 at 5:38 PM ^
It is my goal as a physicist to solve Rieman's hypothesis.
August 10th, 2010 at 8:31 PM ^
Just thinking about Riemann's Hypothesis hurts my head.
August 10th, 2010 at 10:55 PM ^
And I was laid humble. The most accurate way to describe my response there is, "WTS?!?"
August 10th, 2010 at 4:54 PM ^
he was eccentric and refused the money because...
He didn't deserve it, he told a Russian news service, because he was following a mathematical path set by another.
unfortunately seems like the type that until he comes up with a unique idea will never consider himself a success
August 10th, 2010 at 4:43 PM ^
N=1
ok next problem
August 10th, 2010 at 4:45 PM ^
run along, let the big boys play with their toys.
August 10th, 2010 at 4:45 PM ^
Gesundheit?
August 10th, 2010 at 4:46 PM ^
1) I love that this has come up on MGoBlog.
2) I'm bewildered that it's posted by an OSU fan. Surely this is a sign of a coming apocalypse.
August 10th, 2010 at 4:55 PM ^
but after careful deliberation, I rightly decided this particular discussion would fare better with this community.
I knew this would at least make a few of you question possible impending doom.
August 10th, 2010 at 7:42 PM ^
(P=NP) / P / (= NP)
When does P (Pryor) = NP (Not Pryor)?
Well when you take this starting equation and divide by Pryor and then, you divide something that is Not Pryor. The result is if "Not Pryor" is infinitely better then Pryor, you get P / infinity which make the probability of P = NP = Zero.
QED, NP must = Dilithium.
August 10th, 2010 at 4:49 PM ^
Thanks for making me feel like some mouth breather...
August 10th, 2010 at 4:50 PM ^
Now, see if this guy can confirm whether 3-3-5=4-2-5
August 10th, 2010 at 4:54 PM ^
I'm more interested in the follow up proof where 3-3-5=4-2-5=13-0
August 10th, 2010 at 5:13 PM ^
If we switch to a 2-5-4 this season, I will bodly predict 7 wins:
2 - 5 - 4 = -7 losses (2010?)
3 - 3 - 5 = -5 losses (2009)
4 - 2 - 5 = -3 losses (2008)
though I'm really pulling for a 1-6-4.
August 10th, 2010 at 4:53 PM ^
I tried really hard to understand wtf was going on in that article but failed miserably. Always wanted to be able to do high level math but never could. Much credit to anyone who can understand this stuff, much less the guy who tried to solve it. Like was said above, I love the fact that this is on MGoBlog, despite the fact that it makes me feel like an idiot...
August 10th, 2010 at 5:02 PM ^
P/=Np isn't just a confusing emoticon?
That's a relief. Well... back to eating paint!
August 10th, 2010 at 5:04 PM ^
we'll let the big boys pore over the proof and decide whether it is rigorous and complete enough. I am guessing it will probably take a year or two, interspersed with the author reworking stuff, before the mathematical community decides one way or the other. Anything that requires 100 pages of arcane math to prove will take a while to be digested.
August 10th, 2010 at 5:19 PM ^
I don't think it'll take a year or two. It's caused a lot of excitement in the CS world that someone has purported to solve it, but it's mainly skepticism. I like the response from MIT CS prof and blogger Scott Aaronson: http://www.technologyreview.com/blog/post.aspx?bid=349&bpid=25584
In fact, I could think of only one mechanism to communicate my hunch about Deolalikar’s paper in a way that everyone would agree is (more than) fair to him, without having to invest the hard work to back my hunch up. And thus I hereby announce the following offer:
If Vinay Deolalikar is awarded the $1,000,000 Clay Millennium Prize for his proof of P≠NP, then I, Scott Aaronson, will personally supplement his prize by the amount of $200,000.
August 10th, 2010 at 5:29 PM ^
August 10th, 2010 at 6:00 PM ^
Plus, the original statement doesn't make very much sense, because there would still be a very large creative gap between recognizing that polynomial-time algorithms exist for solving a problem, and actually finding the polynomial time algorithm (and perhaps even then, improving the algorithm/waiting for better technology to develop to be able to implement said algorithm).
It sort of reminds of a problem from coding theory (I forget exactly which one), where you can show there exists an algorithm with a certain running time because the average over all possible algorithms is less than it, yet it's still a challenge to come up with even one such algorithm.
Also somewhat related is the recently solved problem of "God's Number", which asserted that a Rubik's cube in any position can be solved in at most 20 moves. There's millions of positions that take the full 20 moves to solve, yet they compose only a minuscule fraction of all possible Rubik's cube positions.
August 11th, 2010 at 8:40 AM ^
True, but in the unlikely event that P=NP, it's pretty likely that someone proves that by giving a polynomial-time algorithm to solve an NP-complete problem (certainly not guaranteed that's how it would be proved but it's decently likely). And once you've solved one, you've solved them all, so you're golden.
August 10th, 2010 at 6:04 PM ^
Aaronson is just taking his default position w/r/t this problem. He's been in Europe for a week and hasn't seriously read the paper. Terrence Tao, on Dick Lipton's blog, has pointed out there are counterexamples to a few of the refutations that give Deolalikar some wiggle room. This is a tough scenario for the Internet crowd to get a feel about; the closest example is Andrew Wiles publishing a solution to Fermat's Last Theorem, being told it was wrong, then taking nearly a year to fix it.
August 10th, 2010 at 8:24 PM ^
Oh the irony of taking 40 years to "prove" and 2 years to verify NP vs P.
August 10th, 2010 at 5:30 PM ^
I always had a lot of respect for mathematicians like that since being enrolled in Honors Math I as a freshman (basically intro to analysis and developing calculus with proofs). The amount of creativity required to create new proofs like this is enormous and goes unappreciated by people that haven't taken theoretical math.
Also, classes Protip: Honors Math 1 (MTH295) is one of the few (possibly the only) classes on campus that is so hard that if you fail it they give you an A- for effort and kindly ask you to leave the pantheon of nerddom in East Hall for all time. I know this first hand.
August 10th, 2010 at 6:02 PM ^
To make a poor joke relating to the topic at hand, things get exponentially worse as you move on in the sequence.
August 10th, 2010 at 6:27 PM ^
I promise you this sort of thing is not being discussed on little brother's blogs. They are still deciphering what Chris L. Rucker ate last season to make his poo turn that 'funny color' in the locker room toilet.
August 10th, 2010 at 8:00 PM ^
It was definitely paint.
August 10th, 2010 at 8:02 PM ^
I do not profess to know much about this proof, but it does sound like there are some holes that will need to be filled before it will even be seriously considered as a proof. It does sound, though, like this is a novel approach to P = NP, and my sense is that even if the proof is ultimately found to be incorrect, pieces of it will be salvaged and probably utilized in an upcoming attempt.
August 10th, 2010 at 9:30 PM ^
Even if it's wrong, it's closer than anyone's gotten before and likely to be at least a good starting point.
August 10th, 2010 at 8:37 PM ^
NERDS!
