本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：工作論文
- 編號：工作論文 #1236
- 日期：2026-03-18
摘要
我們研究元胞自動機，其中每個站點的狀態由其鄰近站點的多數投票決定。對於一組有限的初始條件，這些等效於零度溫度下伊辛模型的單自旋翻轉動力學中的非零機率躍遷。我們證明，在三個或更多維度上，這些系統可以模擬 AND 和 OR 閘的布林電路，因此是 P 完備的。也就是說，預測未來的狀態 $t$ 時間步長至少與串行電腦上需要多項式時間的任何其他問題一樣困難。因此，除非在電腦科學中廣泛相信的猜想是錯誤的，否則即使使用平行計算來預測多數票細胞自動機或零溫度單自旋翻轉伊辛動力學，在質量上也不可能比顯式模擬更快。