<p>Allan Sly <a href="http://arxiv.org/abs/1005.5584">proved</a> recently that MAX-CUT reduces (under a randomized reduction) to sampling from the Gibbs distribution of the hard core lattice gas beyond the uniqueness phase transition on the Bethe lattice.  Less tight results of this kind (where the reduction is to sampling with parameters well within the non-uniqueness region rather than exactly at the uniqueness transition threshold) have been well known for quite some time: see for example <a href="http://portal.acm.org/citation.cfm?id=258663">[LV97]</a> and <a href="http://www.math.cmu.edu/~af1p/Texfiles/indcount.pdf">[DFJ02]</a>.</p>

CC BY-SA 3.0
2011-10-24T08:09:04.217Z
2011-10-24T08:09:04.217Z
Piyush
<p>There's also work by Schuch, Cirac, and Verstraete showing that finding the ground states of even 1D systems with inverse poly gap is NP-hard, even if we are promised the ground state is a matrix product state -- see <a href="http://arxiv.org/abs/0802.3351">http://arxiv.org/abs/0802.3351</a>. If I recall correctly, the reduction begins with an arbitrary NP verifier, though, not necessarily for a specific problem like MAX-2-SAT.</p>

CC BY-SA 3.0
2011-10-27T01:40:04.270Z
2011-10-27T01:40:04.270Z
Sevag Gharibian
<p>Counting constraint-satisfaction problems (#CSP), evaluating partition functions of many physical models, as well as many topics in classically simulating quantum states/circuits, are all fundamentally contracting tensor networks, which is a #P-complete problem. For a good overview see the following papers: </p>

<p>Itai Arad, Zeph Landau, <a href="http://arxiv.org/abs/0805.0040">Quantum computation and the evaluation of tensor networks</a></p>

<p>Cai, Lu, Xia <a href="http://arxiv.org/abs/1008.0683">Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP</a></p>

<p>See especially the introduction of the latter for the connection to physical models.</p>

CC BY-SA 3.0
2011-10-24T06:35:15.587Z
2011-10-24T06:35:15.587Z
Martin Schwarz
<p>I am looking for examples of hard problems (in NP or harder) from computer science which can be reduced to models of physical processes.</p>

<p>For example, max-2-sat can be reduced to energy minimization in an Ising model.  I would like to find more examples of this type of reduction.</p>

<cc.complexity-theory><reductions><physics><formal-modeling>
Reductions of hard problems to physical models
mdenil
# Reductions of hard problems to physical models

(Asked by: username_0 on 2011-10-24)

I am looking for examples of hard problems (in NP or harder) from computer science which can be reduced to models of physical processes.

For example, max-2-sat can be reduced to energy minimization in an Ising model. I would like to find more examples of this type of reduction.

**Tags:** cc.complexity-theory, reductions, physics, formal-modeling


---

## 3 answers

### Answer by username_3 on 2011-10-24. Score: 10 | Accepted answer

Counting constraint-satisfaction problems (#CSP), evaluating partition functions of many physical models, as well as many topics in classically simulating quantum states/circuits, are all fundamentally contracting tensor networks, which is a #P-complete problem. For a good overview see the following papers:

Itai Arad, Zeph Landau, [Quantum computation and the evaluation of tensor networks](http://arxiv.org/abs/0805.0040)

Cai, Lu, Xia [Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP](http://arxiv.org/abs/1008.0683)

See especially the introduction of the latter for the connection to physical models.


---

### Answer by username_1 on 2011-10-24. Score: 6

Allan Sly [proved](http://arxiv.org/abs/1005.5584) recently that MAX-CUT reduces (under a randomized reduction) to sampling from the Gibbs distribution of the hard core lattice gas beyond the uniqueness phase transition on the Bethe lattice. Less tight results of this kind (where the reduction is to sampling with parameters well within the non-uniqueness region rather than exactly at the uniqueness transition threshold) have been well known for quite some time: see for example [[LV97]](http://portal.acm.org/citation.cfm?id=258663) and [[DFJ02]](http://www.math.cmu.edu/~af1p/Texfiles/indcount.pdf).


---

### Answer by username_2 on 2011-10-27. Score: 6

There's also work by Schuch, Cirac, and Verstraete showing that finding the ground states of even 1D systems with inverse poly gap is NP-hard, even if we are promised the ground state is a matrix product state -- see <http://arxiv.org/abs/0802.3351>. If I recall correctly, the reduction begins with an arbitrary NP verifier, though, not necessarily for a specific problem like MAX-2-SAT.


---

