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

181–190 of 233 posts

Re: P ≠ NP

#181

Post by JabavuAdams »

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…

I'm not sure why creativity has this special aura. My internal process seems fairly mechanistic, to me.

Perhaps it's a legacy from the idea of a life-force or vis viva.

Re: P ≠ NP

#182

Post by marbu »

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…

Well, but Scott Aaronson wrote: "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." So I suppose that any non-trivial flaw which will be eventually fixed by author of the paper himself is not a problem here.

Re: P ≠ NP

#183

Post by presidentender »

agravier wrote: post #170
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.

Or Economics. No, really, the "Nobel Prize" in economics isn't: http://en.wikipedia.org/wiki/Nobel_Memorial_Prize_in_Economi...

Re: P ≠ NP

#184

Post by tel »

Groxx wrote: post #66
ynniv wrote: post #16

Earlier quoted context omitted.

a) Complicated academic proofs take (and should take) months if not years to verify, and will only be "front-page news" after verification. This is hardly the first unverified proof of the [edit: possible (in)]equality of P and NP. b) The practical consequences of P=NP are immense. The practical consequences of P≠NP are that we can stop looking for computational unicorns and fairies. We have for some time thought tha…

I doubt it'll impact the unicorns-and-fairies searches significantly. Most people already work under the assumption that P≠NP. Similarly, most people believe the world is round, and we go around the Sun. This hasn't prevented serious flat-Earthers nor geocentrists from existing.

It has been something of a damper on their funding, however.

Re: P ≠ NP

#185

Post by studer »

svat wrote: post #180
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.

Discussed here:

http://news.ycombinator.com/item?id=1587405

As randomwalker says, it's not entirely obvious that Aaronson is betting against the proof.

Re: P ≠ NP

#186

Post by shadowfox »

pmiller2 wrote: post #174
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.

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

You wouldnt actually need to put that in your CV

Re: P ≠ NP

#187

Post by sfk »

pmiller2 wrote: post #174
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.

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

Not that it matters, but there was the Wolfskehl Prize:

http://www.simonsingh.net/Wolfskehl_Prize.html

Re: P ≠ NP

#188

Post by Jun8 »

houseabsolute wrote: post #151
Jun8 wrote: post #147

This is sad: This result, if correct, is the mathematical result of the century; however, it still hasn't appeared in Google News or Google trends.

It's a leaked PDF of an unverified proof which has yet to appear in any mainstream news source and is relevant, probably, to no one but computer scientists. So it's not even remotely surprising that it has not yet appeared on Google News. I have no idea what part of this you think is sad.

This result is much more relevant than either Perelman's proof of the Poincare Conjuncture or Wiles' proof or Fermat's Conjuncture, both of which got huge coverage in the mainstream media. If you think this is relevant to "no one but computer scientists" you are naive about the ramifications of the result.

The proof is unverified but most qualified sources say it is one of the best efforts in many years, it could even be the proof. This was the #1 news in most technical blogs yesterday.

Re: P ≠ NP

#189

Post by long »

cdavidcash wrote: post #153
long wrote: post #119

Earlier quoted context omitted.

Again, I'm no expert, but relativization and algebrization are properties of proofs that invoke oracles, which this paper doesn't appear to do.

Ah, that is not how those "barriers" work. Roughly, the relativization barrier goes like this: Say you have a proof that P!=NP. Does it also prove that P^A != NP^A for any oracle A? If it does, then the proof is flawed, because there does exist an oracle A such that P^A = NP^A! Such proofs are said to relativize -- i.e., they are still valid relative to any oracle.

Ah, thanks for explaining!

Re: P ≠ NP

#190

Post by akshayubhat »

dLuna wrote: post #166
Confusion wrote: post #164

Earlier quoted context omitted.

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.

Money is the last thing to care about if you solve P ?= NP. Humanity will remember you in same league as Turing Pythagoras Gauss and others.
Post reply on HN