In 1982, Barahona proved that finding the ground state of an Ising model is NP-hard. Later, in 2000, Istrail proved that it is NP-complete. When I look up the citations of these two papers using Google scholar, it appears that the previous and weaker result has 647 citations while on the other hand the more recent and stronger result has 109 citations.

Shouldn't it be the other way round? Isn't a stronger result more useful?

  • 1
    $\begingroup$ Actually, Istrail seems to misuse the term NP-complete by applying it to function problems. Finding the ground state of an Ising model is an NP optimization problem, and natural decision versions are trivially in NP, so the real challenge is to show NP-hardness. Barahona does this for the 3D lattice, and Istrail does it for more general non-planar lattices. $\endgroup$ Nov 11, 2014 at 23:47
  • 6
    $\begingroup$ I am not sure your citations question can be objectively answered. But let me offer some non-expert speculation. Barahona's paper is from 1982 while Istrail's is from 2000. Also, if the special case was a breakthrough result (i.e. first to show hardness of solving a natural statistical mechanics model) or if it already captures what most people care about, it is no big surprise if it got more citations. $\endgroup$ Nov 11, 2014 at 23:51


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.