NP=P

[Bill Baxter]

On Sun, Dec 21, 2008 at 3:01 AM, Andrei Alexandrescu
<SeeWebsiteForEmail at 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 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)

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