论文研究 随机约束满足问题的敏锐阈值

约束满足问题（CSP）中的相变现象在人工智能和计算复杂性理论领域中起着至关重要的作用。 在本文中，我们提出了一种新的随机CSP，称为dp-RB模型，它是RB模型在域大小d和约束紧密度p上的推广。 在该模型中，可变域大小d E [nα，nny]和所有约束均被均匀地分为具有不同约束紧密度p的几组。 通过第二矩方法证明，随着控制参数的增加，dp-RB模型经历了从几乎所有实例都可以满足的区域到几乎所有实例都不能满足的区域的相变。 此外，精确地确定了发生相变的阈值。