## digitalmars.D.announce - NP=P

- Knud Soerensen <4tuu4k002 sneakemail.com> Dec 13 2008
- BCS <ao pathlink.com> Dec 13 2008
- Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Dec 20 2008
- Wolfgang Draxinger <wdraxinger darkstargames.de> Dec 20 2008
- "Tim M" <a b.com> Dec 13 2008
- "Bill Baxter" <wbaxter gmail.com> Dec 20 2008
- Mikola Lysenko <mikolalysenko gmail.com> Dec 22 2008
- Knud Soerensen <4tuu4k002 sneakemail.com> Dec 30 2008

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

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

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

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

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

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=

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

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=

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

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

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