We study cellular automata where the state at each site is decided by a majority vote of the sites in its neighborhood. These are equivalent, for a restricted set of initial conditions, to non-zero probability transitions in single spin-flip dynamics of the Ising model at zero temperature. <p> We...</p>

The technique of approximating the mean path of Markov chains by differential equations has proved to be a useful tool in analyzing the performance of heuristics on random graph instances. However, only a small family of algorithms can currently be analyzed by this method, due to the need to...

We study path integration on a quantum computer that performs quantum summation. We assume that the measure of path integration is Gaussian, with the eigenvalues of its covariance operator of order j^{-k} with k1. For the Wiener measure occurring in many applications we have k=2. We want to...

We show that predicting the HPP or FHP III lattice gas for finite time is equivalent to calculating the output of an arbitrary Boolean circuit, and is therefore P-complete: that is, it is just as hard as any other problem solvable by a serial computer in polynomial time. <p> It is widely believed...</p>

A dynamical-systems-based model of computation is studied. We demonstrate the computational ability of nonlinear mappings. There exists a switching map system with two types of baker's map to emulate any Turing machine. Taking non-hyperbolic mappings with second-order nonlinearity (e.g., the...