1995/03/31 by Jonathan Machta, J. Machta, Raymond Greenlaw +1 · 4 citations
Mathematics · Physics and Astronomy · #Opinion Dynamics and Social Influence #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #adap-org #cond-mat #nlin.AO
paper · pdf · doi:10.1007/bf02183384
published as J. Stat. Phys. 82 (1996) 1299 · 28 pages, LATEX, 8 Postscript figures available from [email protected]
arxiv created 1995/03/31 · openalex publication_date 1996/03/01 · arxiv updated 2009/11/30 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
In this paper we examine a number of models that generate random fractals. The models are studied using the tools of computational complexity theory from the perspective of parallel computation. Diffusion limited aggregation and several widely used algorithms for equilibrating the Ising model are shown to be highly sequential; it is unlikely they can be simulated efficiently in parallel. This is in contrast to Mandelbrot percolation that can be simulated in constant parallel time. Our research helps shed light on the intrinsic complexity of these models relative to each other and to different growth processes that have been recently studied using complexity theory. In addition, the results may serve as a guide to simulation physics.