  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 non-local 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 O((n/k + log k) n^{2/d}) steps. This is a
significant speedup over explicit sequential simulation, which takes
O(n^{1+2/d}) time on average.
  Finally, we show that in one dimension internal DLA can be predicted in O(log
n) parallel time, and so is in the complexity class NC.
