The computational complexity of generating random fractals

DOI10.1007/BF02183384zbMath1260.68182arXivcond-mat/9503170MaRDI QIDQ1946896

Jonathan Machta, Raymond Greenlaw

Publication date: 10 April 2013

Published in: Journal of Statistical Physics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cond-mat/9503170

zbMATH Keywords

computational complexityIsing modelcluster algorithmsMetropolis algorithmP-completenessdiffusion-limited aggregation

Mathematics Subject Classification ID

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

Related Items

Computational Complexity of Biased Diffusion-Limited Aggregation, Predicting nonlinear cellular automata quickly by decomposing them into linear ones, Parallel dynamics and computational complexity of the Bak-Sneppen model, The computational complexity of the Lorentz lattice gas, Natural complexity, computational complexity and depth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the quadratic mapping \(z\rightarrow z^{2}-\mu \) for complex \(\mu \) and \(z\): the fractal structure of its set, and scaling
• Connectivity properties of Mandelbrot's percolation process
• Conservative logic
• On the theory of average case complexity
• The computational complexity of pattern formation
• On the behavior of the surface tension for spin systems in a correlated porous medium.
• The parallel complexity of growth models
• Polynomial-Time Approximation Algorithms for the Ising Model
• Average Case Complete Problems
• Circuit Definitions of Nondeterministic Complexity Classes
• Phase diagram and correlation length bounds for Mandelbrot aerogels
• Invaded Cluster Algorithm for Equilibrium Critical Points
• On Construction and Properties of the Generalized Inverse