MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 5 fixed grammer

EDIT: this 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 also 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?

Related closed MO posts:
https://mathoverflow.net/questions/34947/when-would-you-read-a-paper-claiming-to-have-settled-a-long-open-problem-like-p
https://mathoverflow.net/questions/34953/whats-wrong-with-this-proof-closed

Discussion on meta:
http://meta.mathoverflow.net/discussion/590/whats-wrong-with-this-proof/
show/hide this revision's text 4 improved fromatting

Regarding Vinay Deolalikar's How can an approach to $P \neq P$ vs $NP$ . Does his approach based on descriptive complexity avoid being a 'natural proof ' in the sense of Razborov and RudichRaborov-Rudich?

Here is

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

Vinay Deolalikar's paper, and Richard Lipton's post about it. Steve Cook has remarked that "this appears to be a relatively serious claim to have solved P vs NP", and the wiki page on polymath site summarizing 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. My question is

Does his approach avoid being a 'natural proof' in the sense of Razborov and Rudich?

EDITRichard Lipton remarks remarked that apparently "it exploits a uniform characterization of P that may not extend to give lower bounds against circuits". So a little more specific A question (which is also mentioned in one of the comments on Lipton's post ) isthe following:

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

A related question

i.e is

What are the complexity results using uniformity of $P$ used in such an essential way other than proofs by diagonalizationthat the barrier will not apply to it? (By essential I mean that the proof does not work for the non-uniform version.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?

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?
show/hide this revision's text 3 fixed grammar

Here is Vinay Deolalikar's paper, and Richard Lipton's post about it. Steve Cook has remarked that "this appears to be a relatively serious claim to have solved P vs NP".

One of famous barriers for separating $NP$ from $P$ is Razborov-Rudich Natural Proofs barrier. My question is

Does his approach avoid being a 'natural proof' in the sense of Razborov and Rudich?

EDIT

Lipton remarks that apparently "it exploits a uniform characterization of P that may not extend to give lower bounds against circuits". So a little more specific question (which is also mentioned in one of the comments on Lipton's post) is the following:

How essential is the uniformity of P to his proof?

A related question is

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

By essential I mean that the proof does not work for the non-uniform version.

Related closed MO posts:
https://mathoverflow.net/questions/34947/when-would-you-read-a-paper-claiming-to-have-settled-a-long-open-problem-like-p
https://mathoverflow.net/questions/34953/whats-wrong-with-this-proof-closed

Discussion on meta:
http://meta.mathoverflow.net/discussion/590/whats-wrong-with-this-proof/
show/hide this revision's text 2 added 697 characters in body; edited title
show/hide this revision's text 1