Timed Prediction Problem for Sandpile Models
Pablo Concha-Vega (AMU, LIS), Kévin Perrot (AMU, LIS)
我们研究二维沙堆模型中计时预测问题的计算复杂性。 这个问题完善了经典的预测问题,它询问一个单元格q在从给定配置的单元格 p 中添加一个粒后最终是否会变得不稳定。 预测问题在几个设置中被证明是P-complete,包括摩尔社区的子集,但它对冯诺依曼社区的复杂性仍然开放。 在之前的一项工作中,我们为这些小社区提供了交叉闸门(实现非平面单体电路的关键)的完整表征,导致8个相邻单元中只有4个和5个邻居的P完整性证明。 在本文中,我们介绍了时间设置,其中的目标是确定单元格q是否在时间t时变得不稳定。 我们区分了几个案例:一些社区支持完整的计时工具包(包括计时交叉门)并表现出P完整性;另一些社区承认计时交叉,但存在同步问题;平面社区可能不承认任何计时交叉;最后,对于一些剩余的社区,我们猜想没有计时交叉是可能的。
We investigate the computational complexity of the timed prediction problem in two-dimensional sandpile models. This question refines the classical prediction problem, which asks whether a cell q will eventually become unstable after adding a grain at cell p from a given configuration. The prediction problem has been shown to be P-complete in several settings, including for subsets of the Moore neighborhood, but its complexity for the von Neumann neighborhood remains open. In a previous work, we...