Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

P ≠ NP

scribd.com

Post reply on HN
Print view View original

171–180 of 233 posts

Re: P ≠ NP

#171

Post by wlievens »

JeanPierre wrote: post #39
zacs wrote: post #37

The paper's origin was that the author mailed a copy for review to some very high-level folks in the field (Cook, Mazirani, Sipser, etc). Here's the mail: Date: Fri, 6 Aug 2010 21:28:39 +0000 Subject: Proof announcement: P is not equal to NP Dear Fellow Researchers, I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts. The proof required the piecing together of principl…

If this proof is up for review, that would mean there could be errors in it, right?

If a proof has been reviewed there might still be errors in it...

Re: P ≠ NP

#172

Post by Confusion »

Eliezer wrote: post #165

Scott Aaronson expresses his confidence that the proof is wrong by offering to supplement the million-dollar Clay prize with $200,000 of his own money if it's correct: http://scottaaronson.com/blog/?p=456

I find it strange that he doesn't explain his confidence with at least a general description of the way in which he thinks the proof will fail.

I suppose he could have safely claimed this with Wiles's original proof as well, since it did have at least one non-trivial flaw that required amending. It's quite possible that the proof contains flaws, but will still hold up in the end, because the flaws can be corrected. But I feel that's a bit of a lame gamble.

Re: P ≠ NP

#173

Post by albertzeyer »

Confusion wrote: post #172
Eliezer wrote: post #165

Scott Aaronson expresses his confidence that the proof is wrong by offering to supplement the million-dollar Clay prize with $200,000 of his own money if it's correct: http://scottaaronson.com/blog/?p=456

I find it strange that he doesn't explain his confidence with at least a general description of the way in which he thinks the proof will fail. I suppose he could have safely claimed this with Wiles's original proof as well, since it did have at least one non-trivial flaw that required amending. It's quite possible that the proof contains flaws, but will still hold up in the end, because the flaws can be corrected. B…

Sometimes there are also flaws which can not be corrected.

But I cannot make a qualified guess if this might be the case here.

Re: P ≠ NP

#174

Post by pmiller2 »

Vivtek wrote: post #161
Confusion wrote: post #156

Earlier quoted context omitted.

* If the statistical physics method used here is powerful enough to resolve P != NP, then there's a good chance it is powerful enough to have led to many smaller results before the author was able to nail the big one. It's a little weird we haven't heard anything about that earlier. Well, Wiles didn't publish intermediate results either, partly because someone might have beat him to the final result with those interm…

The conclusion might seem to be that prizes harm science. Which sucks, but intermediate results are important for science as a whole; if there's significant financial reason to withhold them, we're no better than the alchemists.

But, there was no prize for solving FLT other than being able to list on one's CV "Proved FLT."

Re: P ≠ NP

#175

Post by Confusion »

albertzeyer wrote: post #173
Confusion wrote: post #172

Earlier quoted context omitted.

I find it strange that he doesn't explain his confidence with at least a general description of the way in which he thinks the proof will fail. I suppose he could have safely claimed this with Wiles's original proof as well, since it did have at least one non-trivial flaw that required amending. It's quite possible that the proof contains flaws, but will still hold up in the end, because the flaws can be corrected. B…

Sometimes there are also flaws which can not be corrected. But I cannot make a qualified guess if this might be the case here.

Of course, but that's an even larger gamble, if you don't have at least a very specific hunch about the way in which a proof will fail. All in all, this announcement by Aaronson seems rather rash. I don't understand why he would do such a thing.

Re: P ≠ NP

#176

Post by philwelch »

dasht wrote: post #56

So: What publicly traded firms benefit from a confirmation that P!=NP and are there any that lose (e.g., that were betting that P might == NP). There's gotta be money in this news :-)

Assuming P provably != NP, banks and online retailers win (certain forms of encryption even theoretically can't be broken in P time), NSA supercomputer contractors might lose (certain forms of encryption even theoretically can't be broken in P time). UPS and FedEx likely lose (traveling salesman problem is NP-complete). Any other business that hinges on solving hard problems might lose, though counterintuitively, some might win--firms that do a really good job at approximate solutions to NP problems (is ITA an example?) are extremely talented at doing something really hard, whereas if P = NP, it would be easier for any old firm to develop a perfect solution.

But considering the fact that we've all been operating under the assumption that P != NP, the losers don't lose much (if anything) and the winners don't win much (if anything). If P = NP was proven, it's possible but not guaranteed that bank robbers and whatever software firms can pivot fast enough to exploit P = NP get huge windfalls, internet retailers would be ruined, banks who didn't shut off their data links fast enough would be ruined, etc. This worst case scenario hinges on a proof that took the form of a proof by counterexample, which happened to neatly solve an NP-complete problem in efficient P time. In better case scenarios, where other proof forms were used or the P-time solution was a horrific factor like O(n^100,000), online retailers would still lose a little if only based on media hype about the discovery scaring grandmothers away.

Re: P ≠ NP

#179

Post by hga »

kjrose wrote: post #139
hga wrote: post #93

Earlier quoted context omitted.

Statistical mechanics : http://en.wikipedia.org/wiki/Statistical_mechanics

"is the application of probability theory" My comment still stands.

I wonder, since you said your problem was that it "could easily imply the common problem of assuming the existence of a secure PRNG". Statistical mechanics involves real, true randomness, and the statistical comes in e.g. where you use statistical models of things at the micro scale to explain macro scale behavior. I don't get the impression that it involves statistics in the way you are using the word.

Re: P ≠ NP

#180

Post by svat »

Eliezer wrote: post #165

Scott Aaronson expresses his confidence that the proof is wrong by offering to supplement the million-dollar Clay prize with $200,000 of his own money if it's correct: http://scottaaronson.com/blog/?p=456

Scott Aaronson does not explicitly say the proof is wrong, but says

> If P≠NP has indeed been proved, my life will change so dramatically that having to pay $200,000 will be the least of it. […] If P≠NP is proved, then to whatever extent theoretical computer science continues to exist at all, it will have a very different character.

and

> I can afford $200k, but not in the same way Bill Gates can afford $200k.

Post reply on HN