The Computational Complexity of Generating Random Fractals

Details The Computational Complexity of Generating Random Fractals The Computational Complexity of Generating Random Fractals

1995-03-31

arxiv.org/abs/cond-mat/9503170v1

J. Stat. Phys. 82 (1996) 1299

Physics

Condensed Matter

28 pages, LATEX, 8 Postscript figures available from machta@phast.umass.edu

Scientific paper

10.1007/BF02183384

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.

Affiliated with

Also associated with

No associations

Rating

The Computational Complexity of Generating Random Fractals does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Computational Complexity of Generating Random Fractals, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Computational Complexity of Generating Random Fractals will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-96974