Natural Complexity, Computational Complexity and Depth
arXiv:1111.2845 · doi:10.1063/1.3634009
Abstract
Depth is a complexity measure for natural systems of the kind studied in statistical physics and is defined in terms of computational complexity. Depth quantifies the length of the shortest parallel computation required to construct a typical system state or history starting from simple initial conditions. The properties of depth are discussed and it is compared to other complexity measures. Depth can only be large for systems with embedded computation.
arXiv comment21 pages, 1 figure
References in corpus (12)
- Monte Carlo study of the random-field Ising model
- Complexity Through Nonextensivity
- Majority-Vote Cellular Automata, Ising Dynamics, and P-Completeness
- Effective Complexity and its Relation to Logical Depth
- Excess entropy in natural language: present state and perspectives
- Parallel Dynamics and Computational Complexity of Network Growth Models
- The Computational Complexity of Generating Random Fractals
- The Parallel Complexity of Growth Models
- The Computational Complexity of the Lorentz Lattice Gas
- Structural and computational depth of diffusion limited aggregation
- Sampling Chaotic Trajectories Quickly in Parallel
- Parallel Complexity of Random Boolean Circuits