How the Web Rallied To Review the P != NP Claim 160
An anonymous reader writes "Remember, about a month ago, when a researcher claimed he had a proof that P != NP? Well, the proof hasn't held up. But blogs and news sites helped spur a massive, open, collaborative effort on the Internet to understand the paper and to see if its ideas could be extended. This article explains what happened, how the proof was supposed to work, and why it failed."
Damn... (Score:5, Funny)
Step #1: Wait for him to prove and confirm P!=NP
Step #2: Solve for N:
So P!=NP,
therefore P!/P=N,
thus the Ps cancel and we are left with N=!.
Step #3: ???
Step #4: Profit!
Re:Nerd Superbowl (Score:4, Funny)
I think Mr. Venkatasubramanian is just overgeneralizing from his personal experience. No one interacts with him at conferences because they can't pronounce his name.
OT: sig comment (Score:5, Funny)
People replying to my sig annoy me. That's why I change it all the time.
Time to change again.
Re:Nerd Superbowl (Score:4, Funny)
Yeah. It'd be easier and cooler if he shortened it to Venkman [wikipedia.org].
Re:Damn... (Score:1, Funny)
My thoughts exactly.
Obvious or oblivious? (Score:3, Funny)
It is the greatest question in computer science. A negative answer would likely give a fundamentally deeper understanding of the nature of computation. And a positive answer would transform our world: Computers would acquire mind-boggling powers such as near-perfect translation, speech recognition and object identification; the hardest questions in mathematics would melt like butter under computation’s power; and current computer security methods would be as easy to crack as a TSA-approved suitcase lock.
Proof that P!=NP: We haven't made any really hard problems really easy. If P=NP, then computers automatically acquire mind-boggling powers and the ability to crack encryption. Presumably that would have already happened if P=NP, therefor P!=NP. QED.
Re:Nerd Superbowl (Score:5, Funny)
Yeah, but nobody scored...
Re:So... we disproved P != NP (Score:5, Funny)
P!=NP
(P-1)! * P=NP
N=(P-1)!
Re:So... we disproved P != NP (Score:3, Funny)
Re:To summarize where the proof went wrong... (Score:3, Funny)
Re:maybe not proven, but seems obvious (Score:3, Funny)
You will pay a million bucks for code that doesn't work correctly? shit, if I work for you I would have all the money in the world!
Re:To summarize where the proof went wrong... (Score:5, Funny)
So for example if one was looking at 3-SAT "(A v B v ~ C) ^ (A v A v ~D)" would be a valid example. Now, it happens that for k>2, k-SAT is NP-complete.
Oh, that explains it.
Re:To summarize where the proof went wrong... (Score:5, Funny)
Math is hard, but some types of math are really hard.
Re:To summarize where the proof went wrong... (Score:3, Funny)
Re:Nerd Superbowl (Score:3, Funny)
There's an extraneous word in your post.
“It was like the Nerd Superbowl."
Yeah, nobody scored.
QED
Re:Ah, but what if it had held up??? (Score:3, Funny)
If it had held up, someone would have already set about producing a computing system that was capable of constructing all proofs and all complex structures of everything, and formatting and submitting them as patents.
Many of these would be business models and means of winning elections regardless of public opinion.
Within a few years, our legislative and economic systems would be taken over by the people operating the machine, and they would change the law and, legally, make us their slaves.
You might say I'm rather relieved that P != NP.
Re:Pi, what a waste of time (Score:3, Funny)