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

111–120 of 233 posts

Re: P ≠ NP

#111

Post by ratsbane »

leif wrote: post #68
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…

Somewhere, deep in a dark corner of my heart, I hope and pray that this paper is correct, just so we can keep and revere the immortal words "I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts ."

Sounds a little like the line in Watson and Crick's first paper about DNA. They said "It has not escaped our notice..." to introduce the idea that the subject of the paper might be the secret to life, the universe, and everything.

Re: P ≠ NP

#112

Post by dfox »

miloshh wrote: post #46
abstractbill wrote: post #33

Earlier quoted context omitted.

Intuitively: NP questions take a long time to answer. P questions take much less time. The statement "P = NP" means that any NP question can be transformed into a P question. Answering the P question gives you an answer to the NP question. So, if P = NP, then we can answer questions that we thought were slow, much more quickly than we would have thought possible. Proving P = NP would (presumably) give you that method…

Yeah, the common complaint against "P=NP would break cryptography" is "but what if the polynomial algorithm for (say) SAT is n^10000?". That is not very likely, in my opinion. Even though "polynomial" is not equivalent to "efficient", in practice all problems that have a polynomial algorithm also have an efficient algorithm.

There are many problems that have polynomial algorithm, that is not especially fast for practical problems (matrix multiplication comes to mind for example, for which there isn't even any proof that fastest known algorithm is in fact optimal)

Re: P ≠ NP

#114

Post by cdavidcash »

long wrote: post #86
bramcohen wrote: post #81

While the author of this paper does not appear to be a crank, nowhere in the entire paper does it discuss why the fundamental barriers of naturalization, algebrization, and relativization don't apply to the work, making it seem unlikely that those barriers have actually been overcome.

From what little I understand, those barriers prevent only certain proof strategies from working. So for instance, the Razborov-Rudich barrier concerns a class of combinatorial proofs (the so-called natural proofs); this paper uses two techniques - statistical mechanics and model theory - which I gather are out of the province of RR.

"only certain proof strategies" is technically correct, but its closer to "essentially every proof strategy we can conceive of".

And besides, the question is over the entire proof strategy and not the specific techniques involved. It seems plausible that one could give a relativizing proof using some method of calculation from statistical mechanics, for example.

Re: P ≠ NP

#115

Post by pavs »

mishmash wrote: post #102
pavs wrote: post #63

Earlier quoted context omitted.

2 things. - The html5 transformation is not instant. Everyone gets the Flash reader till the HTML5 version gets ready. Which can be anywhere between minutes to hours (I don't know the avg time). - The HTML5 version or the Flash is worse than a plain old PDF viewer. Have you used the Integrated PDF viewer in Chrome lately? PDF under chrome makes reading PDF fun again, its the fastest/smoothest PDF viewer I have ever u…

Have you used BugMeNot? http://www.bugmenot.com/view/scribd.com

I have in the past for other sites. But now, sites that do decide to BugMe I choose Not to visit them.*

*NYT being the exception.

Re: P ≠ NP

#116

Post by akshayubhat »

werrett wrote: post #85
ilkhd2 wrote: post #34

See, all these monstrous old companies such as IBM and HP, they hire pure scientists such as Chaitin and this guy, and every once in awhile it pays off. I have feeling, yonger companies, with their own research departments, they are still very down to earth, and look for immediate profit from R&D.

To quote the announcement email which zacs posted earlier: This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work. So based off this solitary data point, it seems that while they might hire the brains it doesn't necessarily follow that they have…

I feel its more like saying that the work is not endorsed by HP, without actually saying it.

Re: P ≠ NP

#117

Post by Dn_Ab »

benhalllondon wrote: post #10

Anyone got a link to any proper discussion?

Here is a good link. http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-n...

The suspence is killing me. As an observer I'm worried that there is some small error in the core of his argument that will cause the whole thing to unravel, as is often the case for proofs of this level. But I am hopeful that at least this may be a breakthrough that points to approaches to finally nail this great beast.

Re: P ≠ NP

#118

Post by miloshh »

dfox wrote: post #112
miloshh wrote: post #46

Earlier quoted context omitted.

Yeah, the common complaint against "P=NP would break cryptography" is "but what if the polynomial algorithm for (say) SAT is n^10000?". That is not very likely, in my opinion. Even though "polynomial" is not equivalent to "efficient", in practice all problems that have a polynomial algorithm also have an efficient algorithm.

There are many problems that have polynomial algorithm, that is not especially fast for practical problems (matrix multiplication comes to mind for example, for which there isn't even any proof that fastest known algorithm is in fact optimal)

That's not a very good example - square matrix multiplication is O(n^1.5) (where n is the input size) and extremely fast in practice.

(Though, as you say, there could still be an O(n) algorithm - this is not known).

What I said is true even for linear programming (a P-complete problem) - it has polynomial and efficient algorithms - though the latter are actually not polynomial in the worst case. :)

Re: P ≠ NP

#119

Post by long »

cdavidcash wrote: post #114
long wrote: post #86

Earlier quoted context omitted.

From what little I understand, those barriers prevent only certain proof strategies from working. So for instance, the Razborov-Rudich barrier concerns a class of combinatorial proofs (the so-called natural proofs); this paper uses two techniques - statistical mechanics and model theory - which I gather are out of the province of RR.

"only certain proof strategies" is technically correct, but its closer to "essentially every proof strategy we can conceive of". And besides, the question is over the entire proof strategy and not the specific techniques involved. It seems plausible that one could give a relativizing proof using some method of calculation from statistical mechanics, for example.

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

Re: P ≠ NP

#120

Post by angstrom »

shrikant wrote: post #73
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 :-)

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

And that doesn't even scratch the security implications. Cryptography based on complexity theory would become an instant relic. The only cryptography I know of that could stand up to a P vs NP solution is quantum cryptography. Of course, there's the distinct possibility the NSA and other government sponsored institutions are already aware of a solution.
Post reply on HN