InterJournal Complex Systems, 422
Status: Accepted
Manuscript Number: [422]
Submission Date: 611
Revised On: 11029
Phase Transitions in the Computational Complexity of ``Elementary
Author(s): sitabhra sinha

Subject(s): CX.04.01, CX.04.04, CX.07

Category: Article


A study of the computational complexity of determining the ``Garden-of-Eden" states (i.e. states without any pre-images) of one-dimensional cellular automata (CA) is reported. The work aims to relate phase transitions in the computational complexity of decision problems, with the type of dynamical behavior exhibited by the CA time evolution. This is motivated by the observation of critical behavior in several computationally hard problems - e.g., the Satisfiability problem (SAT) cite{Kir94}. The focus is on ``legal" CA rules, i.e. those which obey the quiescence and symmetry conditions cite{Wol83}. A relation exists between the problem of ``Garden-of-eden" state determination and the SAT problem, and several CA rules (e.g., CA rules 4, 22 and 54) are studied in detail to establish the occurrence of phase transition. Finite-size scaling exponents corresponding to the critical behavior are obtained which point to a new {em quantitative} classification of ``elementary" cellular automata into 5 classes.

Retrieve Manuscript
Retrieve Previous Revision's Abstract
Submit referee report/comment

Public Comments: