How can an approach to $P$ vs $NP$ based on descriptive complexity avoid being a natural proof in the sense of Raborov-Rudich?

2010-08-09T08:13:51Z

EDIT: This question has been modified to make it a stand-alone question. Feel free to retract your votes for the previous version.

Here are Vinay Deolalikar's paper, and Richard Lipton's first post about it, and the wiki page on polymath site summarizing the discussions about it. His approach is based on descriptive complexity.

One of famous barriers for separating $NP$ from $P$ is Razborov-Rudich Natural Proofs 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:

How essential is the uniformity of $P$ to his proof?

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.)

So here is my questions:

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)?

How can an approach to $P$ vs $NP$ based on descriptive complexity avoid being a natural proof in the sense of Raborov-Rudich?

A related question is:

What are the complexity results using uniformity in an essential way other than proofs by diagonalization?

Discussion on meta:
http://meta.mathoverflow.net/discussion/590/whats-wrong-with-this-proof/

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?

2010-08-27T11:01:22Z

His proof is wrong. Completely. It makes no sense whatsoever. Haven't you heard?

How can an approach to $P$ vs $NP$ based on descriptive complexity avoid being a natural proof in the sense of Raborov-Rudich? - MathOverflow

How can an approach to $P$ vs $NP$ based on descriptive complexity avoid being a natural proof in the sense of Raborov-Rudich?

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?