Thread overview | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|
|
December 13, 2008 NP=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/ |
December 13, 2008 Re: NP=P | ||||
---|---|---|---|---|
| ||||
Posted in reply to Knud Soerensen | 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 Re: NP=P | ||||
---|---|---|---|---|
| ||||
Posted in reply to BCS | 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 Re: NP=P | ||||
---|---|---|---|---|
| ||||
Posted in reply to Tim M | 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 Re: NP=P | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | 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 Re: NP=P | ||||
---|---|---|---|---|
| ||||
Posted in reply to Tim M | 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 Re: NP=P | ||||
---|---|---|---|---|
| ||||
Posted in reply to Knud Soerensen | 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 Re: NP=P | ||||
---|---|---|---|---|
| ||||
Posted in reply to Knud Soerensen | 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/ |
Copyright © 1999-2021 by the D Language Foundation