## digitalmars.D.announce - NP=P

- Knud Soerensen (5/5) Dec 13 2008 Lęs lige denne artikel...
- BCS (5/9) Dec 13 2008 If I'm reading that correctly,...
- Tim M (4/12) Dec 13 2008 If they really did find proof ...
- Andrei Alexandrescu (6/23) Dec 20 2008 The paper shows that #P=FP. I'...
- Bill Baxter (12/35) Dec 20 2008 es and...
- Wolfgang Draxinger (13/16) Dec 20 2008 Actually, to publish such a pa...
- Mikola Lysenko (3/9) Dec 22 2008 I'd be a bit skeptical in this...
- Mikola Lysenko (7/34) Dec 22 2008 Proving FP=#P is a far more gr...
- Knud Soerensen (6/9) Dec 30 2008 Sorry, about this off tropic p...

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

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

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

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 andprobably should have kept it to themselves. (I haven't read that all the=

waythrough 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=

owimportant 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

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

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

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

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