本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
我们研究元胞自动机，其中每个站点的状态由其邻近站点的多数投票决定。对于一组有限的初始条件，这些等效于零温度下伊辛模型的单自旋翻转动力学中的非零概率跃迁。我们证明，在三个或更多维度上，这些系统可以模拟 AND 和 OR 门的布尔电路，因此是 P 完备的。也就是说，预测未来时间步长的状态至少与串行计算机上需要多项式时间的任何其他问题一样困难。因此，除非在電腦科學中廣泛相信的猜想是錯誤的，否則即使使用平行計算來預測多數票細胞自動機或零溫度單自旋翻轉伊辛動力學，在質量上也不可能比顯式模擬更快。