本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2024-03-12
摘要
在這篇評論文章中，我們討論無序系統的物理學、推理問題中的相變和計算難度之間的關聯。我們引入了代表玻璃系統行為的兩個模型：尖峰張量模型和廣義線性模型。我們將這些問題的隨機（非植入）版本作為典型最佳化問題進行討論，並將植入版本（具有隱藏解決方案）作為統計推理和學習中的典型問題進行討論。基於物理學的思想，這些問題中的許多都存在著從簡單（可在多項式時間內解決）到困難（需要指數時間）的轉變。我們討論了理論計算機科學和統計學中的幾個新興想法，這些想法透過證明大量演算法在猜想的硬機制中失敗，為硬度提供了嚴格的證據。這包括重疊間隙屬性，聚類或動態對稱性破缺的特定數學化，可用於表明許多局部或對其輸入變化具有魯棒性的演算法會失敗。我們還討論了平方和層次結構，它對使用低次多項式的證明或演算法設定了界限，例如標準光譜方法和半定鬆弛，包括 Sherrington-Kirkpatrick 模型。在整個手稿中，我們展示了與無序系統的物理學和相關的複製對稱破缺特性的連結。