mersenneforum.org P!=NP in the news
 Register FAQ Search Today's Posts Mark Forums Read

 2010-08-10, 01:12 #12 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2×11×457 Posts There are some minor word changes and a ~200-word paragraph added before Remark 7.8.
2010-08-10, 01:20   #13
joblack

Oct 2008
n00bville

10111000002 Posts

Quote:
 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 Silvermans statements have, as always, no serious impact on reality.

2010-08-10, 01:28   #14
CRGreathouse

Aug 2006

5,987 Posts

Quote:
 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 Silvermans 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.

2010-08-10, 01:35   #15
joblack

Oct 2008
n00bville

25·23 Posts

Quote:
 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'.

 2010-08-10, 01:43 #16 ATH Einyen     Dec 2003 Denmark 2·17·101 Posts 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. "
2010-08-10, 04:53   #17
davieddy

"Lucan"
Dec 2006
England

11001010010102 Posts
Just fancy that...

(As Private Eye magazine would say):

Quote:
 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.
Quote:
 Originally Posted by R.D. Silverman I have started reading it in details. The general approach is very creative and seems to be workable.

 2010-08-10, 07:02 #18 only_human     "Gang aft agley" Sep 2002 2×1,877 Posts 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. Last fiddled with by only_human on 2010-08-10 at 07:29 Reason: trimmed a bit
2010-08-10, 14:54   #19
only_human

"Gang aft agley"
Sep 2002

2×1,877 Posts
Wiki

http://michaelnielsen.org/polymath1/..._P!%3DNP_paper
Quote:
 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

2010-08-10, 23:19   #20
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts

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

 2010-08-11, 01:14 #21 only_human     "Gang aft agley" Sep 2002 2×1,877 Posts 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.
 2010-08-12, 05:11 #22 AntonVrba     Jun 2005 2×72 Posts Now also in the BBC news: http://www.bbc.co.uk/news/science-environment-10938302

 Similar Threads Thread Thread Starter Forum Replies Last Post gd_barnes Conjectures 'R Us 305 2023-01-21 13:53 gd_barnes No Prime Left Behind 258 2023-01-21 11:09 Cruelty Riesel Prime Search 41 2010-03-08 18:46 NBtarheel_33 Hardware 17 2009-05-04 15:52 KEP Riesel Base 3 Attack 4 2008-12-17 11:54

All times are UTC. The time now is 20:13.

Wed Feb 1 20:13:44 UTC 2023 up 167 days, 17:42, 0 users, load averages: 1.22, 0.95, 0.95