7
$\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.

$\endgroup$
  • 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 Feb 5 '18 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 Feb 10 '18 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 Feb 11 '18 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 Feb 16 '18 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 Mar 3 '18 at 22:17
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.

$\endgroup$
  • $\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 Feb 6 '18 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 Feb 6 '18 at 2:01
  • $\begingroup$ See Shor's comment on the OP. $\endgroup$ – 0x90 Feb 12 '18 at 3:29
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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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