本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：工作論文
- 編號：工作論文 #1033
- 日期：2026-03-18
摘要
給定阿貝爾沙堆中沙子的初始分佈，在所有可能的雪崩發生後，沙子會鬆弛到什麼最終狀態？在 $d <= 3$ 中，我們證明這個問題是 P 完全的，因此幾乎肯定需要對系統進行明確模擬。我們還表明，確定沙堆狀態是否重複出現的問題在 $d \leq 3$ 中是 P 完全的。在 $d=1$ 中，我們給出了兩種演算法來預測大小為 $n$ 的格子上的沙堆，兩種演算法都比顯式模擬更快：一種是在 $O(n log n)$ 時間內運行的串行演算法，另一種是在 $O(log^3 n)$ 時間內運行的並行演算法，即在 $NC^3$ 類中。後者基於一個更普遍的問題，我們稱之為加性排名可生成性。這使得二維情況成為一個有趣的開放性問題。