本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
從理論和實踐的角度研究了內部擴散限制聚合（DLA）的計算複雜性。我們證明，對於二維或更多維度，從給定路徑集預測簇的問題對於複雜性類別 CC 來說是完整的，CC 是 P 的子集，其特徵在於由比較器閘組成的電路。 CC 完整性被認為意味著，在最壞的情況下，即使在平行電腦上，成長大小為 n 的群集也需要 n 的多項式時間。提出了一種平行鬆弛演算法，該演算法利用簇接近球形的事實從給定的一組路徑中猜測簇，然後透過非局部湮滅過程糾正猜測的簇中的缺陷。透過在串列計算機上的仿真，研究了二維內部DLA鬆弛演算法的平行運行時間。數值結果與 n 的多對數或 ii 的小冪的運行時間相容。因此，成長大型叢集所需的運算資源平均比最壞情況分析所建議的要少得多。對於具有 le 處理器的平行機，我們表明可以在 O((n/k + 邏輯) n(2/d)) 步驟中產生 d 維度的隨機簇。與顯式順序模擬相比，這顯著加快了速度，顯式順序模擬平均需要 O(n(1 + 2/d)) 時間。最後，我們證明在一維中內部 DLA 可以在 O(log n) 並行時間內預測，在複雜性類別 NC 中也是如此。