On Sun, Dec 21, 2008 at 3:01 AM, Andrei Alexandrescu <[email protected]> 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 <[email protected]> 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
