NP-Completeness of a Still-Life Question

by Matthew Cook (12 Sep 98)
Contents:

Introduction

In the cellular automaton known as Conway's Game of Life, there is an infinite 2-D square grid of cells, each of which can be either "alive" or "empty". The cells are repeatedly updated in unison according to the rule that a cell will be alive iff on the previous step it had three live neighbors (including diagonals), either including itself or not.

Here are the definitions of some basic Life terms:

It is thought that the problem of distinguishing a strict-still-life from a pseudo-still-life is exponentially hard, but little has been proved in this direction.

Here we show that a slight modification to the definition of pseudo-still-life, namely allowing either 2 or 3 sets of islands, makes the problem NP-complete.

It is still an open problem whether the "two sets" definition or the "any number of sets" definition makes the problem NP-complete.


What We Prove

We will reduce the following two problems to each other using only polynomial-time preprocessing transformations:

SAT:

LIFE-PSEUDO-3: First, we will show that any LIFE-PSEUDO-3 problem can be preprocessed into a SAT problem in polynomial time.
Then we will tackle the harder converse problem, showing that any SAT problem can be preprocessed into a LIFE-PSEUDO-3 problem in polynomial time.


LIFE-PSEUDO-3 ==> SAT

Given a stable Life pattern, we can clearly identify its islands in polynomial time. For each island A,B,C,..., we will use 3 variables in our SAT problem: a1, a2, a3, b1, b2, b3, c1, c2, c3, etc.
The variables a1, a2, and a3 will represent which of the three stable sets island A belongs to, and so on.

Now we just have to pick what terms we will use in the big conjuctive expression.

For each island X, we will have the following terms:

(x1 || x2 || x3) representing that island X must belong to at least one of the stable sets
(!x1 || !x2) representing that for any two sets, island X cannot be in both
i.e. island X may belong to at most one set
(!x1 || !x3)
(!x2 || !x3)
We will also have the two terms:
(a1 || b1 || c1 || ...) representing that the first two sets may not be empty
(a2 || b2 || c2 || ...)
We will not worry about whether the third set is empty, since that case corresponds to a partition of the islands into just two stable sets. Of course, if we wanted to force a partition into three sets, we could include a term for the third set, too.

Finally, we need some more interesting terms, representing the more interesting parts of the problem. These terms must ensure that we
do not partition the islands into unstable sets. As we know, this can be checked by making sure that overcrowded cells adjacent to more
than one island do not wind up with exactly three live neighbors from one of the sets.

So for each empty cell, for each set of adjacent islands that contributes exactly three live neighbors, we will need some terms preventing this problem. The following pattern shows the possibilities:

 . . . . . . . . . A A . B B      1: The cell touches 4 islands 
 . . . . . . . . . A A . B B         * We must avoid exactly 3 in any set 
 . . C . . . . . . . . 1 . . 
 . . C C C . . . . D D . E E      2: The cell touches 3 islands, one of 
 C C . . . C . D . . D . E E         which contributes 3 live neighbors 
 . C . . C C . D D D . . . .         * At least one of the two other islands 
 . C . C . . 2 . 4 . . . . .           must be in the same set as the "3" one 
 . . C C . F F F . . . G G . 
 . . . . 3 F . . F . G . G .      3: The cell touches 3 islands, one of 
 . . H H . . F . F 5 G . . .         which contributes 2 live neighbors 
 . . H . . . . F F . G . G .         * Neither or both of the two others must 
 . . . H . . . . . . . G G .           be in the same set as the "2" one 
 . . H H . . . . . . . . . . 
                                4,5: The cell touches 2 islands, one or both 
                                     of which contribute 3 live neighbors 
                                     * Both islands must be in the same set
For cells of type 1, we will have the following terms for i=1,2,3:
(!ai || !bi || !di || ei) we can't have A & B & D but not E in set i
(!ai || !bi || di || !ei) we can't have A & B & E but not D in set i
(!ai || bi || !di || !ei) we can't have A & D & E but not B in set i
(ai || !bi || !di || !ei) we can't have B & D & E but not A in set i

For cells of type 2, we will have the following term for i=1,2,3:
(!fi || ci || di) we can't have F but not C or D in set i

