The Computational Complexity of Sandpiles

Дата и время публикации : 1998-08-17T22:40:22Z

Авторы публикации и институты :
Cristopher Moore
Martin Nilsson

Ссылка на журнал-издание: Ссылка на журнал-издание не найдена
Коментарии к cтатье: Ссылка на журнал-издание не найдена
Первичная категория: cond-mat

Все категории : cond-mat, adap-org, nlin.AO, nlin.PS, patt-sol

Краткий обзор статьи: 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.

Category: Physics