View mode: basic / threaded / horizontal-split · Log in · Help
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
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
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
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
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
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
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
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/
Top | Discussion index | About this forum | D home