关于随机MAX SAT和(2+p)-SAT模型可满足阈值的研究

The study of phase transition phenomenon and computational complexity near the threshold of the SAT problem, which is the most classical family of constraint satisfaction problems, is the key to understand the nature of hardness of NP complete problems. This project will focus on the random MAX SAT and random (2+p)-SAT problems. By using rigorous mathematical analysis, the weighting method as well as random graph theory, we estimate the exact position of phase transition phenomenon of the two models. This study will help generating benchmarks near satisfiability threshold for testing algorithms, which is of practical value for designing efficient algorithms in technological area. More importantly, it will be of theoretical value for understanding the intrinsic hardness of NP complete problems.

SAT问题作为最经典的约束满足问题，其相变现象及阈值附近复杂性的研究是揭示NP完全问题难解本质的关键之一。本项目将围绕随机MAX SAT和随机(2+p)-SAT两大问题进行研究，旨在通过使用严格的数学概率分析，加权方法，并结合图论等理论工具来估计其精确的可满足阈值点。对SAT问题阈值点的精确估计，不仅有助于在阈值附近生成能测试算法的难解实例，从而构造出高效求解算法，以提高工程技术中复杂问题的求解效率，而且有助于从根本上促进对NP完全问题难解性的理解。

关于随机约束满足问题的相变现象以及其形成机制，特别是在相变区域存在的最难解的实例，是探索NP完全问题难解本质的重要途径之一。本项目主要研究了MAX 3-SAT和MAX 4-SAT的p-可满足阈值问题，以及由长度为2和3的边构成的超图的传播式连通性问题。利用新的二阶矩加权办法，我们得出将MAX 3-SAT和MAX 4-SAT的p-可满足阈值点的上界进行了改进。另一方面，利用Markov过程来刻画传播式连通过程，用概率的方法证明了这种超图随着边密度的增加，会发生由连通到不连通的精确相变，并且求出了该相变点。这一结果能够更深刻了解随机(2+p)-SAT内部变量的赋值之间的制约关系，从而推动其阈值猜想方面的研究，而且能加深对现今社会中的复杂网络的理解。