mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2010-08-10, 01:12   #12
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

991010 Posts
Default

There are some minor word changes and a ~200-word paragraph added before Remark 7.8.
Batalov is offline   Reply With Quote
Old 2010-08-10, 01:20   #13
joblack
 
joblack's Avatar
 
Oct 2008
n00bville

2·5·73 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
joblack is offline   Reply With Quote
Old 2010-08-10, 01:28   #14
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,981 Posts
Default

Quote:
Originally Posted by joblack View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2010-08-10, 01:35   #15
joblack
 
joblack's Avatar
 
Oct 2008
n00bville

2×5×73 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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'.
joblack is offline   Reply With Quote
Old 2010-08-10, 01:43   #16
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

D1B16 Posts
Default

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. "
ATH is offline   Reply With Quote
Old 2010-08-10, 04:53   #17
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2×3×13×83 Posts
Default Just fancy that...

(As Private Eye magazine would say):

Quote:
Originally Posted by R.D. Silverman View Post
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 View Post
I have started reading it in details. The general approach is very creative
and seems to be workable.
davieddy is offline   Reply With Quote
Old 2010-08-10, 07:02   #18
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

EAA16 Posts
Default

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
only_human is offline   Reply With Quote
Old 2010-08-10, 14:54   #19
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

2×1,877 Posts
Default 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
only_human is offline   Reply With Quote
Old 2010-08-10, 23:19   #20
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

5×1,493 Posts
Default

Quote:
Originally Posted by only_human View Post
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
R.D. Silverman is offline   Reply With Quote
Old 2010-08-11, 01:14   #21
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

2·1,877 Posts
Default

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.
only_human is offline   Reply With Quote
Old 2010-08-12, 05:11   #22
AntonVrba
 
AntonVrba's Avatar
 
Jun 2005

2×72 Posts
Default

Now also in the BBC news:

http://www.bbc.co.uk/news/science-environment-10938302
AntonVrba is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
News gd_barnes No Prime Left Behind 257 2022-08-10 06:28
News gd_barnes Conjectures 'R Us 304 2022-04-19 23:07
Other news Cruelty Riesel Prime Search 41 2010-03-08 18:46
The news giveth, the news taketh away... NBtarheel_33 Hardware 17 2009-05-04 15:52
News KEP Riesel Base 3 Attack 4 2008-12-17 11:54

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


Fri Aug 19 21:13:44 UTC 2022 up 1 day, 18:42, 0 users, load averages: 2.11, 2.30, 2.04

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