Welcome to MathOverflow

Question

11

6

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:
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/

edited Aug 27 2010 at 12:39

asked Aug 9 2010 at 8:13

Kaveh
2,177●5●24

Could you rephrase your question? – Ryan Budney Aug 9 2010 at 8:17

@Ryan: Sure. How should I rephrase it? Do you have any specific suggestion on how to improve it? – Kaveh Aug 9 2010 at 8:22

2

Have you read it yourself? – Will Jagy Aug 9 2010 at 8:28

21

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. – Victor Protsak Aug 9 2010 at 9:16

5

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. – Olivier Aug 9 2010 at 11:51

show 7 more comments

sisko misko · Answer 1 · 2010-08-27 11:01:22Z UTC

-8

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

answered Aug 27 2010 at 11:01

sisko misko
1

3

This is not a helpful answer. If you care to look, the question was asked on August 9, before anyone had a clear idea about the proof. – Victor Protsak Aug 27 2010 at 11:13

3

I think you're being rather hard on Deolalikar here. It took an expert in descriptive complexity to find the fatal flaw in the proof. – Peter Shor Aug 27 2010 at 16:51

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.