Andrei Alexandrescu 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) > > > Andrei
Proving FP=#P is a far more grandiose claim than proving P = NP. To clarify: FP is the class of all *functions* that can be computed 'easily' (on a deterministic computer in polynomial time). It is a pretty simple generalization of, P, which is the class of easy *decision problems* (must have a yes/no answer.) While on the other hand: #P is the set of all functions which compute the number of solutions for problems in NP. For example, *counting* the number of Hamiltonian circuits in a graph is in #P, while simply *testing* if it has Hamiltonian circuit is in NP. If this were indeed true, it would have many screwy consequences, such as NP=coNP (but then again pretty much any hierarchy collapse would do the same thing.) Of course, most likely this is just noise.
