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.
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
Cai, Lu, Xia Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
See especially the introduction of the latter for the connection to physical models.
Allan Sly proved 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] and [DFJ02].
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.
