 |
Center for Nonlinear Studies |
In this talk I will analyze systems in statistical physics from the point of view of computational complexity theory. The two systems that I will talk about in detail are diffusion limited aggregation and growing networks. The talk will review concepts in parallel computational complexity theory including the notion of P-completeness. I will then discuss the complexity of simulating these models in parallel. The talk will conclude with a discussion of possible connections between computational complexity and informal notions of physical complexity.