The Computational Complexity of Sandpiles

Cristopher Moore and Martin Nilsson

Working Papers from Santa Fe Institute

Abstract: 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. * >= is greater than or equal to.

Keywords: Quantum computation; error-correcting codes; Clifford Group; parallel computation (search for similar items in EconPapers)
Date: 1998-08
References: View complete reference list from 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:98-08-071

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 ().