2
$\begingroup$

I've been told recently that one can use the Ising model can find solutions to certain NP-hard problems, such as Clique, although it doesn't do so in polynomial time.

Googling gets a few Arxiv results but where might I find an introduction to this interesting relationship?

$\endgroup$
2
$\begingroup$

Finding the minimal energy configuration in the Ising model is NP-hard, and many problems can be directly reduced to it. For a list, including Karp's original 21 NP-hard problem see e.g. Ising formulations of many NP problems. The Ising model is also equivalent to unconstrained quadratic binary optimization which also can be used to model a large number of other NP-complete problems, see e.g. A unified modeling and solution framework for combinatorial optimization problems.

$\endgroup$
  • $\begingroup$ Awesome thank you ! $\endgroup$ – Craig May 28 at 16:51

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.