<p>It was only recently (2016) that it was proved mathematically that all of classical spin physics can be reproduced by the 2D Ising Model with linear terms (what physicists call "fields") with at most polynomial overhead: <a href="http://science.sciencemag.org/content/351/6278/1180" rel="nofollow noreferrer">Simple universal models capture all classical spin physics</a>.</p>

<p>So there's two things to say:<br></p>

<ul>
<li>It is not "trivial" to do this reduction, since it took about 100 years to prove.<br></li>
<li>Not just <strong><em>any</em></strong> spin-glass problem encapsulates all of classical spin physics. The paper proves that a 2D spin-glass problem with linear terms is sufficient. But a 1D spin-glass, or a 2D spin-glass without linear terms, would not be enough.<br></li>
</ul>

CC BY-SA 4.0
2018-07-15T01:10:50.583Z
2018-07-15T01:10:50.583Z
user1271772
<p>Classical physical problems often involve real-number positions or parameter values rather than values from a discrete set (such as the integers) which would be more typical of NP-complete problems. Because of this these problems can often be NP-hard but not (or not obviously) NP-complete. For instance, we do not know whether the Euclidean TSP (for integer points in the plane, with Euclidean distances) is NP-complete, because it hinges on <a href="http://cs.smith.edu/~jorourke/TOPP/P33.html" rel="noreferrer">an unsolved problem, the complexity of comparing sums of square roots</a>. Some other geometric problems, such as the recognition of unit distance graphs (of some relevance as an abstraction of protein folding) are complete for the <a href="https://en.wikipedia.org/wiki/Existential_theory_of_the_reals" rel="noreferrer">existential theory of the reals</a>, which as far as we know is a different complexity class than NP.</p>

CC BY-SA 3.0
2018-02-06T01:28:03.903Z
So why do these 2 pieces of work have such significant impact? They turn a real number position problem to discrete (but any simulation on computer basically does that).
0x90
CC BY-SA 3.0
2018-02-06T02:01:42.490Z
It is not true that the only way to do things on a computer is to round to floating point. The Euclidean TSP has an exact solution, which can be represented combinatorially (it is just a sequence of points) but finding it appears to require the use of symbolic computation methods that represent all lengths exactly (as the zeros of polynomials with integer coefficients, say). Instead, if you try to round the edge lengths to floating point numbers, you will likely find the wrong tour, a different sequence of points that is good but not optimal.
David Eppstein
CC BY-SA 3.0
2018-02-06T00:19:53.053Z
2018-02-06T00:19:53.053Z
David Eppstein
<p>In the late 80's there were several highly cited efforts to use Spin-Glass models to formulate other computational problems such as: <a href="http://www.pnas.org/content/84/21/7524" rel="nofollow noreferrer">Protein Folding</a> and <a href="https://journals.aps.org/pra/abstract/10.1103/PhysRevA.32.1007" rel="nofollow noreferrer">Neural Networks</a>. </p>

<p>Isn't it straight forward to reduce any classical physics problem into Spin-Glass which is <a href="http://yaroslavvb.com/papers/barahona-on.pdf" rel="nofollow noreferrer">NP-complete problem</a>? </p>

<p>What I am saying is: since Spin-Glass is at least as powerful model (computationally) as any classical physics model it is always possible to restate a classical system using Spin-Glass.</p>

<p>I believe I am missing a huge point here, because these 2 papers are highly cited ones.</p>

<p><strong>EDIT</strong>: If you downvote, please, kindly consider to add a constructive comment.  </p>

