本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
在本文中，我們研究了模型 RB 的解空間結構，模型是約束滿足問題 (CSP) 的標準原型，具有不斷增長的領域。使用一階矩方法和二階矩方法，我們嚴格證明，在接近可滿足性轉變的可滿足階段，解被聚類成指數數量的良好分離的簇，每個簇包含次指數數量的解。因此，系統具有聚類（動態）轉變，但沒有凝聚轉變。這張相圖與其他具有固定域大小的經典隨機 CSP 不同，例如 K-可滿足性 (K-SAT) 問題和圖著色問題，其中存在凝聚轉變，並且與可滿足性轉變明顯不同。我們的結果驗證了使用自旋玻璃理論中的腔法獲得的一些非嚴格結果。