For cells of type 3, we will have the following terms for i=1,2,3:
(!fi || !ci || hi) we can't have F and C but not H in set i
(!fi || ci || !hi) we can't have F and H but not C in set i

For cells of type 4 and 5, we will have the following term for i=1,2,3:
(!fi || gi) we can't have F but not G in set i

That's it. We're done. Nothing was exponentially complicated in performing this transformation.

And now, for the fun part:


SAT ==> LIFE-PSEUDO-3

Given a SAT problem, we will construct an equivalent LIFE-PSEUDO-3 problem using simple 20x20 building blocks to form the stable pattern.

How we build the Life pattern

These building blocks will have "wires" of cells, and the "value" carried by a wire will be the set that it belongs to.

Here are the building blocks:

A Wire Making a 90 Degree Turn:

 O . . . . . . . . . . . . . . . . . . O
 . O . . . . . . . . . . . . . . . . O .
 . . O . . . . . . . . . . . . . . O . .
 . . . O . . . . . . . . . . . . O . . .
 . . . . O . . . . . . . . . . O . . . .
 . . . . . O . . . O O . . . O . . . . .
 . . . . . . O . O . O . . O . . . . . .
 . . . . . . . O O . O . O . . . . . . .
 . . . . . . . . . . . O . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
   <remaining 10 empty rows not shown>
A "Y" Wire Connection:
 O . . . . . . . . . . . . . . . . . . O
 . O . . . . . . . . . . . . . . . . O .
 . . O . . . . . . . . . . . . . . O . .
 . . . O . . . . . . . . . . . . O . . .
 . . . . O . . . . . . . . . . O . . . .
 . . . . . O . . . O O . . . O . . . . .
 . . . . . . O . O . O . . O . . . . . .
 . . . . . . . O O . O . O . . . . . . .
 . . . . . . . . . . . O . . . . . . . .
 . . . . . . . . . . . . O O O . . . . .
 . . . . . . . . . . . . . . O . . . . .
 . . . . . . . . . . . . O O . . . . . .
 . . . . . . . . . . . . O . . . . . . .
 . . . . . . . . . . . . . O . . . . . .
 . . . . . . . . . . . . . . O . . . . .
 . . . . . . . . . . . . . . . O . . . .
 . . . . . . . . . . . . . . . . O . . .
 . . . . . . . . . . . . . . . . . O . .
 . . . . . . . . . . . . . . . . . . O .
 . . . . . . . . . . . . . . . . . . . O
We also have building blocks for a straight wire, and for empty space, but their construction will be left as an exercise for the reader.

Two Wires Crossing:

 O . . . . . . . . . . . . . . . . . . O 
 . O . . . . . . . . . . . . . . . . O . 
 . . O . . . . . . . . . O O . . . O . . 
 . . . O . . . . . . . . . O . . O . . . 
 . . . . O . . . . . . O . O . O . . . . 
 . . . . . O . . . . O . O . O . . . . . 
 . . . . O O . . . . O . O . . . . . . . 
 . . . . . . O O . O O . O O . . . . . . 
 . . . . . . O . . . . . . . . . . . . . 
 . . . . . . . O . O O . O O . . . . . . 
 . . . . . . O O . O O . O . . . . . . . 
 . . . . . . . . . . . . . O . . . . . . 
 . . . . . . O O . O O . O O . . . . . . 
 . . . . . . . O . O . . . . O O . . . . 
 . . . . . O . O . O . . . . O . . . . . 
 . . . . O . O . O . . . . . . O . . . . 
 . . . O . . O . . . . . . . . . O . . . 
 . . O . . . O O . . . . . . . . . O . . 
 . O . . . . . . . . . . . . . . . . O . 
 O . . . . . . . . . . . . . . . . . . O
What does it mean to say that this is two wires crossing? It means that the wires at opposite corners must belong to the same set, and that which set one pair belongs to is independent of which set the other pair belongs to.

The first thing to notice is that if any wire belongs to the same set as the center block, then the next wire clockwise must also belong to the same set, in order to stabilize a cell diagonally adjacent to the center block. This in turn will force the next wire after that to belong to the same set too, and in the end all four wires together with the center block must belong to the same set.

