论文标题
简化的生活游戏：算法和复杂性
Simplified Game of Life: Algorithms and Complexity
论文作者
论文摘要
生活游戏是一个简单而优雅的模型，用于研究网络上的动态系统。该模型由一个图组成，其中每个顶点具有两种类型之一，即死亡或活着。配置是将顶点映射到类型的映射。一个更新规则描述了给定其邻居类型的顶点的类型。在每一轮中，所有顶点均同步更新，这会导致配置更新。一般而言，生活游戏允许广泛的更新规则，但我们将重点放在两个简单的更新规则的家庭上，即人口不足和人口过剩，这些模型模拟了文献中研究的几种有趣的动态。在这两种情况下，一个死去的顶点都需要至少一定数量的现场邻居才能活着。对于人口不足（分别，人口过剩），一个活的顶点至少需要（最多分别）（最多分解）所需数量的现场邻居才能保持活力。我们研究了这两个规则家族的基本计算问题，例如配置可及性。对于人口不足的规则，我们表明这些问题可以在多项式时间内解决，而对于人口过剩规则，它们是pspace complete。
Game of Life is a simple and elegant model to study dynamical system over networks. The model consists of a graph where every vertex has one of two types, namely, dead or alive. A configuration is a mapping of the vertices to the types. An update rule describes how the type of a vertex is updated given the types of its neighbors. In every round, all vertices are updated synchronously, which leads to a configuration update. While in general, Game of Life allows a broad range of update rules, we focus on two simple families of update rules, namely, underpopulation and overpopulation, that model several interesting dynamics studied in the literature. In both settings, a dead vertex requires at least a desired number of live neighbors to become alive. For underpopulation (resp., overpopulation), a live vertex requires at least (resp. at most) a desired number of live neighbors to remain alive. We study the basic computation problems, e.g., configuration reachability, for these two families of rules. For underpopulation rules, we show that these problems can be solved in polynomial time, whereas for overpopulation rules they are PSPACE-complete.
