Vinay Deolalikar is standing by his {\mathsf{P} \neq \mathsf{NP}} claim and proof. He and I have been exchanging e-mails, and as noted in the. Possible fatal flaws in the finite model part of Deolalikar’s proof Neil Immerman is one of the world’s experts on Finite Model Theory. He used. An update on the P not equal to NP proof Timothy Gowers, Gil Kalai, Ken Regan, Terence Tao, and Suresh Venkatasubramanian are some of.

Author: Shasho Kakus
Country: Spain
Language: English (Spanish)
Genre: Love
Published (Last): 16 May 2004
Pages: 401
PDF File Size: 16.62 Mb
ePub File Size: 16.29 Mb
ISBN: 185-3-80123-434-9
Downloads: 45750
Price: Free* [*Free Regsitration Required]
Uploader: Shakasa

I was just wondering…. If people had refrained from making public what had been communicated to them privately, and given him a chance to digest the feedback, maybe we would be looking at a more polished paper ddeolalikar of correctness.

Although, many-a-times, some people might have had historical distastes with intellectual debate, we need to realize that it can only benefit humanity in the long run especially when intelligence is modulated with the human spirit for collaboration and for understanding people and things.

Deolalikar Responds To Issues About His P≠NP Proof

Should they choose to follow his call which, once again, they are not compelled to doand find later that the promised panorama is not in their opinion up to the billing, surely the blame does not lie with the author.

Under 1, eventually some very powerful people will take a look, but when it is convenient for them. Namely, he points out that in certain phases there are exponential number of clusters. This is perhaps where we need new ideas.

More important is increased communication we can build, going forward, whether my perception is right or wrong. Not that you or me, for that matter, care much, but no mention of this big effort does not just sound right. This strongly suggests that property A cannot contain all problems in P. We agree in the encoding, fine.


Update on Deolalikar’s Proof that P≠NP

He might do it in his new draft. The solid non-trivial results about the space of solutions are of the kind cited as theorem 5.

I think you exaggerate a bit. It was obvious from the beginning that this was the problem. The author has chosen to reach a contradiction using random k-SAT. Then we immediately know this deolaljkar be false. In a poll of researchers, 61 believed the answer to be no, 9 believed the answer is yes, and 22 were unsure; 8 believed the question may be independent of the currently accepted axioms and therefore impossible to prove or disprove.

The space of algorithms is very large and we are only at the beginning of its exploration. What does polylog parameterisable mean?

After having a very weak and incorrect characterization of P, the proof could end in a variety of ways. So the diameter is 4, which means that the neighborhoods in the Gaifman graph include everything provided the radius is at least 2. Just as the class P is defined in terms of polynomial ceolalikar time, the class EXPTIME is the set of all decision problems that have exponential running time. It seemed highly unlikely but one could not dismiss it out of hand.

The reason is that it is not written in a clear mathematical or rigorous format. Leave a Reply Cancel reply Enter your comment here There are infinitely many subsets of k-SAT that are in P for instance, every finite subset is in P but which are not of the form that the dichotomy theorems apply to.

This seems to suggest, as I have done above, that the errors are first originating in the finite model theory sections but are only really manifesting themselves when those sections are applied to random k-SAT and thence to the complexity conclusions.


And if I am rude, and will not answer, and might happen that I did not transform it, your prospective algorithm will be in trouble. As I understand it, Neil is just pointing out that the stages of an LFP induction need not be order-invariant even if the result of the induction is. This page is derived from an earlier collaborative document created by Suresh Venkatasubramanian.

In the expression for potential, we have m clauses, and if each is given by this number of parameters, number of parameters is not exponential. All is well, this parametrization is easy, but nontrivial.

He and I have been exchanging e-mails, and as noted in the several comments, he has updated his paper several times. I think we all should thank you, Richard, for your enthusiasm in updating this blog, and your providing food for thought and a deolaliar for discussion.

P, NP, and the Search for the Impossible.

Update on Deolalikar’s Proof that P≠NP | Gödel’s Lost Letter and P=NP

So there does not appear to be a separation between SAT and P here. Many do fail for reasons which have been stated again and again. Second, without everyone being required to support and present their work carefully and rigorously, there is a bias in the review process whereby some researchers i. Now, this should not be a problem when k is a fixed constant.