×

The computational complexity of generating random fractals. (English) Zbl 1260.68182

Summary: 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 equilibratring 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 guide to simulation physics.

MSC:

68Q25 Analysis of algorithms and problem complexity
68W10 Parallel algorithms in computer science
28A80 Fractals
82B20 Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics
65Y05 Parallel numerical computation
60K35 Interacting random processes; statistical mechanics type models; percolation theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] C. H. Bennett, How to define complexity in physics, and why, inComplexity, Entropy and the Physics of Information, W. H. Zurek, ed. (Addison-Wesley, Reading, Massachusetts, 1990).
[2] B. B. Mandelbrot,The Fractal Geometry of Nature (Freeman, San Francisco, 1983). · Zbl 1194.30028
[3] J. T. Chayes, L. Chayes, and R. Durrett, Connectivity properties of Mandelbrot’s percolation process,Prob. Theory Related Fields 77:307 (1988). · Zbl 0621.60110 · doi:10.1007/BF00319291
[4] T. A. Witten and L. M. Sander, Diffusion-limited aggregation, a kinetic critical phenomenon,Phys. Rev. Lett. 47:1400 (1981). · doi:10.1103/PhysRevLett.47.1400
[5] J. Machta, The computational complexity of pattern formation.J. Stat. Phys. 170:949 (1993). · Zbl 0935.82566 · doi:10.1007/BF01053602
[6] J. Machta and R. Greenlaw, The parallel complexity of growth models,J. Stat. Phys. 77:755 (1994). · Zbl 0850.82001 · doi:10.1007/BF02179460
[7] F. Barahona, On the computational complexity of Ising spin glass models,J. Phys. A: Math. Gen. 15:3241 (1982). · doi:10.1088/0305-4470/15/10/028
[8] J. Machta, The computational complexity of the self-avoiding walk on random lattices,J. Phys. A: Math. Gen. 25:521 (1992). · doi:10.1088/0305-4470/25/3/012
[9] J. C. Angles d’Auriac, M. Preissmann, and R. Rammal, The random field Ising model: Algorithmic complexity and phase transitions.J. Phys. (Paris)46:L173 (1985).
[10] D. J. A. Welsh, The computational complexity of some classical problems from statistical physics, inDisorder in Physical Systems, G. R. Grimmett and D. J. A. Welsh, eds. (Oxford University Press, Oxford, 1990), p. 307. · Zbl 0737.60094
[11] M. Jerrum and A. Sinclair, Polynomial-time approximation algorithms for the Ising model,SIAM J. Computing 22(5):1087 (1993). · Zbl 0782.05076 · doi:10.1137/0222066
[12] J. E. Hopcroft and J. D. Ullman,Introduction to Automata Theory, Languages, and Computation Addison-Wesley, Reading, Massachusetts, (1979). · Zbl 0426.68001
[13] H. R. Lewis and C. H. Papadimitriou,Elements of the Theory of Computation (Prentice-Hall, Englewood Cliffs, New Jersey, 1981). · Zbl 0464.68001
[14] R. Greenlaw, H. J. Hoover, and W. L. Ruzzo,Limits to Parallel Computation: P-Completeness Theory (Oxford University Press, Oxford, 1995). · Zbl 0829.68068
[15] D. S. Johnson, A catalog of complexity classes, inHandbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, J. van Leeuwman, ed. (MIT Press/Elsevier, 1990), p. 68.
[16] M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, New York, 1979). · Zbl 0411.68039
[17] A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, Massachusetts, 1974). · Zbl 0326.68005
[18] F. E. Fich, The complexity of computation on the parallel random access machine, inSynthesis of Parallel Algorithms, J. H. Reif, ed. (Morgan Kaufman, San Mateo, California, 1993), Chapter 20, pp. 843–899.
[19] R. M. Karp and V. Ramachandran, Parallel algorithms for shared-memory machines, inHandbook of Theoretical Computer Science, volume A: Algorithms and Complexity, Jan van Leeuwman, ed. (MIT Press/Elsevier, 1990), Chapter 17, pp. 869–941. · Zbl 0900.68267
[20] R. E. Ladner, The circuit value problem is log space complete for P,SIGACT News 7:18 (1975). · doi:10.1145/990518.990519
[21] E. Fredkin and T. Toffoli, Conservative logic,Int. J. Theor. Phys. 21:219 (1982). · Zbl 0496.94015 · doi:10.1007/BF01857727
[22] J. Von Neumann,Theory of Self-Reproducing Automata (University of Illinois Press, Urbana, 1966).
[23] J. Machta, Y. S. Choi, A. Lucke, T. Schweizer, and L. V. Chayes. Invaded cluster algorithm for equilibrium critical points,Phys. Rev. Lett. 75:2792 (1995). · Zbl 0951.82016 · doi:10.1103/PhysRevLett.75.2792
[24] H. Venkateswaran, Circuit definitions of nondeterministic complexity classes,SIAM J. Computing 21:655 (1992). · Zbl 0749.68039 · doi:10.1137/0221040
[25] J. Machta, Phase transitions in fractal porous media,Phys. Rev. Lett. 66:169 (1991). · doi:10.1103/PhysRevLett.66.169
[26] J. T. Chayes, L. Chayes, and J. Machta, Phase diagram and correlation length bounds for Mandelbrot aerogels,J. Phys. A: Math. Gen. 26:4249 (1993). · Zbl 0797.60087 · doi:10.1088/0305-4470/26/17/031
[27] L. Chayes and J. Machta, On the behavior of the surface tension for spin-systems in a correlated porous medium,J. Stat. Phys. 79:117 (1995). · Zbl 1081.82637 · doi:10.1007/BF02179384
[28] U. Wolff, Collective Monte Carlo updating for spin systems,Phys. Rev. Lett. 62:361 (1989). · doi:10.1103/PhysRevLett.62.361
[29] R. H. Swendsen and J.-S. Wang, Nonuniversal critical dynamics in Monte Carlo simulations,Phys. Rev. Lett. 58:86 (1987). · doi:10.1103/PhysRevLett.58.86
[30] M. E. Fisher, The theory of condensation and the critical point,Physics 3:255 (1967). · Zbl 0154.40308
[31] C. M. Fortuin and P. M. Kasteleyn, On the random-cluster model,Physica 57:536 (1972). · doi:10.1016/0031-8914(72)90045-6
[32] A. Coniglio and W. Klein, Clusters and Ising critical droplets: A renormalisation group approach,J Phys. A: Math. Gen. 13:2775 (1980). · doi:10.1088/0305-4470/13/8/025
[33] A. Gibbons and W. Rytter,Efficient Parallel Algorithms (Cambridge University Press, Cambridge, 1988). · Zbl 0771.68015
[34] L. A. Levin, Average case complete problems,SIAM J. Computing 15:285 (1986). · Zbl 0589.68032 · doi:10.1137/0215020
[35] S. Ben-David, B. Chor, O. Goldreich, and M. Luby, On the theory of average case complexity,J. Computer Syst. Sc. 44:193 (1992). · Zbl 0762.68027 · doi:10.1016/0022-0000(92)90019-F
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.