The other possibility is that the center block does not belong to the same set as any of the wires. In this case, we notice that two adjacent wires may not belong to the same set, since then a cell diagonally adjacent to the center block would be unstable. Since there are only three possible sets, this means that the center cell must belong to one set, and the wires must then alternate between the two other sets, so that opposite wires belong to the same set.

So in summary we see that no matter what, opposite wires must belong to the same set. Furthermore, if one pair of opposite wires belongs to set i, and the other pair belongs to set j, then we can have either i==j (in which case the center block belongs to the same set too), or i!=j (in which case the center block belongs to the third set, not i or j).

Therefore this does in fact correspond to two independent crossing wires.

A Loose Switch:

 O . . . . . . . . . . . . . . . . . . O
 . O . . . . . . . . . . . . . . . . O .
 . . O . . . . . . . . . . . . . . O . .
 . . . O . . . . . . . . . . . . O . . .
 . . . . O . . . . . . . . . . O . . . .
 . . . . . O . . . . . . . . O . . . . .
 . . . . O O . . . . . . . O . . . . . .
 . . . . O . . . . . . . O . . . . . . .
 . . . . . O . . . . . O . . . . . . . .
 . . . . . . O . O . O . . . . . . . . .
 . . . . . . . O O . O O . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . O . O O O . O . . . . . . .
 . . . . . . O O . O . O O . . . . . . .
 . . . . . . . . . . . . . O O . . . . .
 . . . . . . . . . . . . . O . O . . . .
 . . . . . . . . . . . . . . . . O . . .
 . . . . . . . . . . . . . . . . . O . .
 . . . . . . . . . . . . . . . . . . O .
 . . . . . . . . . . . . . . . . . . . O
Here, the wire coming in from the lower right must be in the same set as (i.e. connected to) either the upper right or the upper left, with the other upper wire being free to belong to any set (i.e. disconnected).

We will use the following simplified icons to represent these blocks:

          Wire    Turn      "Y"    Crossing   Loose Switch
           \       \/       \/       '/           ??
            \                \       /,            *
As our last step of preparation, we will examine the following symmetrical arrangement of four switches:
                         P
      \                /
       \      /\      /
        \    /  \    /
         \  /\   \  /
          '/  *   \/
          /,  ??   \  /\
         /  \/  \   ??  \
        /   /    \  *   /
       /   /      \/   /
      /   /\      /   /
     /   *  \    /   /
     \  ??   \  /\  /
      \/  \   ??  '/
          /\   *  /,
         /  \   \/  \
        /    \  /    \
       /      \/      \
      /                \
    Q
Say the upper right wire is in set P and the lower left wire is in set Q (not necessarily distinct).

If P and Q are the same set, then the left loose switch forces the upper left wire to be in this set too, and the right loose switch forces the lower right wire to also be in this set, so all four wires must be in the same set.

Now suppose P is different from Q. Consider the upper left and lower right wires.
The upper loose switch says that one of them must be P, while the lower loose switch says that one of them must be Q.
So they must be different, one being P and one being Q.
But which is which?
One can easily check that the loose switches allow either possibility..

So this is almost the opposite of the "crossed wires" block -- this forms non-crossing connections. This is a essentially a fancy switch, that allows either of the following connectivities for the four wires:

                  \    /        \    /
                   \  /          \__/
                   (  )           __
                   /  \          /  \
                  /    \        /    \
Now, with this Fancy Switch, we are ready to start constructing a pattern for the SAT problem.

We will start by having a row of Fancy Switches, one for each SAT variable. A bunch of wires will dangle down, and we will slowly add stuff onto them.

(Our diagrams will now be rotated 45 degrees from their previous orientation, and they will be at a different scale. "F S" indicates a Fancy Switch, and a "+" indicates that wires are connected.)

     +-----------+-----------+-----------+-----------+-----------+---------+ 
     |           |           |           |           |           |         | 
 +--F S--+   +--F S--+   +--F S--+   +--F S--+   +--F S--+   +--F S--+     | 
 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |     | 
 |   +-----------+-----------+-----------+-----------+-----------+   |     | 
 |       |   |       |   |       |   | False |   |       |   |       |     | 
 |       |   |       |   |       |   |       |   |       |   |       |     |

 a      !a   b      !b   c      !c   d      !d   e      !e   f      !f   True
We will name the upper wire "True" and the horizontal wire underneath all the Fancy Switches "False".

