The Computational Complexity of the Lorentz Lattice Gas
arXiv:comp-gas/9607001 · doi:10.1007/BF02181282
Abstract
The Lorentz lattice gas is studied from the perspective of computational complexity theory. It is shown that using massive parallelism, particle trajectories can be simulated in a time that scales logarithmically in the length of the trajectory. This result characterizes the ``logical depth" of the Lorentz lattice gas and allows us to compare it to other models in statistical physics.
9 pages, LaTeX, to appear in J. Stat. Phys