混合约束满足问题的复杂度分析

本文分析了随机CSP模型RBmix的分辨率复杂度,该模型的实例由长度不同的约束组成。 对于RBmix模型,已经确定了相变的存在,并且已经精确定位了阈值点。 通过将随机实例编码为CNF公式,可以证明几乎所有RBmix模型实例都没有小于指数大小的树状分辨率证明。 因此,RBmix模型可以在阈值中生成大量硬实例。 该结果对NP完全问题的算法测试和复杂度分析具有重要意义。