51–60 of 233 posts
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…
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 often end up with a practical need to deal with some real-world instance of a size-able NP-complete problem. We don't know any way to efficiently find the optimal solution so we creatively deal with what we can figure out (the traveling salesman's optimization problem, placed into the real world, might count). Are our creative guessworks and heuristic discoveries essential? Or can automation based on P == NP eliminate the need for them - and do better than we do on these problems.
The opposite proposition -- that P is equal to NP -- is widely doubted. But if there were a proof that P and NP were equal, anyone with a good data set could verify the proof in a few minutes. Just run the proof on a hard 3-SAT or whatever and observe the answer returning significantly before the heat death of the universe.
So what we think is true is insanely hard to verify but what we think is false is blazingly obvious to check. Chalk another one up for irony.
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…
I'm curious - how do you know this mail was sent to the aforementioned people in complexity theory?
Also, from the blog post: "I see someone else has uploaded the paper. I should point out that in the email thread I got, Stephen Cook said “This appears to be a relatively serious claim to have solved P vs NP.". I would love to see that email thread.
There's gotta be money in this news :-)
Can someone call Knuth? If he gives it the thumbs up then I'll believe it.
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…
> This is hardly the first unverified proof of the equality of P and NP. in 'a' above didn't you mean to write 'inequality of P and NP' ?
102 pages via one of the most annoying PDF readers on the planet? No thanks. There are good, free, PDF readers for every major operating system and for every major mobile device. I wish people would just link directly to PDFs.
http://dl.dropbox.com/u/33127/35539144-pnp12pt.pdf
Earlier quoted context omitted.
This is not the point.
Sure it is. Scribd has succeeded in going from "the worst pdf viewer on the web" to something that's perfectly usable using HTML5.