• Mikola Lysenko <mikolalysenko gmail.com> Dec 22 2008

Mikola Lysenko <mikolalysenko gmail.com> writes:

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