Problem 19

How common are computationally intractable problems about cellular automata?

Questions concerning the finite time behaviour of finite cellular automata can always be answered by finite computations. But as the phenomenon of computational irreducibility suggests, there may be questions for which the computations are necessarily very long. One may consider for example the question of whether a particular sequence of site values can occur after time steps in the evolution of a one-dimensional cellular automaton, starting from any initial state. Then one may ask whether there exists any algorithm that can determine the answer in a time given by some polynomial in and . The question can certainly be answered by testing all sequences of initial site values that determine the length sequence, but this procedure requires a time that grows exponentially with and . Nevertheless, if an initial sequence could be guessed, then it could be tested in a time polynomial in and . As a consequence, the problem is in the class NP. Now if , then there may be no polynomial time algorithm for the problem, and the best method of solution may essentially be to try all the exponentially many possible cases explicitly, so that the problem rapidly becomes intractable. In the infinite time limit, the analogous problem is in general undecidable.

Just as undecidability in a system can be proved by establishing a capability for universal computation, so, assuming , computational intractability can be proved through NP-completeness. A problem is NP-complete if specific instances of it correspond to arbitrary problems in the class NP [8, 53]. This can be shown by establishing equivalence to a known NP-complete problem. Thus for example it has been possible to give a specific example of a cellular automaton in which the problem of determining whether particular sequences can occur after time steps is equivalent to the NP-complete problem of finding a set of truth values for variables so that a particular logical expression is satisfied [54]. How widespread NP-completeness is in problems concerning cellular automata has yet to be established. But one suspects that it is common in many class 3 and 4 systems.

previous  l  next