混合约束长度满足问题的分簇相变

The Clustering Phase Transition of Random Mixed Constraint Satisfaction Problem

摘要: 随机约束满足问题解空间的结构与问题的难解性之间具有紧密的内在联系。针对随机约束满足问题中固定约束长度模型与实际场景中非均匀约束的差异性，提出了具有混合约束长度的RB^mix模型。基于统计物理的序参量理论，利用解对间Hamming距离演化分析与矩方法相结合，揭示了混合约束满足问题模型解空间的分簇相变。结果表明，当控制参数达到临界阈值时，解空间发生从复本对称态到统计可分簇态的相变，其特征表现为解集内部涌现指数级规模的子簇，且相邻子簇间存在超Hamming距离的能量壁垒。这揭示了分簇相变过程中解空间连通性的突变规律为基于相变特征的组合优化算法设计提供了理论依据。

Abstract: There exists a profound intrinsic connection between the structure of the solution space and the computational hardness of random constraint satisfaction problems (CSPs). To address the discrepancy between fixed constraint length models in random CSPs and the non-uniform constraints in real-world scenarios, the RB^mix model with mixed constraint lengths has been proposed. Leveraging the order parameter theory from statistical physics and combining the analysis of Hamming distance evolution between solution pairs with the moment method, the clustering phase transition in the solution space of the mixed constraint satisfaction problem model has been revealed. The results demonstrate that when the control parameter reaches a critical threshold, the solution space undergoes a phase transition from a replica-symmetric state to a statistically clustered state. This transition is characterized by the emergence of exponentially many sub-clusters within the solution set, accompanied by energy barriers of ultra-Hamming distances between adjacent sub-clusters. This reveals the abrupt change in the connectivity of the solution space during the clustering phase transition, providing a theoretical foundation for the design of combinatorial optimization algorithms based on phase transition characteristics.