InterJournal Complex Systems, 57
Status: Accepted
Manuscript Number: [57]
Submission Date: 963011
Parallel computational complexity and logical depth in statistical physics
Author(s): Jon Machta , Ray Greenlaw

Subject(s): CX.07

Category: Brief Article


One of the fundamental insights motivating the PhysComp meetings is that the states of physical systems are the result of transformations not just of matter and energy but also of information. By focusing on the computational aspects of the physical world, we hope to gain new insights into important familiar systems. In this interdisciplinary work we apply the tools of parallel computational complexity theory to a number of problems in statistical physics. New useful bridges between physics and computer science are constructed and a number of interesting results are achieved. The strategy of analyzing problems in statistical physics via parallel computational complexity that we develop will likely find applications to a number of other problems as the method is general. A summary of our results is presented.

Retrieve Manuscript
Submit referee report/comment

Public Comments: