THE COMPUTATIONAL-COMPLEXITY OF THE LORENTZ LATTICE-GAS

Authors
MACHTA J MORIARTY K
Citation
J. Machta et K. Moriarty, THE COMPUTATIONAL-COMPLEXITY OF THE LORENTZ LATTICE-GAS, Journal of statistical physics, 87(5-6), 1997, pp. 1245-1252
Citations number
15
Categorie Soggetti
Mathematical Method, Physical Science","Physycs, Mathematical
Journal title
Journal of statistical physics → ACNP
ISSN journal
00224715
Volume
87
Issue
5-6
Year of publication
1997
Pages
1245 - 1252
Database
ISI
SICI code
0022-4715(1997)87:5-6<1245:TCOTLL>2.0.ZU;2-W
Abstract
The Lorentz lattice gas is studied from the perspective of computation al complexity theory. It is shown that using massive parallelism, part icle trajectories can be simulated in a time that scales logarithmical ly in the length of the trajectory. This result characterizes the ''lo gical depth'' of the Lorentz lattice gas and allows us to compare it t o other models in statistical physics.