www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - NP=P

reply Knud Soerensen <4tuu4k002 sneakemail.com> writes:
Lęs lige denne artikel

http://arxiv.org/abs/0812.1385
-- 
Crowdnews.eu - a social news site based on sharing instead of voting.
Follow me on CrowdNews http://crowdnews.eu/users/addGuide/42/
Dec 13 2008
next sibling parent reply BCS <ao pathlink.com> writes:
Reply to Knud,


 Lęs lige denne artikel
 
 http://arxiv.org/abs/0812.1385
 


If I'm reading that correctly, not exactly, the verbiage seems to imply that 
they didn't solve P=NP but a related problem.

"... these problems most of which are not believed to have even a polynomial 
time sequential algorithm."
Dec 13 2008
parent reply "Tim M" <a b.com> writes:
If they really did find proof that p==np wouldn't they be millionaires and  
probably should have kept it to themselves. (I haven't read that all the  
way through btw)

On Sun, 14 Dec 2008 08:43:48 +1300, BCS <ao pathlink.com> wrote:


 Reply to Knud,


 Lęs lige denne artikel
  http://arxiv.org/abs/0812.1385


 If I'm reading that correctly, not exactly, the verbiage seems to imply  
 that they didn't solve P=NP but a related problem.

 "... these problems most of which are not believed to have even a  
 polynomial time sequential algorithm."
Dec 13 2008
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Tim M wrote:

 If they really did find proof that p==np wouldn't they be millionaires 
 and probably should have kept it to themselves. (I haven't read that all 
 the way through btw)
 
 On Sun, 14 Dec 2008 08:43:48 +1300, BCS <ao pathlink.com> wrote:
 

 Reply to Knud,


 Lęs lige denne artikel
  http://arxiv.org/abs/0812.1385


 If I'm reading that correctly, not exactly, the verbiage seems to 
 imply that they didn't solve P=NP but a related problem.

 "... these problems most of which are not believed to have even a 
 polynomial time sequential algorithm."




The paper shows that #P=FP. I'm not that versed with theory to figure 
how important that result is.

http://en.wikipedia.org/wiki/Sharp-P
http://en.wikipedia.org/wiki/FP_(complexity)


Andrei
Dec 20 2008
parent "Bill Baxter" <wbaxter gmail.com> writes:
On Sun, Dec 21, 2008 at 3:01 AM, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:

 Tim M wrote:

 If they really did find proof that p=3D=3Dnp wouldn't they be millionair=




es and

 probably should have kept it to themselves. (I haven't read that all the=




 way

 through btw)

 On Sun, 14 Dec 2008 08:43:48 +1300, BCS <ao pathlink.com> wrote:


 Reply to Knud,


 L=E6s lige denne artikel
  http://arxiv.org/abs/0812.1385


 If I'm reading that correctly, not exactly, the verbiage seems to imply
 that they didn't solve P=3DNP but a related problem.

 "... these problems most of which are not believed to have even a
 polynomial time sequential algorithm."




 The paper shows that #P=3DFP. I'm not that versed with theory to figure h=


ow

 important that result is.

 http://en.wikipedia.org/wiki/Sharp-P
 http://en.wikipedia.org/wiki/FP_(complexity)


If the explanations on Wikipedia can be believed then #P=3DFP is still
pretty significant.
"""Clearly, a #P problem must be at least as hard as the corresponding
NP problem. """

But these P=3DNP type papers seem to come out every year or so then get
debunked.  This may be The One, but I'm not holding my breath.

--bb
Dec 20 2008
prev sibling parent Wolfgang Draxinger <wdraxinger darkstargames.de> writes:
Tim M wrote:


 If they really did find proof that p==np wouldn't they be
 millionaires and probably should have kept it to themselves. (I
 haven't read that all the way through btw)


Actually, to publish such a paper publically is the only method,
one can gain reputation in the mathematical world. And if you
want one of the prizes for mathematical achievment you've no
other choice.

Funny enough some years ago Perelman published a paper online in
which he proved Poincares conjecture, but then didn't want to
take the prize (Fields medal). The proof was also one of the
millenia problems, donated with 1 million dollars prize money,
but for that to claim it would had to be published in one of the
(offline) publications on mathematics.

http://en.wikipedia.org/wiki/Grigori_Perelman

Wolfgang
Dec 20 2008
prev sibling next sibling parent Mikola Lysenko <mikolalysenko gmail.com> writes:
Knud Soerensen Wrote:


 Lęs lige denne artikel
 
 http://arxiv.org/abs/0812.1385
 -- 
 Crowdnews.eu - a social news site based on sharing instead of voting.
 Follow me on CrowdNews http://crowdnews.eu/users/addGuide/42/


I'd be a bit skeptical in this cases.  Usually 3-4 papers like this show up on
arxiv every month.  Most of them are just confused, but well-meaning, amateurs.
 Part of the problem is that it is very easy to get confused in this area, as
many of the key arguments are quite subtle (I've even seen tenured professors
get time complexity completely wrong).

Given that the author of that paper has no academic credentials or publications
outside of this single article (which has not been peer-reviewd), I would say
that the veracity of these claims has not yet been scrutinized to the level
where I would be comfortable asserting P=NP.
Dec 22 2008
prev sibling next sibling parent Mikola Lysenko <mikolalysenko gmail.com> writes:
Andrei Alexandrescu Wrote:


 Tim M wrote:

 If they really did find proof that p==np wouldn't they be millionaires 
 and probably should have kept it to themselves. (I haven't read that all 
 the way through btw)
 
 On Sun, 14 Dec 2008 08:43:48 +1300, BCS <ao pathlink.com> wrote:
 

 Reply to Knud,


 Lęs lige denne artikel
  http://arxiv.org/abs/0812.1385


 If I'm reading that correctly, not exactly, the verbiage seems to 
 imply that they didn't solve P=NP but a related problem.

 "... these problems most of which are not believed to have even a 
 polynomial time sequential algorithm."




 
 The paper shows that #P=FP. I'm not that versed with theory to figure 
 how important that result is.
 
 http://en.wikipedia.org/wiki/Sharp-P
 http://en.wikipedia.org/wiki/FP_(complexity)
 
 
 Andrei


Proving FP=#P is a far more grandiose claim than proving P = NP.

To clarify:

FP is the class of all *functions* that can be computed 'easily' (on a
deterministic computer in polynomial time).  It is a pretty simple
generalization of, P, which is the class of easy *decision problems* (must have
a yes/no answer.)



While on the other hand:

#P is the set of all functions which compute the number of solutions for
problems in NP.  For example, *counting* the number of Hamiltonian circuits in
a graph is in #P, while simply *testing* if it has Hamiltonian circuit is in NP.


If this were indeed true, it would have many screwy consequences, such as
NP=coNP (but then again pretty much any hierarchy collapse would do the same
thing.)  Of course, most likely this is just noise.
Dec 22 2008
prev sibling parent Knud Soerensen <4tuu4k002 sneakemail.com> writes:
Sorry, about this off tropic post.

I meant to send it to my brother which have done some research on NP=P.



Knud Soerensen wrote:

 Lęs lige denne artikel
 
 http://arxiv.org/abs/0812.1385


-- 
Crowdnews.eu - a social news site based on sharing instead of voting.
Follow me on CrowdNews http://crowdnews.eu/users/addGuide/42/
Dec 30 2008