The two wires dropping out the sides of each Fancy Switch will be called x and !x for the Fancy Switch corresponding to variable x.

If True and False belong to the same set, then all the x and !x wires will also belong to this set. If True and False belong to different sets, then the Fancy Switch for x either puts x in True's set and !x in False's set, or else it puts x in False's set and !x in True's set.

Now we need to represent the terms of the big conjunctive expression.

This turns out to be very easy -- we can use loose switches to build up each term.
As an example, we'll show the term (a || b || !d || e).

 a      !a   b      !b   c      !c   d      !d   e      !e   f      !f   True
 |       |   |       |   |       |   |       |   |       |   |       |     |
 +-------------?     |   |       |   |       |   |       |   |       |     |
 |       |   |  *------------------------------? |       |   |       |     |
 |       |   +-?     |   |       |   |       |  *--?     |   |       |     |
 |       |   |       |   |       |   |       +-? |  *----------------------+
 |       |   |       |   |       |   |       |   +-?     |   |       |     |
 |       |   |       |   |       |   |       |   |       |   |       |     |
 a      !a   b      !b   c      !c   d      !d   e      !e   f      !f   True
The first loose switch takes a and b, and produces a wire we will call (a || b). The next loose switch takes this wire and !d, and produces a wire we will call (a || b || !d). The third switch takes this wire and e, and produces a wire we will temporarily call (a || b || !d || e), though we see that this is really the same as the True wire.

First, we note that a,!a,b,!b,etc. are each in True's set or False's set, and so (a || b), (a || b || !d), and (a || b || !d || e) will each also have to be in True's set or False's set (which for all we know are the same set).

At this point we need to specify that after we have represented all the terms of the big conjunctive expression in this way, we terminate all the dangling wires, and we are done making the pattern:

 a      !a   b      !b   c      !c   d      !d   e      !e   f      !f   True
 |       |   |       |   |       |   |       |   |       |   |       |     |
 !       !   !       !   !       !   !       !   !       !   !       !     !
We can terminate each wire with the following simple pattern:
 O . . . . . . 
 . O . . . . . 
 . . O . O . . 
 . . . O O . . 
 . . . . . . . 
 . . . . . . .
So now we see that if True and False are in the same set, then in fact all the wires in the entire pattern must be in the same set, and in fact all the islands in the entire pattern must be in the same set, since the only islands that aren't wires are the blocks at the middle of crossing wires, and if two crossing wires are in the same set, then the block will be in that same set too.

Can the pattern be partitioned into 2 or 3 stable sets?

We have shown that the pattern's islands cannot be partitioned into two or three stable sets if True and False are in the same set.

But what if True and False are in different sets?
Then might it be possible to partition the pattern's islands into 2 or 3 stable sets?

We can define a boolean variable a' to be true iff the wire named "a" is in the same set as the wire True. Since True and False are in different sets, we can conclude that the negation of our boolean variable, !a', will be true iff the wire named "!a" is in the same set as the wire True.

Similarly defining variables b', c', ..., let's look at the loose switches corresponding to a term of the big conjunctive expression.

Considering the term shown above, (a || b || !d || e), we see that the last loose switch says that either e is in True's set, or else (a || b || !d) is in True's set. Working our way back through the loose switches, we see that at least one of a, b, !d, or e must be in the same set as True.

This means that any successful partitioning of the pattern's islands into 2 or 3 stable sets will cause the expression (a' || b' || !d' || e') to be true.

A similar conclusion will arise for each of the loose switch arrangments corresponding to a term of the big disjunctive expression, and in the end, we see that the existence of a partitioning of the pattern's islands into 2 or 3 stable sets implies the existence of a solution to the original SAT problem.

(Note that we can force exactly 3 stable sets by having the True and False wires cross, though any nontrivial problem would wind up with 3 sets anyway.)

But is such a partitioning possible exactly when there is a solution to the SAT problem?

Conversely, any solution to the original SAT problem can be used to successfully partition the pattern's islands into 2 or 3 stable sets, so we can conclude that there is a solution to the SAT problem if and only if there is a solution to our LIFE-PSEUDO-3 problem.

Therefore we have shown that any SAT problem can be reduced to a LIFE-PSEUDO-3 problem in a very straightforward way requiring only polynomial time.