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?

Related closed MO posts:
When would you read a paper claiming to have settled a long open problem like $P$ vs. $NP$?

Discussion on meta:

  • $\begingroup$ "Does his approach avoid being a 'natural proof' in the sense of Razborov and Rudich?" would be a start. $\endgroup$ – Ryan Budney Aug 9 '10 at 8:27
  • 2
    $\begingroup$ Have you read it yourself? $\endgroup$ – Will Jagy Aug 9 '10 at 8:28
  • 22
    $\begingroup$ Kaveh, here is my suggestion: Read the paper first and only ask a technical question if you come across a difficulty that, after thinking about it for sufficient time, you cannot overcome. Also, please, remember that, as exciting as this new development might be, MO is not a seminar on Vinay Deolalikar's paper. $\endgroup$ – Victor Protsak Aug 9 '10 at 9:16
  • 5
    $\begingroup$ I think it more polite to let experts and the usual course of events decide whether specific parts of an unpublished work is correct or not. I think that MO is a terrible place to do this, in particular because anonymous and pseudonymous comments are possible. $\endgroup$ – Olivier Aug 9 '10 at 11:51
  • $\begingroup$ interesting question! fyi it seems one expected major/key way to approach P=?NP question from descriptive complexity theory would be Fagins thm but presumably Deolalikar did not go this route... also this post by aaronson Eight Signs A Claimed P≠NP Proof Is Wrong has a point or two relevant to the use of descriptive complexity in a P vs NP proof & this particular proof attempt/attack. $\endgroup$ – vzn Feb 18 '14 at 22:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.