Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 3 of 3
Full-Text Articles in Physical Sciences and Mathematics
Natural Complexity, Computational Complexity And Depth, Jonathan Machta
Natural Complexity, Computational Complexity And Depth, Jonathan Machta
Jonathan Machta
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 with other complexity measures. Depth can only be large for systems with embedded computation.
Parallel Complexity Of Random Boolean Circuits, Jonathan Machta, S. Dedeo, S. Mertens, C. Moore
Parallel Complexity Of Random Boolean Circuits, Jonathan Machta, S. Dedeo, S. Mertens, C. Moore
Jonathan Machta
Random instances of feedforward Boolean circuits are studied both analytically and numerically. Evaluating these circuits is known to be a P-complete problem and thus, in the worst case, believed to be impossible to perform, even given a massively parallel computer, in a time much less than the depth of the circuit. Nonetheless, it is found that, for some ensembles of random circuits, saturation to a fixed truth value occurs rapidly so that evaluation of the circuit can be accomplished in much less parallel time than the depth of the circuit. For other ensembles saturation does not occur and circuit evaluation …
Monte Carlo Methods For Rough Free Energy Landscapes: Population Annealing And Parallel Tempering, Jonathan Machta, Richard S. Ellis
Monte Carlo Methods For Rough Free Energy Landscapes: Population Annealing And Parallel Tempering, Jonathan Machta, Richard S. Ellis
Jonathan Machta
Parallel tempering and population annealing are both effective methods for simulating equilibrium systems with rough free energy landscapes. Parallel tempering, also known as replica exchange Monte Carlo, is a Markov chain Monte Carlo method while population annealing is a sequential Monte Carlo method. Both methods overcome the exponential slowing associated with high free energy barriers. The convergence properties and efficiencies of the two methods are compared. For large systems, population annealing is closer to equilibrium than parallel tempering for short simulations. However, with respect to the amount of computation, parallel tempering converges exponentially while population annealing converges only inversely. As …