Lattice Gas Prediction is P-Complete

Kristian Lindgren, Cristopher Moore and Mats G. Nordahl
Additional contact information
Cristopher Moore: http://www.santafe.edu/~moore

Working Papers from Santa Fe Institute

Abstract: We show that predicting the HPP or FHP III lattice gas for finite time is equivalent to calculating the output of an arbitrary Boolean circuit, and is therefore P-complete: that is, it is just as hard as any other problem solvable by a serial computer in polynomial time.

It is widely believed in computer science that there are inherently sequential problems, for which parallel processing gives no significant speedup. Unless this is false, it is impossible even with highly parallel processing to predict lattice gases much faster than by explicit simulation. More precisely, we cannot predict t time-steps of a lattice gas in parallel computation time O(log^{k}t) for any k, or O(t^{\alpha}) for

Keywords: Lattice gases; cellular automata; parallel computation; computational complexity; P-completeness; rum punch (search for similar items in EconPapers)
Date: 1997-04
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wop:safiwp:97-04-034

Access Statistics for this paper

More papers in Working Papers from Santa Fe Institute Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel ().