Computational Complexity in Statistical Physics

Chris R. Laumann, Roderich Moessner, Antonello Scardicchio +1 more

Stephan Mertens

The theory of computational complexity has some interesting links to physics, in particular to quantum computing and statistical mechanics. The article contains an informal introduction to this theory and its links to physics.

Amit Hagar

We propose a new interpretation of objective probability in statistical physics based on physical computational complexity. This notion applies to a single physical system (be it an experimental set-up in the lab, or a subsystem of the universe), and quantifies (1) the difficulty to realize a physical state given another, (2) the 'distance' (in terms of physical resources) between a physical state and another, and (3) the size of the set of time-complexity functions that are compatible with the physical resources required to reach a physical state from another. This view (a) exorcises 'ignorance' from statistical physics, and (b) underlies a new interpretation to non-relativistic quantum mechanics.

Demian A. Battaglia, Michal Kolář, Riccardo Zecchina

Amit Hagar, Giuseppe Sergioli

We propose a new interpretation of objective deterministic chances in statistical physics based on physical computational complexity. This notion applies to a single physical system (be it an experimental set--up in the lab, or a subsystem of the universe), and quantifies (1) the difficulty to realize a physical state given another, (2) the `distance' (in terms of physical resources) of a physical state from another, and (3) the size of the set of time--complexity functions that are compatible with the physical resources required to reach a physical state from another. This view (a) exorcises "ignorance" from statistical physics, and (b) underlies a new interpretation to non--relativistic quantum mechanics.

Berni J. Alder