Exercise b. Hard spin glasses. Physicists use a model called an Ising spin glass to study magnetic materials. We have a graph G = (V, E) and a function J : E → Z, where J(u, v) is the interaction strength of edge {u, v} ∈ E. A state is a function s : V → {−1, +1}. 1 The energy of a state s is H(s) = − P {u,v}∈E J(u, v) · s(u) · s(v).2 An edge {u, v} is called ferromagnetic if J(u, v) > 0, and antiferromagnetic if J(u, v) < 0. Ferromagnetic edges “pressure” u and v to be the same spin, and antiferromagnetic edges “pressure” them to be different. We wish to find the ground state, i.e., values of s(u) for each u ∈ V that minimize the energy. Phrased as a decision problem, we ask whether a state exists below a certain energy threshold: Spin-Glass Input: a graph G = (V, E), interaction strengths J : E → Z, and a threshold hˆ ∈ Z Question: is there a state s : V → {−1, +1} with H(s) ≤ hˆ? Show that Spin-Glass is NP-complete. 1Each s(u) is called the spin of u; if u is a magnetic domain, think of s(u) as its orientation: s(u) = +1 means it is pointed “up” and s(u) = −1 means it is pointed “down”. 2Note the negative sign: we are keeping convention with physics here in which “more negative” energies represent “more favorable states”. Equivalently, if there were no negative sign, we would ask for a maximum energy state
Exercise b. Hard spin glasses.
Physicists use a model called an Ising spin glass to study magnetic materials. We have
a graph G = (V, E) and a function J : E → Z, where J(u, v) is the interaction strength
of edge {u, v} ∈ E. A state is a function s : V → {−1, +1}.
1 The energy of a state
s is H(s) = −
P
{u,v}∈E
J(u, v) · s(u) · s(v).2 An edge {u, v} is called ferromagnetic if
J(u, v) > 0, and antiferromagnetic if J(u, v) < 0. Ferromagnetic edges “pressure” u
and v to be the same spin, and antiferromagnetic edges “pressure” them to be different.
We wish to find the ground state, i.e., values of s(u) for each u ∈ V that minimize the
energy. Phrased as a decision problem, we ask whether a state exists below a certain
energy threshold:
Spin-Glass
Input: a graph G = (V, E), interaction strengths J : E → Z, and a threshold hˆ ∈ Z
Question: is there a state s : V → {−1, +1} with H(s) ≤ hˆ?
Show that Spin-Glass is NP-complete.
1Each s(u) is called the spin of u; if u is a magnetic domain, think of s(u) as its orientation: s(u) = +1 means it
is pointed “up” and s(u) = −1 means it is pointed “down”.
2Note the negative sign: we are keeping convention with physics here in which “more negative” energies represent
“more favorable states”. Equivalently, if there were no negative sign, we would ask for a maximum energy state
**USE MAX-CUT to prove this
To show that SPIN-GLASS is NP-complete, we will reduce a known NP-complete problem to it. Consider the problem 3-SAT, which asks whether a given boolean formula can be satisfied by assigning binary values to its variables. We can reduce 3-SAT to SPIN-GLASS as follows.
Given a 3-SAT instance with variables x1, x2, ..., xn and clauses c1, c2, ..., cm, we construct a graph G = (V,E) as follows:
• For each variable xi, we add two vertices ui and vi to V.
• For each clause cj, we add three edges (uj,vj), (uj,vk), and (ul,vm) to E, where uj, vk, and vm are the two vertices associated with the variables appearing in cj.
• We set J(u, v) = -1 for all edges (u, v) € E.
It is easy to see that this graph has the desired properties: it is bipartite, and all its edges are antiferromagnetic. Moreover, it is easy to check that a state s is a valid assignment of {-1, +1} to the variables if and only if it has energy H(s) = -m. Thus, the 3-SAT instance is satisfiable if and only if the corresponding instance of SPIN-GLASS has a state of energy H(s) < -m.
This reduction shows that SPIN-GLASS is NP-complete, since 3-SAT is NP-complete.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
