Skip to main content
added 3 characters in body
Source Link
user76284
  • 2.2k
  • 15
  • 24

The Ising model is NP-complete for $d \geq 3$ but not $d < 2$$d \leq 2$.

The Ising Model Is NP-Complete. SIAM News, Volume 33, Number 6:

The three-dimensional spin glass model for the standard square lattice [is] NP-complete. More precisely, for the three-dimensional result, Barahona showed that a graph-theoretic problem known to be NP-complete—the task of finding a maximum set of independent edges (i.e., with no vertices in common) in a graph for which each vertex has degree 3—can be reduced to the problem of finding a ground state for the three-value coupling constant ($J_{ij}$ = –1, 0, or 1) on a cubic grid.

The Ising model is NP-complete for $d \geq 3$ but not $d < 2$.

The Ising Model Is NP-Complete. SIAM News, Volume 33, Number 6:

The three-dimensional spin glass model for the standard square lattice [is] NP-complete. More precisely, for the three-dimensional result, Barahona showed that a graph-theoretic problem known to be NP-complete—the task of finding a maximum set of independent edges (i.e., with no vertices in common) in a graph for which each vertex has degree 3—can be reduced to the problem of finding a ground state for the three-value coupling constant ($J_{ij}$ = –1, 0, or 1) on a cubic grid.

The Ising model is NP-complete for $d \geq 3$ but not $d \leq 2$.

The Ising Model Is NP-Complete. SIAM News, Volume 33, Number 6:

The three-dimensional spin glass model for the standard square lattice [is] NP-complete. More precisely, for the three-dimensional result, Barahona showed that a graph-theoretic problem known to be NP-complete—the task of finding a maximum set of independent edges (i.e., with no vertices in common) in a graph for which each vertex has degree 3—can be reduced to the problem of finding a ground state for the three-value coupling constant ($J_{ij}$ = –1, 0, or 1) on a cubic grid.

Source Link
user76284
  • 2.2k
  • 15
  • 24

The Ising model is NP-complete for $d \geq 3$ but not $d < 2$.

The Ising Model Is NP-Complete. SIAM News, Volume 33, Number 6:

The three-dimensional spin glass model for the standard square lattice [is] NP-complete. More precisely, for the three-dimensional result, Barahona showed that a graph-theoretic problem known to be NP-complete—the task of finding a maximum set of independent edges (i.e., with no vertices in common) in a graph for which each vertex has degree 3—can be reduced to the problem of finding a ground state for the three-value coupling constant ($J_{ij}$ = –1, 0, or 1) on a cubic grid.

Post Made Community Wiki by user76284