P!=NP in the news

[Batalov]

There are some minor word changes and a ~200-word paragraph added before Remark 7.8.

[joblack]

Originally Posted by R.D. Silverman

The wording of the announcement makes it clear that this is
not the effort of a professional. (too much hyperbole and
informality) It is very unlikely to be correct.

LOL - always the same unmannered Silverman behavior. Heise News Service has written that he is quite established in his field so Silverman`s statements have, as always, no serious impact on reality.

[CRGreathouse]

Originally Posted by joblack

LOL - always the same unmannered Silverman behavior. Heise News Service has written that he is quite established in his field so Silverman`s statements have, as always, no serious impact on reality.

At least we know what he really thinks.

But if you look at his more recent posts, Silverman has softened considerably on the paper.

[joblack]

Originally Posted by CRGreathouse

At least we know what he really thinks.
But if you look at his more recent posts, Silverman has softened considerably on the paper.

He had no choice after it was apparent that the paper is more than 'a bad introduction'.

[ATH]

The author Vinay Deolalikar writes that this version is preliminary version and was not meant for the public and final version is coming soon.

http://www.hpl.hp.com/personal/Vinay_Deolalikar/

"BASIC RESEARCH

Vinay Deolalikar. P is not equal to NP. 6th August, 2010 (66 pages 10pt, 102 pages 12pt). Manuscript sent on 6th August to several leading researchers in various areas. Confirmations began arriving 8th August early morning. The preliminary version made it to the web without my knowledge. I have made minor updates, here. Please note that the final version of the paper is under preparation, and is to be posted here very shortly. Stay tuned. "

[davieddy]

(As Private Eye magazine would say):

Originally Posted by R.D. Silverman

The wording of the announcement makes it clear that this is
not the effort of a professional. (too much hyperbole and
informality) It is very unlikely to be correct.

Originally Posted by R.D. Silverman

I have started reading it in details. The general approach is very creative
and seems to be workable.

[only_human]

Some preliminary analysis and organization by Dick Lipton and Ken Regan: http://rjlipton.wordpress.com/2010/0...-p%E2%89%A0np/ . This enumerates four possible issues with the proof for ease of discussion.

[only_human]

http://michaelnielsen.org/polymath1/..._P!%3DNP_paper

Deolalikar's P!=NP paper

From Polymath1Wiki
Note: This is currently an UNOFFICIAL page on Deolalikar's P!=NP paper, and is not yet affiliated with a Polymath project.
This is a clearinghouse wiki page for the analysis of Vinay Deolalikar's recent preprint claiming to prove that P != NP, and to aggregate various pieces of news and information about this paper. Corrections and new contributions to this page are definitely welcome. Of course, any new material should be sourced whenever possible, and remain constructive and objectively neutral; in particular, personal subjective opinions or speculations are to be avoided. This page is derived from an earlier collaborative document created by Suresh Venkatasubramanian.
For the latest discussion on the technical points of the paper, see this thread of Dick Lipton and Ken Regan. For meta-discussion of this wiki (and other non-mathematical or meta-mathematical issues), see this thread of Suresh Venkatasubramanian

[R.D. Silverman]

Originally Posted by only_human

http://michaelnielsen.org/polymath1/..._P!%3DNP_paper

Charanjit Jutla
August 10, 2010 9:50 am


Serious (unfixable) problem.


Vinay uses FO(LFP) as his main tool. However, I think
he fails to realize that FO(LFP) , although defined using
least fixed point, also contains greatest fixed points.


Thus, if \mu x f(y,x) is the formula denoting least fixpont of f(y,x) under
x,
and \nu x f(y,x) is the formula denoting greatest fixpont of f(y,x0 undex x,


then there is this triple negation rule:


\neg \mu x \neg f(y, \neg x) = \nu x f(y,x). (See Kozen's
paper on axiomatizing Mu-Calculus, or my paper with
Allen Emerson on Mu-Calculus in FOCS 1991 titled
"Mu-Calcus, Tree Automata and Determinacy", or just
original Vardi and Immerman papers). Note that the left
hand side is well defined in LFP, as x is under even
number of negations from the operator \mu.


Now, his whole theory of least fixed point only increasing
the size of the structures falls apart. BTW, this is a usual
mistake most people new to fixed-point logics fall prey to.


For example, now he has to deal with formulas of the kind
\nu x (f(y, x) \and g(y, x)).


His section 4.2 deals with just one least fixed point operator.
where his idea is correct.


But, in the next section 4.3, where he deals with complex
fixed point iterations, he is just hand waving, and possibly
way off. Given that he does not even mention greatest fixed
points leads me to think that this is a huge (unfixable) gap.


Charanjit Jutla
IBM T.J. Watson

[only_human]

I was fascinated watching the developing evaluation of the paper. A preliminary consensus seems complete. Here is a blog that takes an optimistic view of this new form of peer review: http://cameronneylon.net/blog/p-%E2%...f-peer-review/ Perhaps blitz-read is a more apt term.

Among my peripatetic browsing about all of this I came across Leslie Valiant's theory of holographic algorithms which exponentially speed up some computations; this was very interesting to me. There is a (mod 7) operation that seems to be part of canceling a large part of the calculations -- leaving a simpler system to be counted (and that by some kind of weighing). It reminded me a bit of the AKS method so simplifying a row.

[AntonVrba]

Now also in the BBC news:

http://www.bbc.co.uk/news/science-environment-10938302