The Computational Complexity of Generating Random Fractals

Abstract

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.

28 pages, LATEX, 8 Postscript figures available from [email protected]

References in corpus (2)

• Invaded cluster algorithm for equilibrium critical points
• The Parallel Complexity of Growth Models

Cited by in corpus (11)

• The Computational Complexity of Sandpiles
• Majority-Vote Cellular Automata, Ising Dynamics, and P-Completeness
• Predicting Non-linear Cellular Automata Quickly by Decomposing Them into Linear Ones
• Noisy Random Boolean Formulae - a Statistical Physics Perspective
• Parallel Dynamics and Computational Complexity of Network Growth Models
• Parallel Invaded Cluster Algorithm for the Ising Model
• Parallel Algorithm and Dynamic Exponent for Diffusion-limited Aggregation
• Natural Complexity, Computational Complexity and Depth
• The Computational Complexity of the Lorentz Lattice Gas
• Structural and computational depth of diffusion limited aggregation
• Parallel dynamics and computational complexity of the Bak-Sneppen model