Beta

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

How the Web Rallied To Review the P != NP Claim

Soulskill posted more than 3 years ago | from the peer-to-peer-review dept.

Math 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."

cancel ×

160 comments

Sorry! There are no comments related to the filter you selected.

CmdrTaco is hung like a toddler (-1, Troll)

Anonymous Coward | more than 3 years ago | (#33538056)

CmdrTaco's penis is so small that a toddler looks like Mandingo in comparison.

Another one bites the dust (0)

Anonymous Coward | more than 3 years ago | (#33538146)

He thought he'd get famous and rich overnight...but now he is the laughing stock of CS!!

Re:Another one bites the dust (1)

2.7182 (819680) | more than 3 years ago | (#33538216)

Well, the author hasn't been convinced by the crowd:

"Deolalikar hasn't withdrawn his article. He claims to have fixed the errors and will be submitting the revised article to a journal to go through an ordinary peer review process."

Re:Another one bites the dust (1)

HungryHobo (1314109) | more than 3 years ago | (#33538460)

If he was really interesting in making it accurate then he'd allow the public to see the revised paper and attempt to pick holes in it again.

unless of course he just cares more about not being proved wrong than being right.

Re:Another one bites the dust (1)

retchdog (1319261) | more than 3 years ago | (#33538572)

he's also interested in getting as much of the credit as possible. Clearly he thinks that he is using the best strategy of crowdsourcing vs. proprietary approach.

So... we disproved P != NP (0)

Anonymous Coward | more than 3 years ago | (#33538094)

And that means P = NP!

Right guys?

Right?

Re:So... we disproved P != NP (1)

mathmatt (851301) | more than 3 years ago | (#33538154)

I saw what you did there... Moving the "!" to the end...

Re:So... we disproved P != NP (2, Funny)

Evil Shabazz (937088) | more than 3 years ago | (#33539314)

I love peanots. Great source of protein.

My Kurt Reply: (1)

Jeremiah Cornelius (137) | more than 3 years ago | (#33539424)

You Sir, are a Gödeless troglodyte.

Loutish Word of the Day: "Diaeresis"

Re:So... we disproved P != NP (-1, Redundant)

Jorl17 (1716772) | more than 3 years ago | (#33538338)

I propose that C is proof of P
C is refuted as proof of P
Hence, P isn't true

FALSE! Think about it! We've disproved many theories which calimed to be proof of god's existance. But that doesn't mean we proved that god doesn't exist, unfortunately, for my atheist mind.

Re:So... we disproved P != NP (1)

icebraining (1313345) | more than 3 years ago | (#33539816)

No, but it does prove that you've been Whooshed!

Re:So... we disproved P != NP (-1, Offtopic)

Jorl17 (1716772) | more than 3 years ago | (#33540460)

Here's something interesting: I was modded down because I said that I don't believe in God. Say, who the FUCK DID THAT?

Re:So... we disproved P != NP (4, Funny)

Requiem18th (742389) | more than 3 years ago | (#33538936)

P!=NP
(P-1)! * P=NP
N=(P-1)!

Nerd Superbowl (4, Interesting)

mathmatt (851301) | more than 3 years ago | (#33538128)

This quote pretty much sums it up: “Even at a conference you don’t get this kind of interaction happening,” says Suresh Venkatasubramanian of the University of Utah. “It was like the Nerd Superbowl.”

Re:Nerd Superbowl (4, Funny)

Anonymous Coward | more than 3 years ago | (#33538180)

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.

Re:Nerd Superbowl (3, Funny)

game kid (805301) | more than 3 years ago | (#33538348)

Yeah. It'd be easier and cooler if he shortened it to Venkman [wikipedia.org] .

Re:Nerd Superbowl (1)

Kristopeit, M. D. (1892582) | more than 3 years ago | (#33538524)

what do you expect? someone was wrong on the internet.

WILL. NOT. STAND. FOR.

a real nerd wouldn't allow you to label such actions relative to organized sport, because letting an idiot know they are an idiot is not a game... it's a responsibility.

ObXKCD (0)

Anonymous Coward | more than 3 years ago | (#33538654)

Re:Nerd Superbowl (1)

IshmaelDS (981095) | more than 3 years ago | (#33538678)

Thanks for the new sig. :)

Re:Nerd Superbowl (5, Funny)

JamesP (688957) | more than 3 years ago | (#33538690)

Yeah, but nobody scored...

Re:Nerd Superbowl (0)

rla3rd (596810) | more than 3 years ago | (#33539004)

Just like having sex with the opposite gender.

Re:Nerd Superbowl (2, Funny)

blair1q (305137) | more than 3 years ago | (#33540828)

There's an extraneous word in your post.

“It was like the Nerd Superbowl."

Yeah, nobody scored.

QED

The greatest gift (5, Insightful)

Jedi Alec (258881) | more than 3 years ago | (#33538130)

No matter the flaws with his paper, this guy has certainly managed to inspire a whole lot of people to delve into a subject and collaborate on it.

Those who think deep thoughts are precious. Those who manage to inspire thousands of others to do so...

OT: sig comment (5, Funny)

beschra (1424727) | more than 3 years ago | (#33538208)

People replying to my sig annoy me. That's why I change it all the time.

Time to change again.

Obvious flaws (0)

Anonymous Coward | more than 3 years ago | (#33538280)

P = NP when N=1 or P=0

Geez! It can't be more obvious than that.

Re:The greatest gift (0)

Kristopeit, M. D. (1892582) | more than 3 years ago | (#33538544)

well let me tell you about my friend... he's a flying spaghetti monster, and he alone is responsible for us all.

lies and untruths are never precious.

Re:The greatest gift (0)

Anonymous Coward | more than 3 years ago | (#33539860)

I am not that sure this guy inspired anyone; his name is Vinay Deolalikar btw.

I read the hundreds of posts where discussions took place, and you could see many top notch researchers quite angry about the whole issue.

You have someone claiming that P != NP and of course, anyone with an interest will abandon their current projects to review the proof and the claim, thus diverting resources that would have been used in other research.

The main problem with the process is that this guy announced to the world that he had solved the fundamental problem without a proper peer-review from colleagues or a small group of experts; from the start after the announcement, many thought the paper was flawed, but of course, many people had to spend time to understand the 100+ pages and then show why it was flawed.

The good way would have been to share the paper with a small circle of colleagues and experts, so they evaluated it first; it would have not passed their filter, and the rest of the researches would have not spent their precious time on these.

So, I do not see how the whole thing is any good.

Re:The greatest gift (5, Informative)

phaunt (1079975) | more than 3 years ago | (#33540110)

That's exactly what he did. He mailed it to a small group of experts and asked them for their comments. Some of them sent it on, commenting: "hey, this looks like a legit attempt", and before Vinay knew it, his article was on the web.

Re:The greatest gift (0)

Anonymous Coward | more than 3 years ago | (#33540554)

If a nut-job claims he's created a theory combining the general theory of relativity with quantum theory, it is in no way "inspiring". If a semi capable mathmatician does the same, it still isn't inspirering.

He shot and missed, theres no reason to praise him, he just goes on the list of other failed attempts. The fact that he was swarmed by others picking his attempt apart is just due to the media attention. If the media hadn't cried proof before anyone had looked at the paper, then no one would have cared when in a cuple of months it comes out being just "a novel approach attempting to prove P!=NP"

Those who inspire thousands of others to find and point out serius flaws in their work are too got at getting media attention and bad at their job.

A simpler proof? Please? (1)

MrEricSir (398214) | more than 3 years ago | (#33538132)

Many of the fundamental proofs in this area aren't so difficult to understand. Certainly in computing theory classes, proofs were generally a page or two and didn't involve (much) advanced math.

Maybe it's just me, but it "feels" like there should be a simpler way to go about showing that P != NP.

Re:A simpler proof? Please? (5, Insightful)

rubycodez (864176) | more than 3 years ago | (#33538164)

there should be a simpler way to go about showing that P != NP

that simpler way would only exist if P = NP

Re:A simpler proof? Please? (5, Informative)

JoshuaZ (1134087) | more than 3 years ago | (#33538444)

While the parent has been modified "funny" it really should be modified as informative or insightful. Scott Aaronson for example has discussed this issue in detail. If P=NP then we expect proofs in general in some sense to be easy but if P !=NP then in some sense proofs are difficult. (More rigorously speaking, given a well-behaved axiomatic system A, questions of the form "Is there a proof of statement s from axioms in A with the proof length at most k?" are NP-hard and for reasonable enough systems in fact NP-complete. So if P=NP proving that in some rough sense should be easy. But if P != NP then we expect proofs to be difficult. This is one of the reasons many experts actually believe P !=NP.

Re:A simpler proof? Please? (0)

Anonymous Coward | more than 3 years ago | (#33538824)

Sigh... So very depressing...
We end up proving things now by throwing lots of darts, noting that we don't hit anything, then making the logical jump that there is nothing to hit. Or rather, making the jump that even if we hit something, we can't be certain that there is nothing else to hit. Or rather, if we hit something, we can definitely now say that there is something else to hit, but there is absolutely no way that we can know how to hit it.

Re:A simpler proof? Please? (2, Interesting)

Anonymous Coward | more than 3 years ago | (#33539452)

This is definitely the kind of thing complexity theorists say. The argument fails entirely because it relies on our intuition of what easy means, and easy is not the same as polynomial, so transferring the intuition is almost intentionally misleading (not that I'm blaming you). It is basing a serious argument on an non-serious characterization of polynomial=easy that it used to help out-siders who don't know what polynomial means to never the less appreciate somewhat what complexity theory is about. Even ignoring that, if P=NP and we are pretending that easy=polynomial, then proofs are only hard because we haven't proven that P=NP at this time. Our intution is based on what is easy for us now, so all we have learned then is that, indeed, we don't now have access to a polynomial algorithm for making proofs. So the argument fails even if we overlook the slight-of-hand to replace "polynomial" by "easy".

Additionally, proving that P=NP need not be easy or have a short proof even if it is true. As you have just pointed out, it would require coming up with an algorithm that can prove anything in mathematics, every field, in polynomial time. That algorithm might well be monstrosly complicated. On the other hand, there might be a simple one-page proof that P!=NP. There is no way to tell.

Re:A simpler proof? Please? (0)

Anonymous Coward | more than 3 years ago | (#33540304)

If P = NP, you should theoretically be able to find even one NP problem that can be solved in polynomial time. It has been shown that if you can solve any NP problem in polynomial time, you can solve all of them the same way.

Re:A simpler proof? Please? (1)

gfody (514448) | more than 3 years ago | (#33540712)

given a well-behaved axiomatic system A, questions of the form "Is there a proof of statement s from axioms in A with the proof length at most k?

Didn't Gödel prove that you can't prove this or any statement like this?

Re:A simpler proof? Please? (-1, Redundant)

digitalhermit (113459) | more than 3 years ago | (#33538538)

Dude, that's so simple...

P = NP when N=1.

Where's my prize?

Re:A simpler proof? Please? (1)

Dthief (1700318) | more than 3 years ago | (#33538602)

prove N = 1

Re:A simpler proof? Please? (1)

sconeu (64226) | more than 3 years ago | (#33538682)

Assume P = NP
then NP = P
then NP/P = P/P
then N = 1

Re:A simpler proof? Please? (0)

Anonymous Coward | more than 3 years ago | (#33538812)

Doesn't work if P is 0.

Re:A simpler proof? Please? (0)

Anonymous Coward | more than 3 years ago | (#33538844)

Assume P = NP
then NP = P
then NP/P = P/P
then N = 1

What if N=738.63 and P=0?

Re:A simpler proof? Please? (1)

c++0xFF (1758032) | more than 3 years ago | (#33538822)

Or when P = 0.

Re:A simpler proof? Please? (2, Interesting)

Anonymous Coward | more than 3 years ago | (#33538934)

that simpler way would only exist if P = NP

Why? I can only guess your reasoning. Correct me if I am wrong:

"Proving P=NP can be accomplished by finding a polynomial time algorithm to the NP-hard problem of your choice. You give the problem, the algorithm, you prove is correct and that is poly-time. Success.

Proving P!=NP is the same (by definition) that proving that there is a problem in NP for wich there is no poly-time algorithm that solves it. Infinite problems and infinite algorithms... looks that proving no matching exists is necessarily hard."

It is not the case. For example, you can prove that not all sets are decidible by a simple cardinality argument. Infinite sets and infinite algorithms, but the infinites are not the same and you are done. You do not have to give a single example. It turns out that you can draw a parallel between "computable" and "computable in poly time". Many computablility proofs can be adapted to prove computability in poly-time. A nasty glitch is the P!=NP claim, which would be analogous to the existence of undecidible sets. The cardinality argument fails to prove P!=NP.
Len Adleman taught me this, or at least that is what I understood :-)

My point is that impossibility proofs are not always hard.

Re:A simpler proof? Please? (2, Informative)

gfody (514448) | more than 3 years ago | (#33540674)

Try P vs NP for dummies [qntm.org]

Re:A simpler proof? Please? (2, Insightful)

Anonymous Coward | more than 3 years ago | (#33538296)

Considering that Wiles's proof for Fermat's Last Theorem, which is a number theory problem that can be trivially stated, was ridiculously complex and used some crazy maths that weren't even discovered in Fermat's time, I don't think you can really estimate the size of a proof by the complexity of the problem stated.

Re:A simpler proof? Please? (2, Insightful)

MrEricSir (398214) | more than 3 years ago | (#33538386)

But we don't know that the current proof is the *only* proof. There may very well be a simpler one out there.

As for the problem simplicity vs. the proof simplicity, that's not what I said. I stated that related problems (in the same field) have simple proofs.

Re:A simpler proof? Please? (3, Insightful)

Dthief (1700318) | more than 3 years ago | (#33538626)

In fact Fermat would have himself needed a much simpler (and thus different) proof.......unless he made a mistake/made it up

Re:A simpler proof? Please? (1)

imsabbel (611519) | more than 3 years ago | (#33539306)

He made it up.
Or made a misstake and realized it later.

Fact is that _after_ the famous "not enough space here for the solution" stuff he still did quite some work so proof a _very_ limited subset of the last theorem.

Which does not make any sense if he had had a proof for the superset long before.

Re:A simpler proof? Please? (1)

HungryHobo (1314109) | more than 3 years ago | (#33538656)

some proofs are simple, sure, but look up busy beaver stuff to see some loooong proofs.
In cs courses they tend to stick to the most short and sweet proofs simply because the long ones would be unintelligible to almost everyone.

Re:A simpler proof? Please? (4, Informative)

JoshuaZ (1134087) | more than 3 years ago | (#33538878)

I don't think you can really estimate the size of a proof by the complexity of the problem stated.

You are correct that you cannot. In fact, this is a consequence of Godel's theorem. Proof sketch: Assume we have some nice axiomatic system A, that can model the arithmetic of the natural numbers (say Peano arithmetic), and assume that this system is not stupid (axioms are recursively enumerable, valid proofs are recursively enumerable, system is consistent. I think that's all I need but there may be some other silly issues). Assume that there is a computable function f, such that any true statement in A of length n has a proof of length at most f(n). Then I claim that we can use this to resolve whether any given statement has a proof in A by looking at all proofs of length up to f(n). This contradicts standard corollaries of Godel's theorem. So no such f can exist. Thus, minimum proof length for some statements must be much longer than the length of the statements.

Re:A simpler proof? Please? (1)

luis_a_espinal (1810296) | more than 3 years ago | (#33538334)

Many of the fundamental proofs in this area aren't so difficult to understand. Certainly in computing theory classes, proofs were generally a page or two and didn't involve (much) advanced math.

Maybe it's just me, but it "feels" like there should be a simpler way to go about showing that P != NP.

You "feel"? If there has even been a most unsubstantiated and unscientific subjective expression of feelings over fact, this is it.

Re:A simpler proof? Please? (4, Insightful)

MrEricSir (398214) | more than 3 years ago | (#33538410)

Science may lead to facts, but it's not an automated process. Believe it or not, human emotions and intuition are involved with every scientific discovery!

Re:A simpler proof? Please? (1)

geekoid (135745) | more than 3 years ago | (#33540808)

Yes, but they needed to be removed from any rigorous study.

Nature doesn't care how you feel..ever.

Re:A simpler proof? Please? (0, Redundant)

Zalbik (308903) | more than 3 years ago | (#33538568)

Many of the fundamental proofs in this area aren't so difficult to understand. Certainly in computing theory classes, proofs were generally a page or two and didn't involve (much) advanced math.

Maybe it's just me, but it "feels" like there should be a simpler way to go about showing that P != NP.

It's just you.

See, the problem is that it's possible that P = NP. For example, say N=1, then trivially:
        P = P
        P = 1 x P
        P = NP
This also works for P=0.

The problem is, we can't get the mathematicians to agree whether N=1 or P=0.

Re:A simpler proof? Please? (0)

Anonymous Coward | more than 3 years ago | (#33538920)

Maybe both?

Damn... (5, Funny)

PmanAce (1679902) | more than 3 years ago | (#33538136)

I guess I will never profit from my proof I posted a while ago since his didn't hold up:

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:Damn... (1)

LegoEvan (772742) | more than 3 years ago | (#33538314)

I think I spotted an error... you were too quick with the cancellation. The main point is that P! / P = (P-1)!

Re:Damn... (1, Funny)

Anonymous Coward | more than 3 years ago | (#33538416)

My thoughts exactly.

Re:Damn... (0)

Anonymous Coward | more than 3 years ago | (#33538738)

The main point is that P! / P = (P-1)!

Next time you want to give geeks a headache, ask if they have any thoughts on the (P-1)!=N problem and see if anyone gets it.

This works better on forums than in person, since you need the ability to walk away and let it sit there and bother people.

Re:Damn... (1)

interval1066 (668936) | more than 3 years ago | (#33538926)

Step #3: ???
Step #4: Profit!

Boy, that joke just never gets old, does it?

In Other Words, It Was A Crowdsourced (-1, Offtopic)

Anonymous Coward | more than 3 years ago | (#33538290)

Book Burning [youtube.com] !

Yours In Novosibirsk,
K. Trout

Um, isn't it obvious (1)

shoebucket (196059) | more than 3 years ago | (#33538308)

... that P != NP for all values of N except where N = 1? What's all this rukkus?

Re:Um, isn't it obvious (0)

Anonymous Coward | more than 3 years ago | (#33538342)

Yeah, or P=0. Somebody needs to hit all those PhDs with a clue-bat.

Ah, but what if it had held up??? (4, Insightful)

davidwr (791652) | more than 3 years ago | (#33538312)

We would be reading this instead:

"Remember, about a month ago, when a researcher claimed he had a proof that P != NP? Well, after a month of vigorous examination by ordinary netizens and Nobel-prize-winning mathematicians, it looks like it's going to hold up. 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 works, and the holes experts and laymen attempted to punch in it and why the proof is still standing."

Re:Ah, but what if it had held up??? (1)

geekoid (135745) | more than 3 years ago | (#33539154)

Nobody who can add to the P != NP discussion intelligently is an ordinary netizens*.

Look, no one without an interest in math gave a hoot. In fact pretty much any advanced math problem is going to be self selected to be pretty much all people who can contribute.

Had it been about Vitamin D research, then having it open would have been a nightmare.

*And that is the stupidest word to come out of the internet, far far worse the blogosphere.

P=NP or P!=NP depends ono age (-1)

Anon-Admin (443764) | more than 3 years ago | (#33538364)

I have NP (No Problem) Peeing but I understand that when you get older your prostate can cause you to have problems so Peeing would be a problem. But would that not be P=NP when young and P=P when old? It seems that saying it as P!=NP is just too geeky.

Just a random thought.

Re:P=NP or P!=NP depends ono age (1)

mcgrew (92797) | more than 3 years ago | (#33538490)

It seems that saying it as P!=NP is just too geeky.

There is no such thing as "too geeky". Especially here.

Great story (3, Insightful)

oldhack (1037484) | more than 3 years ago | (#33538388)

This has been one of the best slashdot posts in a long, long while.

I'm gonna have to renew my subscription to Science News. Kudos to Ms. Rehmeyer.

Um... pretty old news, folks. (1)

Jane Q. Public (1010737) | more than 3 years ago | (#33538406)

Yes, Deolalikar's claim was made a little over a month ago. But this blog post is also over a month old. I read it on the day it was posted. And many if not most of the objections that appear there have been there ever since that day.

I mean really. Nothing new here, folks. Move along now.

Re:Um... pretty old news, folks. (1)

oldhack (1037484) | more than 3 years ago | (#33538594)

The Science News piece, which summarizes the episode quite skillfully, is dated 9th September.

I swear, if slashdot got a nickle for every smart-ass comment on it (including plenty from yours truly), she would have suffered a coin-induced gravitational collapse.

Re:Um... pretty old news, folks. (1)

Jane Q. Public (1010737) | more than 3 years ago | (#33540588)

But blog which is the ultimate source of the information is still dated August 9. And there was even talk about it here on /.

Re:Um... pretty old news, folks. (0)

geekoid (135745) | more than 3 years ago | (#33539198)

YO really don't get it, do you? Slashdot is a place where a lot of stories from a lot of different places is brought together(sometimes twice~).

It's very nature means it will be behind the places that first publish this stuff.
It's only a month behind, not exactly a big deal.

It's new to me, and ti's new to a lot of other people. so STFU or get out.

Re:Um... pretty old news, folks. (1)

Jane Q. Public (1010737) | more than 3 years ago | (#33540630)

"It's new to me, and ti's new to a lot of other people. so STFU or get out."

That's pretty funny. Did I stop you from reading TFA? Or any of the other comments? I think it's pretty amusing to draw this kind of reaction for simply saying that this happened a month ago.

But you are free to skip my comments if you want to. Nobody is making you read them. So if you don't like them, it's you who can GTFO.

Wait So . . . (0)

Anonymous Coward | more than 3 years ago | (#33538412)

This proved that people on the internet like proving/pointing out when people are wrong? How is that new/news?

Re:Wait So . . . (0)

Anonymous Coward | more than 3 years ago | (#33539024)

This didn't prove anything! This merely failed to disprove it.

Don't give yourselves that much credit (0)

Anonymous Coward | more than 3 years ago | (#33538580)

Anyone in a real position to offset the presented theory didn't need blogs and certainly not Slashdot. Do you honestly think our best minds sit around reading about the latest Linux distro and what's new in the Lego's world? If you do it is high time you pulled your head from your ass.

Obvious or oblivious? (2, Funny)

bluefoxlucid (723572) | more than 3 years ago | (#33538640)

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:Obvious or oblivious? (0)

Anonymous Coward | more than 3 years ago | (#33538802)

I agree 100% with what you are saying. The mere fact that people aren't finding P solutions to NP problems all the time is proof that P != NP. I could see if here and there we were finding ways to make problems like the traveling salesman and the K-SAT reduce to P, then we'd start to see a pattern of how NP reduces to P. But, this isn't happening. This should prove within a 99% certainty that we are not going to find P solutions to NP problems. They are a different class of problems for a reason. The best we can do is make successive approximations to find "good enough" answers to these problems.

Or, maybe we just aren't smart enough to comprehend these problems. Well, the true power of our ingenuity and intelligence will manifest itself when we are able to create quantum computers to solve these types of problems for us by trying all possible solutions at once.

Re:Obvious or oblivious? (1)

koreaman (835838) | more than 3 years ago | (#33539046)

Dude, do you have any idea what a "proof" is?

Re:Obvious or oblivious? (0)

Anonymous Coward | more than 3 years ago | (#33539360)

Yes, I only did about a billion of them when I was in college for CS. I was saying fuck finding a proof for P != NP. It's obviously true. Nothing exciting will come out of the fact that someone formally proves it except that a few people will get a few math boners and we finally don't have to hear anything more about this topic.

If P = NP, it would be revolutionary and change computer science and math forever. But, I am highly doubtful that they are equal.

Re:Obvious or oblivious? (1)

Toonol (1057698) | more than 3 years ago | (#33539688)

Yes, I only did about a billion of them when I was in college for CS. I was saying fuck finding a proof for P != NP. It's obviously true.

And that's interesting. There's a disconnect of sorts between formal logic and reason, tied in to the difference between deductive and inductive methods. Of course a proof is nice, and a necessary part of advancing mathematics; but a person would not be in error for believing N != NP. At some point a preponderance of evidence, or probability, or reasoning by analogy, or Monte Carlo simulation, can lead to to a practical certainty that something is true. They aren't absolutely certain, and those methods of reasoning would all fall before a REAL proof... but neither are they worthless. Sure, "obviously true" things might end up not being true... but in the vast majority of circumstances, they ARE... and we'd be crippled if we didn't act on them.

Re:Obvious or oblivious? (2, Interesting)

Anonymous Coward | more than 3 years ago | (#33538944)

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.

Following that logic, the world was flat until Galileo stated otherwise.

Really.... we humans are ignorant enough that we could be footling around with a limited set of algorithms for aeons and not stumble on any that solve NP problems. This isn't QED, it just shows that our set of known algorithms is painfully limited.

Think about Quicksort: that's an algorithm that really opened my eyes to P=?NP, as it showed how you could really optimize a sort by limiting the scope of the elements being sorted. I had never come up with quicksort by myself, and so it showed me how solutions can exist that we just haven't seen before. Such solutions will continue to pour in... possibly including solutions that provide binary computational engines with heretofore unbelievably powerful computing powers.

Think of it like this... HDD manufacturers were coming up against a known density limit, which meant that they theoretically couldn't manufacture platters with any higher density of information... so what happened? Instead of throwing in the towel and saying "well, time to find some other way to store information," some enterprising soul thought "well, what happens if we make the charges vertical instead of horizontal?" This is the kind of reasoning that is applied to P (and possibly NP) problems to create more efficient solutions. Often, it just takes a re-analysis of the base assumptions to find a novel way of completing a task. Believing that P==NP would go a long way towards having a more robust P set, even if no NP solutions were ever discovered.

Re:Obvious or oblivious? (1)

geekoid (135745) | more than 3 years ago | (#33539232)

Yeah... or there is something else we haven't figured out.

They are looking for mathematical proof.

If you have 3 oranges, and one goes away you will have 2 oranges QED. That does NOT answer why one orange went away.

Re:Obvious or oblivious? (1)

JordanL (886154) | more than 3 years ago | (#33540488)

"Presumably" is the step where you proof breaks down. If P=NP one would also expect proofs to be easier, for reasons elaborated on in a comment further up the page. But as noted there, we cannot know that we are looking effectively for ways to do that.

This is not a perfect comparison, but consider that before Calculus, or rather the fundamental theorem, integrating was inexact, clunky, and was a very difficult problem that was impossible to give an exact answer to. But with the FTC it became possible to not only integrate quickly, but to do so exactly. And the main leap there was the idea of something acting as if it were both zero and just very, very small (due to the rate at which it approached zero).

When Isaac Newton first proposed his ideas on Calculus, he made a squished looking zero that he claimed acting like a zero at times, and like an arbitrarily small number at others, which infuriated his contemporaries as it worked.

The point is that this completely different way of thinking VASTLY reduced the necessary consideration to produce a valid integration. We do not know that the same is not also true for all NP problems.

To summarize where the proof went wrong... (4, Informative)

JoshuaZ (1134087) | more than 3 years ago | (#33538674)

To summarize what difficulty the proof ran into: There's a general class of NP-complete problems known as SAT. SAT is essentially given a collection of Boolean variables (so can have values "yes" or "no") and given some logical statement of those variables is there an assignment to those variables that makes the statement true? So for example, for A ^ ~ A, there isn't one, but for say A v B there are satisfactory solutions. This problem is the canonical NP-complete problem. Now, the attempted proof examined k-SAT, which is a subset of SAT known to also be NP-complete. k-SAT is the same thing as SAT but each statement must be a sequence of ands containing k inputs into set of ors. 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. Deolalikar tried to examine the statistical properties of k-SAT and derive a contradiction from the assumption that k-SAT was polynomial time solvable. However, this runs into issues because from a statistical perspective 2-SAT is known to look statistically more or less the same as k-SAT, and 2-SAT is polynomial time solvable. This is a deep barrier which the proof did not overcome.

There are other deep barriers that the paper did not obviously overcome, including what is known as the "natural proof" barrier and the "relativization" barrier. The last essentially says that P=NP is true in some other computing models very similar to the standard Turing model (you consider Turing machines with special black boxes called oracles attached which answer specific questions quickly.) Similarly, it turns out that P != NP for some oracles as well. Thus, any valid resolution of P=NP will have to break down in some more or less obvious way when one tries to run the proof through for an oracle machine. If one can't point to where in a proof this would occur, this is a good indication that the proof is not valid.

Overall, I'm highly pessimistic that we are going to resolve P=NP anytime soon although I strongly believe that P != NP. There are currently much weaker claims than P=NP that we still cannot prove. We can't as far as I'm aware even get a strongly non-trivial result of the form for some explicit constant C, "No NP complete problem can be solved in polynomial time with a polynomial of degree at most C." And that's much weaker than showing that P != NP, because P !=NP is essentially that statement made for any value of C. We seem to need serious new insights and possibly lots of new machinery and structures before we can have a really good chance at cracking this nut.

Re:To summarize where the proof went wrong... (2, Funny)

regular_gonzalez (926606) | more than 3 years ago | (#33539504)

Can I get a summary of the summary please

Re:To summarize where the proof went wrong... (4, Funny)

corbettw (214229) | more than 3 years ago | (#33540324)

Math is hard, but some types of math are really hard.

Re:To summarize where the proof went wrong... (2, Funny)

cpghost (719344) | more than 3 years ago | (#33540574)

But how do we prove that MP != MNP, where MP = {p | p = Math proof that is understandable in polynomial time}?

Re:To summarize where the proof went wrong... (4, Funny)

DavidD_CA (750156) | more than 3 years ago | (#33539826)

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... (1)

ACS Solver (1068112) | more than 3 years ago | (#33540048)

Thanks for taking the time to post this. While the attempted proof paper and most discussion surrounding it is way too difficult for me to comprehend, your post does actually parse.

Poor reference (0, Flamebait)

admiral201 (562265) | more than 3 years ago | (#33538816)

"This article" is poorly specified. There are three articles linked in the brief text, and of course, none of them are actually linked to the expected "This article." So, what article is "This article" referring to? And, why should I waste my time trying to figure it out?

maybe not proven, but seems obvious (1, Flamebait)

theendlessnow (516149) | more than 3 years ago | (#33538872)

In C code:

            choice1="P";
            choice2="NP";

            if (choice1 != choice2)
                    yeahbaby++;

Submit that! Science, math, logic... it's just too easy

Re:maybe not proven, but seems obvious (1)

Spykk (823586) | more than 3 years ago | (#33538988)

Are you sure that's C? I don't think that "choice2="NP";" does what you think it does...

Re:maybe not proven, but seems obvious (0, Troll)

awc (1656865) | more than 3 years ago | (#33539100)

good job, here's a million bucks

Re:maybe not proven, but seems obvious (2, Funny)

geekoid (135745) | more than 3 years ago | (#33539590)

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!

One problem in the article for me... (1)

Chowderbags (847952) | more than 3 years ago | (#33539184)

He translated the problem of P versus NP out of computer science entirely and into the world of formal logic, using an area known as "finite model theory" that has produced remarkable results.

*face hits palm*

Computer science uses formal logic in it's proofs all the time (at least as formal as mathematics).

For example, choose k logical requirements at random and ask: What is the probability that there is some binary number of n digits that will satisfy them all? If the number of requirements is huge (i.e., k is large) and the number of possible solutions is tiny (i.e., n is small), then of course there will never be correct solutions, no matter how long the problem is calculated.

This too is a facepalming moment. It's akin to saying "If you flip a coin 100 times, of course it will land on heads at least once." Except that a probability of 1/(2^100) != 0.

I'm not sure I understand (0)

Anonymous Coward | more than 3 years ago | (#33539284)

Even if P=NP, wouldn't someone have to figure out the P for every given NP? There'd still be no magic bullet for that part, right?

slashdot has confusing hyperlinks in its summaries (5, Interesting)

ljw1004 (764174) | more than 3 years ago | (#33539524)

This summary had three hyperlinks:

1. "claimed he had a proof"
2. "hasn't held up"
3. "spur a massive effort"

It was missing the only IMPORTANT hyperlink:

4. "this article". --- The slashdot submission was about an article. I'd like to read the article. I'd like a hyperlink which unambiguously takes me to the article. As it was, I didn't know which of the hyperlinks would take me to the article.

1. "claimed he had a proof" -- did this hyperlink take me to his claim? No: it took me to a online collaborative discussion of his claim (i.e. the original slashdot article).

2. "didn't hold up" -- did this hyperlink take me to the announcement that it didn't hold up? No: it took me to a slashdot article that maybe had a link to the statement about how it didn't hold up.

3. "spur a massive effort" -- did this hyperlink take me to that effort? Or did it take me to the spur in question? No: it took me to a REVIEW of that effort.

The hyperlinks in Slashdot summaries are always confusing.

Pi, what a waste of time (2, Insightful)

p51d007 (656414) | more than 3 years ago | (#33539822)

Just think of all the computing power, resources have been WASTED over the years trying to figure out the final digits to pi. Does it really matter if their are 1,000,000, 1,000,000,000, or 1,000,000,000,000 digits of pi? For 99.9% of the public, 3.14xxx is good enough.

Re:Pi, what a waste of time (2, Interesting)

Sulphur (1548251) | more than 3 years ago | (#33540506)

Take a CAD program and figure the area of a circle of radius one. In some cases you get an interesting value of pi.

--

pi = 22/7. 22/7 repeats. Therefore pi is not transcendental.

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?
or Connect with...

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>