CC BY-SA 3.0
2018-02-05T05:41:08.053Z
The first paper derives a phase diagram for protein folding. How would get that from some hardness reduction? NP-hardness reductions between optimization problems do not have to preserve all the structure of the models, just to map optimal solutions to optimal solutions.
Sasho Nikolov
CC BY-SA 3.0
2018-02-05T05:49:40.593Z
@SashoNikolov one can get it from spin glass solutions. Once you do the reduction to the problem one can use the known tools to gather insights on the reduced problem. Unless I am missing here something. In fact, I think that since spin glass is np-complete we can have phase diagram for any problem in NP.
0x90
CC BY-SA 3.0
2018-02-10T12:45:41.957Z
@0x90: You're missing something. A phase diagram depends on a stochastic probability distribution over problem instances, and NP-complete reductions don't take a random instance of (say) TSP to a random instance of a Spin Glass.
Peter Shor 
CC BY-SA 3.0
2018-02-11T02:54:15.483Z
@PeterShor, I would expect the thermodynamics values of the two NP complete problems to be the same/similar. By thermodynamics values I mean some of the first few moments of the distributions. Namely, if $TSP \le_{M} SG$ I would expect problem $SG$ to have similar distribution on the space of problem instances which will effect the partition function/ensemble probabilities (as in Maxwell-Boltzmann formalism).
0x90
CC BY-SA 3.0
2018-02-11T17:07:31.833Z
@0x90: years of experience in theoretical computer science says that the thermodynamic behavior of two NP complete problems are in general ***not*** similar.
Peter Shor 
CC BY-SA 3.0
2018-02-12T03:25:38.023Z
If Peter Shor says how can I argue, thank you for the insightful comments. I will write a follow up question soon.
0x90
CC BY-SA 3.0
2018-02-16T14:24:05.273Z
@PeterShor: Even though the thermodynamic behaviors of two NP-complete problems are not in general similar, how does one reconcile this with e.g. the fact that many natural NP-complete problems have natural distributions which exhibit phase transitions? (Also, while I agree that in general they're not similar, I'm curious of what your most striking example of this phenomenon is.)
Joshua Grochow
CC BY-SA 3.0
2018-02-16T21:55:45.493Z
@JoshuaGrochow a question which is related to your comment: https://cstheory.stackexchange.com/q/40193/
0x90
CC BY-SA 3.0
2018-03-03T22:17:24.263Z
@JoshuaGrochow: There are lots and lots of phenomena that have phase transitions. These different phase transitions don't always behave the same. For example, it would be incredibly surprising if an NP-complete problem with a first-order phase transition could be mapped onto an NP-complete problem with a second-order phase transition, while preserving the thermodynamics. But indeed there are sets of NP-complete problems which have the same class of phase transition, and indeed some subset of these problems can be mapped from one to another while preserving the thermodynamics.
Peter Shor 
CC BY-SA 4.0
2020-07-03T11:03:27.577Z
With regard to the last line of your question, some of the downvoters (me) ***did*** add constructive comments. Others may simply be agreeing with the comments already added. And the question as currently stated deserves a.downvote, because it seems that your real concern is thermodynamics and phase diagrams, and this fact is explained *only* in the comments and not in the actual question.
Peter Shor 
<complexity-classes><reductions><np-complete><physics><statistical-physics>
Isn't it "trivial" to represent/reduce any classical physics problem into a Spin-Glass which is NP-Complete?
0x90
# Isn't it "trivial" to represent/reduce any classical physics problem into a Spin-Glass which is NP-Complete?

(Asked by: username_0 on 2018-02-05)

In the late 80's there were several highly cited efforts to use Spin-Glass models to formulate other computational problems such as: [Protein Folding](http://www.pnas.org/content/84/21/7524) and [Neural Networks](https://journals.aps.org/pra/abstract/10.1103/PhysRevA.32.1007).

Isn't it straight forward to reduce any classical physics problem into Spin-Glass which is [NP-complete problem](http://yaroslavvb.com/papers/barahona-on.pdf)?

What I am saying is: since Spin-Glass is at least as powerful model (computationally) as any classical physics model it is always possible to restate a classical system using Spin-Glass.

I believe I am missing a huge point here, because these 2 papers are highly cited ones.

**EDIT**: If you downvote, please, kindly consider to add a constructive comment.

**Tags:** complexity-classes, reductions, np-complete, physics, statistical-physics

