Нашли опечатку? Выделите ее мышкой и нажмите Ctrl+Enter
Название: The Computational Complexity of Pattern Formation
Автор: Machta J.
The computational complexity of diffusion-limited aggregation and fluid invasion in porous media is studied. The time requirements on an idealized parallel computer for simulating the patterns formed by these models are investigated. It is shown that these growth models are P-complete. These results provide strong evidence that such pattern formation processes are inherently sequential and cannot be simulated efficiently in parallel.