Show that for one-dimensional cellular automata, CA-Predecessor is in P. Hint: think about using recursion on a one-bit-shorter prefix of the input configuration. Suppose that the CA follows the rule that the configuration shrinks by 2 cells on each update, since the leftmost cell has no left neighbor and the rightmost cell has no right neighbor. Therefore, on input a configuration of length n, we are asking whether there is a predecessor configuration of length n + 2.