Complexity of checking validity of downscaled game of life

Question

This is a question I thought up. I'm quite confident the answer is NO, but I'm not sure how to show it, and I'm wondering if this is known.

Imagine you are given a video of a 2k by 2k grid of bounded game of life (I'm not sure this is a standard notion, but I mean that the 2kx2k grid is surrounded by cells that are always forced to be dead), that has been downsampled 2x2 with max. So a 2x2 patch becomes 1 if there is a live cell in it, and 0 if all are dead. For example.

101000
001000
010111
000001
000001
000001

becomes

110
111
001

Let's say the algorithm has been ran for T timesteps. Is there a polynomial-time algorithm (k and T) for finding out whether the video you've been given is consistent with some game of life carried out faithfully?

So if the original game is 2x4, and you receive 00, 00, 00.
The answer is obviously YES. Just take the game with no living cells.

If you receive 01, 10, 01, 10, the answer is NO. It is impossible. Because there is no way for new live cells to appear in the leftmost 2x2 patch, if all of them are currently dead.

I'm 80% sure the answer is NO, seems to me the only general way to check is by iterating over all possible starting states, running the simulation for T timesteps, and checking if the downscaled version ever contradicts what you've been given. This would have exponential complexity $O(T k^2 2^{k^2})$. Game of life is quite general. If you make the patches big enough, you could put complicated things in each patch. However, I'm not sure. I'm also curious if this differs if you instead downscale using maximum, you downscale by getting the number of living cells of each 2x2 patch.

Answer 1

More likely than not this is NP-complete, but proving that will be very challenging. This is almost certainly not known. This answer describes a sketch of how a possible proof might work, because I think it is very unlikely this question will get a complete, definitive answer.

It is possible to build arbitrary logical circuits in Game of Life (GoL). I would imagine it is probably possible to build an "input gate" gadget in your "downscaled GoL validity" problem, where there are two possible initial arrangements for the gate (corresponding to logical 0/1), but we cannot tell from the downscaled history which one of these arrangements was chosen.

These gadgets would then feed into a logical circuit, and solving your downscaled GoL validity problem would require finding initial states for the input gates that lead to a particular outcome of the circuit, which is an NP-complete problem. That would show the NP-hardness of downscaled GoL validity (and the problem is trivially in NP).

The challenge is that we would have to not only build the input gates but also the logic gates meeting two requirements:

1. It's not posssible to see the internal "state" of the logic gates from the downscaled history; we only see the final outcome of the logical circuit;

2. It's not possible to "cheat" (and get the same compressed history) by starting from an arrangement which is substantially different from the intended initial one.

One way that you could possibly achieve (2) is by having a bunch of gliders start off far in the distance, and have their interaction with the circuit (after the computation is finished) somehow reveal more information about how it was built.

Unfortunately, proving this is likely to be a very time-consuming task, because you not only have to figure out how to design these gadgets, you also have to formally prove that they meet these two requirements, for which you might need to enumerate and exclude possible alternative explanations of the compressed history other than the intended ones.

It is possible that whether this problem is NP-complete depends on what factor for the downscaling is chosen: perhaps the downscaling by a factor of 2 is too restrictive and there actually is a clever trick to get enough information from the downscaled history, or perhaps for very large downscaling factors we have a lot more freedom in which cells are alive which perhaps might make solving the problem easier.

Answer 2

Finding a seven by seven area with no valid predecessor is hard enough.