Paper Info
Title
The parallel complexity of algorithms for pattern formation models (extended abstract)
Abstract
Abs t r ac t . This paper investigates the computational complexity of several important models that are currently used by physicists to study pattern formation. The results represent one of the first applications of the tools of parallel computational complexity theory to complex physical systems. The specific models we study are diffusion limited a99regation, fluid invasion, invasion percolation, and invasion percolation with trapping. It is known that all of these processes yield complex, fractal patterns. The paper shows that decision problems based on fluid invasion and diffusion fimited aggregation are P-complete. In contrast, we give A/u0027C 2 algorithms for the two variants of invasion percolation. The results may have a practical significance for numerical simulations and could lead to fundamental insights into the nature of complex pattern forming systems. The P-completeness theorems are interesting because they involve simulations of physical systems and are more intricate than other P-completeness proofs. The A/u0027G algorithms are interesting because they axe given for two procedures that seem inherently sequential.
Year
Venue
Keywords
1994
Canada-France Conference on Parallel and Distributed Computing
parallel complexity,pattern formation model,pattern formation
Field
DocType
ISBN
Decision problem,Invasion percolation,Physical system,Computer science,Fractal,Algorithm,Pattern formation,Theoretical computer science,Mathematical proof,Parallel complexity,Computational complexity theory
Conference
3-540-58078-6
Citations 
PageRank 
References 
0
0.34
5
Authors
2
Name
Order
Citations
PageRank
Raymond Greenlaw114218.56
Jonathan Machta211.39