Thread overview
NP=P
Dec 13, 2008
Knud Soerensen
Dec 13, 2008
BCS
Dec 13, 2008
Tim M
Dec 20, 2008
Bill Baxter
Dec 21, 2008
Wolfgang Draxinger
Dec 22, 2008
Mikola Lysenko
Dec 30, 2008
Knud Soerensen
December 13, 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/
December 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."


December 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."
>
>

December 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)
> 
> 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
December 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==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)

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

But these P=NP 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
December 21, 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

December 22, 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.
December 30, 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/