I think this is getting unwanted publicity. The author never released the proof in public or made any announcement. He only sent it to his expert friends so that they can point out potential flaws. May be this needs more research and putting him in spotlight is not helping anything.
P ≠ NP
191–200 of 233 posts
Re: P ≠ NP
#192Very 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…
If the proof works, he would easily get the Millenium prize and the Fields medal. Edit: Also the Goedel prize
Turing Award, too.
Re: P ≠ NP
#193Several 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…
[deleted]
Re: P ≠ NP
#194While 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.
I would note: "statistical mechanics" is not technique but a subfield of mathematics and physics within which a number of techniques are used.
"Model theory" might be closer to "a" technique or at least a somewhat distinct set of techniques.
And other have noted, there's reason that a proof from statistical mechanics would relativize.
Re: P ≠ NP
#195The two main consequences that would follow are (from Wikipedia): "A proof that showed that P ≠ NP, while lacking the practical computational benefits of a proof that P = NP, would also represent a very significant advance in computational complexity theory and provide guidance for future research. It would allow one to show in a formal way that many common problems cannot be solved efficiently, so that the attention…
The above is false (par for Wikipedia). While RSA is based on the difficulty of factoring, DES (and 3DES) are not. The DES cipher is based on substitution/permutation and not number theory.
Also, factoring is known to be subexponential (e.g., GNFS). While there is no known polynomial time factoring algorithm, this may give some evidence that the integer factorization problem might be in P. Factoring is known to not be NP-complete and we hope it is not in P. While a proof that P=NP would be disastrous for RSA, a proof that P!=NP does not mean factorization is guaranteed to be safe against future advances in algorithms.
In other words, proof that P!=NP would be an amazing result but someone could still improve factoring algorithms.
Re: P ≠ NP
#196Earlier quoted context omitted.
If this proof is up for review, that would mean there could be errors in it, right?
If a proof has been reviewed there might still be errors in it...
Indeed. But, fortunately, this is seldom a problem in math.
I mean, often people discover problems in proofs --- but if the result was beautiful enough, they are usually able to repair the proofs. It's like debugging. (And I mean it, thanks to the Curry-Howard isomorphism.)
Re: P ≠ NP
#197Earlier quoted context omitted.
Sometimes there are also flaws which can not be corrected. But I cannot make a qualified guess if this might be the case here.
Of course, but that's an even larger gamble, if you don't have at least a very specific hunch about the way in which a proof will fail. All in all, this announcement by Aaronson seems rather rash. I don't understand why he would do such a thing.
I am OK with it. He put his money where his mouth is, instead of just putting his mouth somewhere.
Re: P ≠ NP
#198Very 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.
Perhaps he could steal the Economics "Nobel" prize, like lots of other mathematicians have done.
There was a paper about how recognizing bad securities is a NP hard problem a while ago. So this is applicable. (Tongue-in-cheek.)
Re: P ≠ NP
#199I'd like to say congratulations to Vinay Deolalikar for getting to this point and putting the paper out there. As randomwalker and others have said, this appears to at least be a legitimate attempt. It must take some seriously thick skin to work on a paper that a) is in an area so full of failed attempts and error filled proofs; and b) that EVERYONE is going to read and try to tear apart.
Re: P ≠ NP
#200Earlier quoted context omitted.
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. :)
Can you give a reference for a matrix multiplication algorithm which is O(n^1.5) ? thanks.