本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：工作論文
- 編號：工作論文 #1167
- 日期：2026-03-18
摘要
我們證明，在有限時間內預測 HPP 或 FHP III 晶格氣體相當於計算任意布林電路的輸出，因此是 P 完整的：也就是說，它與串行計算機在多項式時間內解決的任何其他問題一樣困難。人們普遍認為計算機科學中存在固有的順序問題，而平行處理並不能顯著加速這些問題。除非這是錯誤的，否則即使使用高度並行處理，也不可能比顯式模擬更快地預測晶格氣體。更精確地說，我們無法在平行計算時間 $O<.em>(log^{k}t)$（對於任何 $k$）或 $O(t^{\alpha})$ 中預測晶格氣體的 $t$ 時間步長，除非類 P 分別等於類 NC 或 SP。