NP=P

[Andrei Alexandrescu]

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