NP=P

[Mikola Lysenko]

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

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.