<p>In 1982, Barahona proved that <a href="http://iopscience.iop.org/0305-4470/15/10/028" rel="nofollow">finding the ground state of an Ising model is NP-hard</a>. Later, in 2000, Istrail proved that <a href="http://dl.acm.org/citation.cfm?id=335316" rel="nofollow">it is NP-complete</a>. When I look up the citations of these two papers using Google scholar, it appears that the previous and weaker result has <a href="http://scholar.google.com/scholar?hl=en&amp;q=On%20the%20computational%20complexity%20of%20Ising%20spin%20glass%20models&amp;btnG=&amp;as_sdt=1%2C21&amp;as_sdtp=" rel="nofollow">647</a> citations while on the other hand the more recent and stronger result has <a href="http://scholar.google.com/scholar?hl=en&amp;q=Statistical%20Mechanics%2C%20Three-Dimensionality%20and%20%20NP-completeness&amp;btnG=&amp;as_sdt=1%2C21&amp;as_sdtp=" rel="nofollow">109</a> citations.</p>

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

CC BY-SA 3.0
2014-11-11T23:47:09.900Z
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.
Sasho Nikolov
CC BY-SA 3.0
2014-11-11T23:51:02.133Z
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.
Sasho Nikolov
<np-hardness><np-complete><combinatorics><statistical-physics><citations>
Which complexity information of Ising model is more important?
Omar Shehab
# Which complexity information of Ising model is more important?

(Asked by: username_0 on 2014-11-11)

In 1982, Barahona proved that [finding the ground state of an Ising model is NP-hard](http://iopscience.iop.org/0305-4470/15/10/028). Later, in 2000, Istrail proved that [it is NP-complete](http://dl.acm.org/citation.cfm?id=335316). When I look up the citations of these two papers using Google scholar, it appears that the previous and weaker result has [647](http://scholar.google.com/scholar?hl=en&q=On%20the%20computational%20complexity%20of%20Ising%20spin%20glass%20models&btnG=&as_sdt=1%2C21&as_sdtp=) citations while on the other hand the more recent and stronger result has [109](http://scholar.google.com/scholar?hl=en&q=Statistical%20Mechanics%2C%20Three-Dimensionality%20and%20%20NP-completeness&btnG=&as_sdt=1%2C21&as_sdtp=) citations.

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

**Tags:** np-hardness, np-complete, combinatorics, statistical-physics, citations

> **Comments:**
> **username_1**: 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.  
> **username_1**: 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.  

---

## 0 answers

