![](https://d3ilqtpdwi981i.cloudfront.net/1WSJA-N6DvDraCpgRvsALAfgpp4=/425x550/smart/https://bepress-attached-resources.s3.amazonaws.com/uploads/8c/0e/ff/8c0eff27-6117-4096-b67a-167686d5af41/thumbnail_baf9234d-ff24-4176-95b2-206d88a9f575.jpg)
The computational complexity of internal diffusion-limited aggregation (DLA) is examined from both a theoretical and a practical point of view. We show that for two or more dimensions, the problem of predicting the cluster from a given set of paths is complete for the complexity class CC, the subset of P characterized by circuits composed of comparator gates. CC-completeness is believed to imply that, in the worst case, growing a cluster of size n requires polynomial time in n even on a parallel computer. A parallel relaxation algorithm is presented that uses the fact that clusters are nearly spherical to guess the cluster from a given set of paths, and then corrects defects in the guessed cluster through a nonlocal annihilation process. The parallel running time of the relaxation algorithm for two-dimensional internal DLA is studied by simulating it on a serial computer. The numerical results are compatible with a running time that is either polylogarithmic in n or a small power of n. Thus the computational resources needed to grow large clusters are significantly less on average than the worst-case analysis would suggest. For a parallel machine with k processors, we show that random clusters in d dimensions can be generated in $$\mathcal{O}$$ ((n/k+logk)n 2/d ) steps. This is a significant speedup over explicit sequential simulation, which takes $$\mathcal{O}$$ (n 1+2/d ) time on average. Finally, we show that in one dimension internal DLA can be predicted in $$\mathcal{O}$$ (logn) parallel time, and so is in the complexity class NC.
Available at: http://works.bepress.com/joonathan_machta/2/