摘要 給定阿貝爾沙堆中沙子的初始分佈，在所有可能的雪崩發生後，沙子會鬆弛到什麼最終狀態

本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。

原文連結

• SFI 頁面

論文資訊

• 類型：已發表論文
• 日期：2022-09-02

摘要

給定阿貝爾沙堆中沙子的初始分佈，在所有可能的雪崩發生後，沙子會鬆弛到什麼最終狀態？當 d 大於或等於 3 時，我們證明這個問題是 P 完全的，因此幾乎肯定需要對系統進行明確模擬。我們也證明了確定沙堆狀態是否循環的問題在 d 大於或等於 3 時是 P-完全的，並簡要討論了構造恆等式的問題。在 d = 1 時，我們給出了兩種演算法來預測大小為 n 的格子上的沙堆，兩種演算法都比顯式模擬更快：一種是運行時間為 O(n log n) 的串列演算法，另一種是運行時間為 O(log(3) n) 的平行演算法，即 NC3 類。後者基於一個更普遍的問題，我們稱之為加法排序可生成性。這使得二維情況成為一個有趣的開放性問題。