Computational Complexity of Avalanches in the Kadanoff two-dimensional Sandpile Model

Details Computational Complexity of Avalanches in the Kadanoff two-dimensional Sandpile Model Computational Complexity of Avalanches in the Kadanoff two-dimensional Sandpile Model

2010-10-07

arxiv.org/abs/1010.1416v1

Computer Science

Discrete Mathematics

15 pages

Scientific paper

In this paper we prove that the avalanche problem for Kadanoff sandpile model (KSPM) is P-complete for two-dimensions. Our proof is based on a reduction from the monotone circuit value problem by building logic gates and wires which work with configurations in KSPM. The proof is also related to the known prediction problem for sandpile which is in NC for one-dimensional sandpiles and is P-complete for dimension 3 or greater. The computational complexity of the prediction problem remains open for two-dimensional sandpiles.

Affiliated with

Also associated with

No associations

Rating

Computational Complexity of Avalanches in the Kadanoff two-dimensional Sandpile Model 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 Computational Complexity of Avalanches in the Kadanoff two-dimensional Sandpile Model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computational Complexity of Avalanches in the Kadanoff two-dimensional Sandpile Model will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-509626