Are spin-glass problems NP (-complete)?

Question

It is well known that finding ground states for spin-glass systems (Ising, XY...) is NP-hard (at least as hard as the hardest NP-problems) so that they can be efficiently used to solve other NP problems like the Traveling Salesman Problem.

My question is: is the problem NP-complete? This seems to be what is claimed here. To my understanding, this would mean that apart from NP-hard, the problem is NP itself. But I don't know an obvious algorithm to check if a given solution is the true ground state in polynomial time? And actually, I think that a similar argument can be made for the traveling salesman problem.

Answer 1

Background

Computational problems come in a variety of types, for example:

• decision problem: given input $x$, output "YES" if $x$ belongs to a fixed set $L$ and output "NO" otherwise,
• function problem: given input $x$, output a $y$ such that $(x, y)$ belongs to a fixed relation $R$,
• optimization problem: given objective $f$ and constraints $g$, output $x$ that maximizes $f$ while satisfying $g$,
• sampling problem: given a probability distribution $P$, output a sample $x\sim P$.

Together with the computational model and resource bounds, the type of relevant problems is a key ingredient in a definition of a computational complexity class.

Traveling Salesman Problem

The class NP is defined as a class of decision problems. The Traveling Salesman Problem formulated as the task of finding the shortest loop traversing all nodes in a graph exactly once is a function problem and thus - as you suspected in your question - does not belong to NP. However, TSP has a decision version which for a given graph and a threshold length $w$ asks whether there is a loop traversing all nodes in the graph exactly once and whose total length is less than $w$. This problem belongs to NP. The certificate is the path and it is easy to see that it can be checked in polynomial time on a deterministic Turing machine.

Spin glasses

Similarly, the problem of finding the ground state of a spin glass system is a function problem and hence not in NP. The problem has a decision variant which for a given spin glass system and an energy threshold $E$ asks whether there is an energy eigenstate with energy below $E$. Under certain assumptions about the Hamiltonian, this problem belongs to NP.

For example, in the absence of a transversal field, the Ising model is diagonal in a product basis and thus has a product eigenstate for every eigenvalue. Each product state admits a description of size polynomial in the number of sites. We can use such a state as a certificate that can be checked in polynomial time to prove that the model has a state with energy below the threshold $E$.

Terminology

The expression "TSP is NP-complete" is an imprecise shortcut for "the decision version of TSP is NP-complete". Leaving "decision version" implicit is generally acceptable because only decision problems may be meaningfully declared to be NP-complete.

That said, note that it does make sense to say that a computational problem $P$ which is not a decision problem is NP-hard. See Wikipedia for an explanation.

Answer 2

Adam gave an excellent answer explaining that the "decision version" of the Ising model could be considered NP-complete, but the term doesn't make sense without that extra context.

I'll answer some of the other parts which I think were not yet addressed:

"But I don't know an obvious algorithm to check if a given solution is the true ground state in polynomial time?"

If you are given a solution to an arbitrary Ising model, for example: 001100110...01101 where 0 means spin-up and 1 means spin-down, there is no way in general to know that it is the true ground state, without checking all $2^n$ possible solutions, which means it can't be done in polynomial time with respect to the number of spins $n$. If you have a very specific Ising model, for example the one where there's no linear terms and all couplings between the spins are negative in strength, then you can find the ground state in polynomial time, but there's no way to verify that a solution is the true ground state in polynomial time in general.

Finally, since you talked about spin-glass systems in general (not just the Ising model, as you specifically mentioned the XY model which unlike the Ising model is not diagonal), I'll mention that the 2-local Hamiltonian problem is QMA-complete, which is the analog of NP-completeness, for when you have access to a quantum computer. Any Hamiltonian can be decomposed into a sum of products of spin-matrices, which describes a k-local spin-glass. It was proven that finding the ground state energy of the k-local Hamiltonian accurately is QMA-complete long before the more strong result in that paper I linked earlier, which shows that 2-local Hamiltonians are enough (you don't even need k-local interactions).

In fact, the 2D Ising model with transverse fields is universal, which was proved in this Science paper 5 years ago.

Answer 3

I've found this Venn Diagram to be incredibly helpful in understanding the differences between P, NP, NP-Complete, and NP-Hard.

You're right that Traveling Salesman would not be considered NP-Complete. It's NP-Hard, but not in NP. The only way to verify a solution to Traveling Salesman (that we know of today) is to compare it to the optimal solution... and to get that optimal solution, you'd need to solve the problem. There are a whole bunch of NP-Hard problems that are too hard to be NP, including spin-glass.