不同紧度下约束满足问题的相变现象

Phase transitions in random constraint satisfaction problem with various constraint tightness

提出了一个基于RB模型的随机约束满足问题即p-RB模型。该模型考虑了约束紧度的多样性,将所有约束按照不同的权重分成若干组,同一组具有相同的约束紧度,而相异组具有不同的约束紧度。用二阶矩方法严格证明了随着控制参数的不断增加,p-RB模型发生了精确的可满足性相变现象。数值实验表明该模型的有解概率经历了从1到0的突然转变,同时求解难度在相变区域达到高峰,表明该模型在相变区域能产生大量的难解实例。

This paper proposed a random constraint satisfaction problem based on RB model named p-RB model,which took into account the diversity of constraint tightness. The model divided all constraints into several groups in accordance with different weights. The same group had the same constraint tightness,while the different group had different constraint tightness. This paper used the second moment method to prove that p-RB model existed exact satisfiability phase transition phenomenon as the control parameter increased. Numerical experiments show that the satisfiable probability of the model does undergo a sudden change from 1 to 0,and the solving hardness reaches the peak in the phase transition region,which indicates that a large number of intractable instances emerge in the phase transition region.