Physics – Condensed Matter – Statistical Mechanics
Scientific paper
2001-05-15
Physica A300, 245-270 (2001)
Physics
Condensed Matter
Statistical Mechanics
37 pages, 12 figures
Scientific paper
10.1016/S0378-4371(01)00336-3
The parallel computational complexity of the Bak-Sneppen evolution model is studied. It is shown that Bak-Sneppen histories can be generated by a massively parallel computer in a time that is polylogarithmic in the length of the history. In this parallel dynamics, histories are built up via a nested hierarchy of avalanches. Stated in another way, the main result is that the logical depth of producing a Bak-Sneppen history is exponentially less than the length of the history. This finding is surprising because the self-organized critical state of the Bak-Sneppen model has long range correlations in time and space that appear to imply that the dynamics is sequential and history dependent. The parallel dynamics for generating Bak-Sneppen histories is contrasted to standard Bak-Sneppen dynamics. Standard dynamics and an alternate method for generating histories, conditional dynamics, are both shown to be related to P-complete natural decision problems implying that they cannot be efficiently implemented in parallel.
Li Xuenan
Machta Jon
No associations
LandOfFree
Parallel dynamics and computational complexity of the Bak-Sneppen model does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Parallel dynamics and computational complexity of the Bak-Sneppen model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel dynamics and computational complexity of the Bak-Sneppen model will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-61944