4 ms·

Before anyone gets too excited, I would caution that there there is a long history of failed attempts at this problem, and an equally long history of premature

Before anyone gets too excited, I would caution that there there is a long history of failed attempts at this problem, and an equally long history of premature announcements. On the surface, here is what is encouraging about this one: - The author is a theory professional and not an amateur or a crank - The author frames this as a possible proof where he's seeking feedback on the method, rather than declaring a solution up front - The author builds on existing theory in a formerly mainstream approach that has been shown to have problems (circuit lower bounds) - Looks like a serious and well-considered proof effort Here is why HN should hold off on any excitement: - This style of proof was found to be unworkable in the past. In particular, approaches to proving circuit lower bounds in this manner were shown by Razborov and Rudich to be "natural proofs" in the 1990s, which is a category of proof strategy that cannot demonstrate P/NP. It's not explained why this strategy does not succumb to the same problem -- though the author surely has some reasoning around it. (see point 6 of Scott Aaronson's "8 signs a proposed P/NP proof is wrong": http://www.scottaaronson.com/blog/?p=458 http://www.scottaaronson.com/blog/?p=458. You might also see this comment from /r/math: http://www.reddit.com/r/compsci/comments/14mqqt/anyone_have_the_math_to_check_out_this_p_np_proof/c7elwbz http://www.reddit.com/r/compsci/comments/14mqqt/anyone_have_...) ). - There is a very good community framework for evaluating proposed solutions when the author's ready. Possibly the author has already submitted the work to a journal, but it's not clear that he's confident enough yet to invite more active discussion on his effort from the theory community. I can't find any discussion of it online. It's likely he's pursuing these on his own, and conceivably flaws have been found since the summer. - The author does not declare this as a completed solution in the same way that Deolikar did two years ago. In that case, his announcement led to an analysis by the theory community online that led to discovery of core errors. We can wait here 'til the author gives a bit more information. - This proof joins dozens of other announced solutions to P/NP in both directions (see, for example, http://www.win.tue.nl/~gwoegi/P-versus-NP.htm http://www.win.tue.nl/~gwoegi/P-versus-NP.htm) which emerge quite regularly, and close attention paid to each will leave no time for original research :)

vznvzn 14y ago
hi AK. maybe consider blogging about this? this is a well written but superficial analysis. scott aaronson insists on his blog that a proof should explain why it succeeds against "known barriers" eg razborov/rudich Natural Proofs. but this is really an optional requirement of a proof. moreover the actual barrier to "natural proofs" is very subtle and basically insists that a proof, if it exists, should have a certain "intrinsic complexity" in its constructions, and that many such constructions in the literature for class separations do not have this "intrinsic complexity". but new researchers are just suggesting that this only requires some new "intrinsic complexity" function that hasnt been seen before; but that such functions do exist, they just dont seem to be used in proofs that we know of. eminent authorities in the field such as Lipton have argued that the near 20yr old Natural Proofs may be overdramatized as a real barrier. here is liptons blog on the subj: http://rjlipton.wordpress.com/2009/03/25/whos-afraid-of-natural-proofs/ http://rjlipton.wordpress.com/2009/03/25/whos-afraid-of-natu... here is chow in AMS: "Nevertheless, it is my personal opinion that the optimistic approach is the right one; that is, the Razborov–Rudich result should be regarded as a hint, and not a barrier, to separating complex- ity classes. The only real barrier is our lack of imagination." http://www.ams.org/notices/201111/rtx111101586p.pdf http://www.ams.org/notices/201111/rtx111101586p.pdf
- anandkulkarni 14y ago
  I may have come across as insistent on clearly stating ways around the natural proofs barrier because this is Hacker News, where folks are liable to jump to conclusions, and not, say, http://cstheory.stackexchange.com http://cstheory.stackexchange.com. Given the large number of attempts against P vs. NP, frequently by folks who are not active in complexity theory, it's often better to try to understand these ideas on theory sites. You make an reasonable point, vis-a-vis Chow; rather than being regarded as an absolute barrier for lines of reasoning involving circuit complexity, the requirement of being a sufficiently complex proof may provide a jumping-off point for uncovering a working method.
vznvzn 14y ago
here chow elaborates further/in depth on the "natural" condition in the Razborov Rudich proof & finds some evidence for "nearby" functions that potentially could be used to defy the Razborov-Rudich natural proofs barrier: http://arxiv.org/pdf/0805.1385v3.pdf http://arxiv.org/pdf/0805.1385v3.pdf "By definition, a natural combinatorial property satisfies two conditions, constructivity and largeness. Our main re- sult is that if the largeness condition is weakened slightly, then not only does the Razborov–Rudich proof break down, but such “almost-natural” (and useful) properties provably exist."
vznvzn 14y ago
"its not clear that he's confident enough yet to invite more active discussion on his effort from the theory community". that is highly debatable; arguably that was his intent in creating the public blog and putting all the papers fully accessable on it-- to engage the online community, which somewhat regrettably hasnt happened much in the ~5 months its been online-- that site seems to be "undiscovered" until recently. furthermore, the author insists in his latest blog entry on aug 26th and in recent comments (within the last few days) that he sees no flaws in the proof & welcomes further feedback.

vznvzn 14y ago

hi AK. maybe consider blogging about this? this is a well written but superficial analysis. scott aaronson insists on his blog that a proof should explain why it succeeds against "known barriers" eg razborov/rudich Natural Proofs. but this is really an optional requirement of a proof. moreover the actual barrier to "natural proofs" is very subtle and basically insists that a proof, if it exists, should have a certain "intrinsic complexity" in its constructions, and that many such constructions in the literature for class separations do not have this "intrinsic complexity". but new researchers are just suggesting that this only requires some new "intrinsic complexity" function that hasnt been seen before; but that such functions do exist, they just dont seem to be used in proofs that we know of. eminent authorities in the field such as Lipton have argued that the near 20yr old Natural Proofs may be overdramatized as a real barrier. here is liptons blog on the subj: http://rjlipton.wordpress.com/2009/03/25/whos-afraid-of-natural-proofs/ http://rjlipton.wordpress.com/2009/03/25/whos-afraid-of-natu... here is chow in AMS: "Nevertheless, it is my personal opinion that the optimistic approach is the right one; that is, the Razborov–Rudich result should be regarded as a hint, and not a barrier, to separating complex- ity classes. The only real barrier is our lack of imagination." http://www.ams.org/notices/201111/rtx111101586p.pdf http://www.ams.org/notices/201111/rtx111101586p.pdf

anandkulkarni 14y ago
I may have come across as insistent on clearly stating ways around the natural proofs barrier because this is Hacker News, where folks are liable to jump to conclusions, and not, say, http://cstheory.stackexchange.com http://cstheory.stackexchange.com. Given the large number of attempts against P vs. NP, frequently by folks who are not active in complexity theory, it's often better to try to understand these ideas on theory sites. You make an reasonable point, vis-a-vis Chow; rather than being regarded as an absolute barrier for lines of reasoning involving circuit complexity, the requirement of being a sufficiently complex proof may provide a jumping-off point for uncovering a working method.

vznvzn 14y ago

here chow elaborates further/in depth on the "natural" condition in the Razborov Rudich proof & finds some evidence for "nearby" functions that potentially could be used to defy the Razborov-Rudich natural proofs barrier: http://arxiv.org/pdf/0805.1385v3.pdf http://arxiv.org/pdf/0805.1385v3.pdf "By definition, a natural combinatorial property satisfies two conditions, constructivity and largeness. Our main re- sult is that if the largeness condition is weakened slightly, then not only does the Razborov–Rudich proof break down, but such “almost-natural” (and useful) properties provably exist."

vznvzn 14y ago

"its not clear that he's confident enough yet to invite more active discussion on his effort from the theory community". that is highly debatable; arguably that was his intent in creating the public blog and putting all the papers fully accessable on it-- to engage the online community, which somewhat regrettably hasnt happened much in the ~5 months its been online-- that site seems to be "undiscovered" until recently. furthermore, the author insists in his latest blog entry on aug 26th and in recent comments (within the last few days) that he sees no flaws in the proof & welcomes further feedback.