The computational complexity of generating random fractals |
| |
Authors: | Jonathan Machta Raymond Greenlaw |
| |
Institution: | (1) Department of Physics and Astronomy, University of Massachusetts, 01003 Amherst, Massachusetts;(2) Department of Computer Science, University of New Hampshire, 03824 Durham, New Hampshire |
| |
Abstract: | 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, which 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. |
| |
Keywords: | Cluster algorithms computational complexity diffusion-limited aggregation Ising model Metropolis algorithm P-completeness |
本文献已被 SpringerLink 等数据库收录! |