Treffer: Parallel Computational Complexity in Statistical Physics

Introduction Parallel computational complexity theory is the branch of theoretical computer science in which problems are classified according to the time and processor requirements of their parallel solutions. From a practical standpoint, parallel complexity analysis will become a valuable tool in simulation physics as parallel computers become more widely available. On a more conceptual level, parallel computational complexity seems to capture important features of the intuitive concept of physical complexity. Bennett[2, 3] suggests that an object should be regarded as complex if it contains structures that are unlikely to have arisen quickly. In this view, the presence of unavoidable history dependence is the signature of physical complexity. We believe that the intrinsic history dependence of a physical process may be isolated by considering a massively parallel computer simulation of the process. The central idea is that superficial history dependence can be eliminated t