How can an approach to \$P\$ vs \$NP\$ based on descriptive complexity avoid being a natural proof in the sense of Raborov-Rudich? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T08:03:34Z http://mathoverflow.net/feeds/question/34980 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/34980/how-can-an-approach-to-p-vs-np-based-on-descriptive-complexity-avoid-being-a How can an approach to \$P\$ vs \$NP\$ based on descriptive complexity avoid being a natural proof in the sense of Raborov-Rudich? Kaveh 2010-08-09T08:13:51Z 2010-08-27T12:39:39Z <p><strong>EDIT:</strong> This question has been modified to make it a stand-alone question. Feel free to retract your votes for the previous version.</p> <p>Here are Vinay Deolalikar's <a href="http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf" rel="nofollow">paper</a>, and Richard Lipton's first <a href="http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/" rel="nofollow">post</a> about it, and the <a href="http://michaelnielsen.org/polymath1/index.php?title=Deolalikar%27s_P!%3DNP_paper" rel="nofollow">wiki</a> page on polymath site summarizing the discussions about it. His approach is based on descriptive complexity.</p> <p>One of famous barriers for separating \$NP\$ from \$P\$ is Razborov-Rudich <a href="http://en.wikipedia.org/wiki/Natural_proof" rel="nofollow">Natural Proofs</a> barrier. Richard Lipton remarked about his paper and the natural proofs barrier that apparently "it exploits a uniform characterization of P that may not extend to give lower bounds against circuits". A question which is mentioned in one of the comments on Lipton's post is:</p> <blockquote> <p>How essential is the uniformity of \$P\$ to his proof? </p> </blockquote> <p>i.e is the uniformity of \$P\$ used in such an essential way that the barrier will not apply to it? (By essential I mean that the proof does not work for the non-uniform version.)</p> <p>So here is my questions:</p> <blockquote> <p>Are there any previous computational complexity results based on descriptive complexity that avoid the Razborov-Rudich natural proofs barrier (because of being based on descriptive complexity)?</p> <p>How can an approach to \$P\$ vs \$NP\$ based on descriptive complexity avoid being a natural proof in the sense of Raborov-Rudich?</p> </blockquote> <p>A related question is:</p> <blockquote> <p>What are the complexity results using uniformity in an essential way other than proofs by diagonalization?</p> </blockquote> <hr> <p>Related closed MO posts:<br/> <a href="https://mathoverflow.net/questions/34947/when-would-you-read-a-paper-claiming-to-have-settled-a-long-open-problem-like-p" rel="nofollow">https://mathoverflow.net/questions/34947/when-would-you-read-a-paper-claiming-to-have-settled-a-long-open-problem-like-p</a> <br/> <a href="https://mathoverflow.net/questions/34953/whats-wrong-with-this-proof-closed" rel="nofollow">https://mathoverflow.net/questions/34953/whats-wrong-with-this-proof-closed</a><br/></p> <p>Discussion on meta:<br/> <a href="http://meta.mathoverflow.net/discussion/590/whats-wrong-with-this-proof/" rel="nofollow">http://meta.mathoverflow.net/discussion/590/whats-wrong-with-this-proof/</a></p> http://mathoverflow.net/questions/34980/how-can-an-approach-to-p-vs-np-based-on-descriptive-complexity-avoid-being-a/36871#36871 Answer by sisko misko for How can an approach to \$P\$ vs \$NP\$ based on descriptive complexity avoid being a natural proof in the sense of Raborov-Rudich? sisko misko 2010-08-27T11:01:22Z 2010-08-27T11:01:22Z <p>His proof is wrong. Completely. It makes no sense whatsoever. Haven't you heard?</p>