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

161–170 of 233 posts

Re: P ≠ NP

#161

Post by Vivtek »

Confusion wrote: post #156
randomwalker wrote: post #41

Several points on the question of whether the proof is likely to be correct: * As far as I know this paper wasn't circulated for informal peer review before being made public; I heard no talk on the grapevine. (Edit: apparently it was circulated and someone other than the author made it public.) * Therefore a proper assessment is going to take a while. Until then we can only speculate :-) * While the crank attempts a…

* 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.

Re: P ≠ NP

#162

Post by mmaunder »

lkozma wrote: post #40

I skimmed through the synopsis but this philosophical statement baffles me (although obviously it is unrelated to the validity or invalidity of the proof): "The implications of [P ?= NP] on the general philosophical question of [..] whether human creativity can be automated, would be profound." How so? If P!=NP, that is obeyed by the brain as much as by computers and whatever trick our brains does to be creative desp…

AFAIK the thinking is that if P=NP then we might be able to automate the creation of theorems because we'd be able to take a problem who's solution is known to be quickly verifiable and because we know it's therefore quickly solvable we might be able to automatically develop the theorem that solves it. So his proof suggests that human creativity can't be automated.

Re: P ≠ NP

#163

Post by loup-vaillant »

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.

The problem is, the most important prize (being able to say "I found it first") is unavoidable.

Re: P ≠ NP

#164

Post by Confusion »

loup-vaillant wrote: post #163
Vivtek wrote: post #161

Earlier quoted context omitted.

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.

The problem is, the most important prize (being able to say "I found it first") is unavoidable.

Yeah, that's what I meant with 'the grand prize'. Not the 1 M$ from the Clay institute; that's just topping on the cake.

Re: P ≠ NP

#166

Post by dLuna »

Confusion wrote: post #164
loup-vaillant wrote: post #163

Earlier quoted context omitted.

The problem is, the most important prize (being able to say "I found it first") is unavoidable.

Yeah, that's what I meant with 'the grand prize'. Not the 1 M$ from the Clay institute; that's just topping on the cake.

Agree fully. Also worth considering if this proof turns out to be correct, is that he will probably have employment contracts and speaker deals dwarfing that $1M quite soon.

Re: P ≠ NP

#167

Post by varjag »

fmora wrote: post #146
dasht wrote: post #53

Earlier quoted context omitted.

You must read it in context. What it says is that if P == NP then the implications are profound for applications such as cryptography and on the general question of whether human creativity can be automated. You can see why P == NP would have profound implications for crypto: many of our widely used techniques would turn out to, um, be easy to crack. I believe the intent regarding human creativity is that humans ofte…

Lets assume that P==NP, why assume that we would be able to find algorithms to easily crack crypto? Let me put it another way, lets say that we finally discover that it is possible to time travel to the past. However, the energy needed to travel back int time is the equivalent of a million Suns because that is the amount of energy needed to warp space enough so that time will reverse itself. And we found proof of thi…

We would know from the proof that such algorithms would exist, and possibly get a method from the proof as to how formulate them.

Also, gut feeling doesn't work in math. I mean, not at all.

Re: P ≠ NP

#168

Post by euccastro »

dasht wrote: post #80
shrikant wrote: post #73

Earlier quoted context omitted.

There sure is: http://www.claymath.org/millennium/P_vs_NP/

Ah, yes. No, I meant for the outside investor with early news of the purported proof who is willing to bet that it holds up. For example, if there is some crypto company whose business is premised on hedging that a "P == NP" proof is just around the corner - short them. Alternatively, maybe buy the firm we think of as RSA. That kind of thing. This paper hasn't yet got a lot of press attention and I'm only about 1/4 j…

HP will get some prestige out of this, and not much else will happen short term. Almost everyone was already assuming P != NP.

Re: P ≠ NP

#169

Post by mzl »

jackfoxy wrote: post #100

Very interesting approach! How cool if this is the real deal. The last 30 years has seen a lot of theoretical work on computation as a physical process. If the greatest conjecture in CS is proved using tools from physics it really brings together math, physics, and CS. Edit: As someone else pointed out a few minutes ago http://www.hpl.hp.com/personal/Vinay_Deolalikar/ confirmations began arriving today. How soon befo…

Wrong area for a Nobel prize, the prize areas are physics, chemistry, physiology/medicine, literature, and peace. There is also a prize in economics given at the same time.

Re: P ≠ NP

#170

Post by agravier »

jackfoxy wrote: post #100

Very interesting approach! How cool if this is the real deal. The last 30 years has seen a lot of theoretical work on computation as a physical process. If the greatest conjecture in CS is proved using tools from physics it really brings together math, physics, and CS. Edit: As someone else pointed out a few minutes ago http://www.hpl.hp.com/personal/Vinay_Deolalikar/ confirmations began arriving today. How soon befo…

There is no Nobel prize for Mathematics.
Post reply on HN