Lattice Gas Prediction is P-complete

Details Lattice Gas Prediction is P-complete Lattice Gas Prediction is P-complete

1997-04-17

arxiv.org/abs/comp-gas/9704001v1

Nonlinear Sciences

Cellular Automata and Lattice Gases

10 pages with figures

Scientific paper

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 \alpha < 1/2, unless the class P is equal to the class NC or SP respectively.

Affiliated with

Also associated with

No associations

Rating

Lattice Gas Prediction is P-complete does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Lattice Gas Prediction is P-complete, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lattice Gas Prediction is P-complete will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-441934