I always felt that it was logical that N != NP. However, I certainly couldn't prove it.
P ≠ NP
131–140 of 233 posts
Re: P ≠ NP
#132Earlier quoted context omitted.
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 ."
I'm not academic - can you explain why he mentioned the font sizes? Why are they relevant?
[deleted]
Re: P ≠ NP
#133Proving P ≠ NP is like finding the Higgs Boson. It doesn't change anything and a lot of people spent a lot of time showing that they have spent a lot of time changing nothing.
Re: P ≠ NP
#134P = NP if and only if N = 1 or P = 0
Beat you to it! http://twitter.com/peterc/status/20667523417
I didn't post it here because I realized it's a joke most people won't get and those who do get it won't find it funny ;-) This joke could even be a Reddit vs HN shibboleth as I just saw it made there too and it's being voted up.
Re: P ≠ NP
#135Earlier quoted context omitted.
I hear this statement frequently when P = NP is discussed, but as someone not involved in computer science I have a hard time understanding it. Could you explain what some of those consequences be? Does P = NP really need to be proved to achieve those practical consequences? Can't it just be assumed to be true and then see what the result is?
If I remember correctly, any proof of P = NP would be have to be constructive, so it would immediately give us a fast algorithm for ALL NP-complete problems, as they can all be reduced to each other.
Not so. Pure existence proofs can be non-constructive.
The first historical example of an important proof which was non-constructive was Hilbert's Basis Theorem in 1888, which solved a famous problem posed by Paul Gordon. It is now viewed as in some sense being the first salvo in the debate over constructivism in the 20th century. See http://en.wikipedia.org/wiki/David_Hilbert#The_finiteness_th... for more.
Re: P ≠ NP
#136Several 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…
Another thing. It's known that a proof resolving P vs NP can't relativize, can't be "natural", and can't "algebrize". (See http://portal.acm.org/citation.cfm?id=1490272&dl=GUIDE&#... and its references for what this means.) The paper doesn't directly address how it avoids these barriers. It does mention the first two barriers in passing. Maybe the answer is obvious to anyone who could read this paper.
In a cursory reading, I think I can address these criticisms. Although one would have liked the author to call out each in his introduction.
Naturalization: This proof is not combinatorial, it is based on a model of formal logic. This is addressed by the author directly.
Relativization: This is proof by contradiction and relies on understanding the solution space of k-SAT instances, not on diagonalization.
Algebrization: This proof looks beyond the size of small circuit into how the circuit inputs interact and how this interaction spreads throughout the circuit.
Re: P ≠ NP
#137Earlier quoted context omitted.
Granted, but this author does not set off any crackpot flags: he's had plenty of prior publications in areas relevant to the proof and works in an industry research lab. Another poster points this out: http://news.ycombinator.com/item?id=1585999
Also, the paper was written using LaTeX. I have a friend who spent a semester helping to edit a small mathematics journal, and, with virtually 100% accuracy, you could tell the crackpot papers from the serious ones based simply on whether they used LaTeX or not.
Submissions in .doc format can also be immediately judged with near 100% accuracy.
Re: P ≠ NP
#138Earlier quoted context omitted.
I'm not sure if it is or isn't weird that he hasn't published on complexity theory. I recall Gasarch publishing a poll in SIGACT where a handful of the researchers polled claimed that it'll be resolved by someone outside of the field. Regardless, from reading the synopsis of the proof, I'm skeptical to the point of disinterest. (I apologize for not providing a link -- but the only URL I was able to find from Google:…
Why are you skeptical of the proof to "the point of disinterest"? I would assume that a researcher with HP with a dual Ph.D.s from USC wouldn't haphazardly make such a claim.
[deleted]
Re: P ≠ NP
#139Earlier quoted context omitted.
Yeah, I'd be curious to see what people who are still working in the field have to say. My red flags went up as soon as I read "statistical" in the abstract, since that could easily imply the common problem of assuming the existence of a secure PRNG. However, I haven't read the entire paper in depth (and likely won't have time to anytime soon), so I don't really know if that common trap was fallen into.
Statistical mechanics : http://en.wikipedia.org/wiki/Statistical_mechanics
"is the application of probability theory"
My comment still stands.
Re: P ≠ NP
#140Earlier 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.
I'd tend to agree...
Taking a methods from a different domain in no way shows that the mechanics of those method don't reduce to the same mechanics as a "natural proof". Further, it makes the actual process much more obscure.
Indeed, statistics in general seems like a hard approach for overcoming the Razborov-Rudich limit, since the limit is on showing that a "typical" function has certain properties and anything statical seems like it would be "typical".
But who knows really, maybe Razborov-Rudich isn't correct, since in fully generality it relies on things that "mathematicians generally believe" (the existence of certain pseudo-random functions) rather than things that are definitely proven - as far as I know.