8
$\begingroup$

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 and Neural Networks.

Isn't it straight forward to reduce any classical physics problem into Spin-Glass which is NP-complete problem?

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.

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Commented Feb 5, 2018 at 5:41
  • 4
    $\begingroup$ @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. $\endgroup$
    – Peter Shor
    Commented Feb 10, 2018 at 12:45
  • 5
    $\begingroup$ @0x90: years of experience in theoretical computer science says that the thermodynamic behavior of two NP complete problems are in general not similar. $\endgroup$
    – Peter Shor
    Commented Feb 11, 2018 at 17:07
  • 3
    $\begingroup$ @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.) $\endgroup$
    – Joshua Grochow
    Commented Feb 16, 2018 at 14:24
  • 5
    $\begingroup$ @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. $\endgroup$
    – Peter Shor
    Commented Mar 3, 2018 at 22:17

2 Answers 2

Reset to default
2
$\begingroup$

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.

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.
Improve this answer
$\endgroup$
9
$\begingroup$

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. 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, which as far as we know is a different complexity class than NP.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$
    – 0x90
    Commented Feb 6, 2018 at 1:28
  • 5
    $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Commented Feb 6, 2018 at 2:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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