The Parallel Computational Complexity of the Percolation Model

The parallel computational complexity of identifying cluster in the two-dimensional site percolation model is investigated. For a square lattice with sides of length $L$ and site occupation probability $p$, the running time of the parallel percolation algorithm we study scales as $log(D_f(L,p))$, where $D_f$ is the average value of the largest, finite cluster diameter in the lattice. We find that $D_f$ exhibits a continuous phase transition as $p$ approaches the critical percolation probability $p_c$ -- indicating that the parallel percolation simulation has a ``complexity critical point,'' corresponding to the structural percolation critical point. Our simulations also suggest that $D_f (L,p_c) \sim L^{d_{min}}$, and thus that the parallel percolation simulation runs in $O(log(L))$ time at $p_c$.