> **Comments:**
> **username_1**: The first paper derives a phase diagram for protein folding. How would get that from some hardness reduction? NP-hardness reductions between optimization problems do not have to preserve all the structure of the models, just to map optimal solutions to optimal solutions.  
> **username_0**: @SashoNikolov one can get it from spin glass solutions. Once you do the reduction to the problem one can use the known tools to gather insights on the reduced problem. Unless I am missing here something. In fact, I think that since spin glass is np-complete we can have phase diagram for any problem in NP.  
> **username_2**: @username_0: You're missing something. A phase diagram depends on a stochastic probability distribution over problem instances, and NP-complete reductions don't take a random instance of (say) TSP to a random instance of a Spin Glass.  
> **username_0**: @PeterShor, I would expect the thermodynamics values of the two NP complete problems to be the same/similar. By thermodynamics values I mean some of the first few moments of the distributions. Namely, if $TSP \le_{M} SG$ I would expect problem $SG$ to have similar distribution on the space of problem instances which will effect the partition function/ensemble probabilities (as in Maxwell-Boltzmann formalism).  
> **username_2**: @username_0: years of experience in theoretical computer science says that the thermodynamic behavior of two NP complete problems are in general ***not*** similar.  
> **username_0**: If username_2says how can I argue, thank you for the insightful comments. I will write a follow up question soon.  
> **username_3**: @PeterShor: Even though the thermodynamic behaviors of two NP-complete problems are not in general similar, how does one reconcile this with e.g. the fact that many natural NP-complete problems have natural distributions which exhibit phase transitions? (Also, while I agree that in general they're not similar, I'm curious of what your most striking example of this phenomenon is.)  
> **username_0**: @JoshuaGrochow a question which is related to your comment: https://cstheory.stackexchange.com/q/40193/  
> **username_2**: @JoshuaGrochow: There are lots and lots of phenomena that have phase transitions. These different phase transitions don't always behave the same. For example, it would be incredibly surprising if an NP-complete problem with a first-order phase transition could be mapped onto an NP-complete problem with a second-order phase transition, while preserving the thermodynamics. But indeed there are sets of NP-complete problems which have the same class of phase transition, and indeed some subset of these problems can be mapped from one to another while preserving the thermodynamics.  
> **username_2**: With regard to the last line of your question, some of the downvoters (me) ***did*** add constructive comments. Others may simply be agreeing with the comments already added. And the question as currently stated deserves a.downvote, because it seems that your real concern is thermodynamics and phase diagrams, and this fact is explained *only* in the comments and not in the actual question.  

---

## 2 answers

### Answer by username_4 on 2018-07-15. Score: 2 | Accepted answer

It was only recently (2016) that it was proved mathematically that all of classical spin physics can be reproduced by the 2D Ising Model with linear terms (what physicists call "fields") with at most polynomial overhead: [Simple universal models capture all classical spin physics](http://science.sciencemag.org/content/351/6278/1180).

So there's two things to say:

* It is not "trivial" to do this reduction, since it took about 100 years to prove.
* Not just ***any*** spin-glass problem encapsulates all of classical spin physics. The paper proves that a 2D spin-glass problem with linear terms is sufficient. But a 1D spin-glass, or a 2D spin-glass without linear terms, would not be enough.


---

### Answer by username_5 on 2018-02-06. Score: 9

Classical physical problems often involve real-number positions or parameter values rather than values from a discrete set (such as the integers) which would be more typical of NP-complete problems. Because of this these problems can often be NP-hard but not (or not obviously) NP-complete. For instance, we do not know whether the Euclidean TSP (for integer points in the plane, with Euclidean distances) is NP-complete, because it hinges on [an unsolved problem, the complexity of comparing sums of square roots](http://cs.smith.edu/~jorourke/TOPP/P33.html). Some other geometric problems, such as the recognition of unit distance graphs (of some relevance as an abstraction of protein folding) are complete for the [existential theory of the reals](https://en.wikipedia.org/wiki/Existential_theory_of_the_reals), which as far as we know is a different complexity class than NP.

> **Comments:**
> **username_0**: So why do these 2 pieces of work have such significant impact? They turn a real number position problem to discrete (but any simulation on computer basically does that).  
> **username_5**: It is not true that the only way to do things on a computer is to round to floating point. The Euclidean TSP has an exact solution, which can be represented combinatorially (it is just a sequence of points) but finding it appears to require the use of symbolic computation methods that represent all lengths exactly (as the zeros of polynomials with integer coefficients, say). Instead, if you try to round the edge lengths to floating point numbers, you will likely find the wrong tour, a different sequence of points that is good but not optimal.  

---

