The Computational Complexity of Sandpiles

Details The Computational Complexity of Sandpiles The Computational Complexity of Sandpiles

1998-08-17

arxiv.org/abs/cond-mat/9808183v2

Physics

Condensed Matter

Scientific paper

Given an initial distribution of sand in an Abelian sandpile, what final state does it relax to after all possible avalanches have taken place? In d >= 3, we show that this problem is P-complete, so that explicit simulation of the system is almost certainly necessary. We also show that the problem of determining whether a sandpile state is recurrent is P-complete in d >= 3. In d=1, we give two algorithms for predicting the sandpile on a lattice of size n, both faster than explicit simulation: a serial one that runs in time O(n log n), and a parallel one that runs in time O(log^3 n), i.e. in the class NC^3. The latter is based on a more general problem we call Additive Ranked Generability. This leaves the two-dimensional case as an interesting open problem.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-550098