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

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

项目编号： No.11626039

项目类型： 专项基金项目

立项/批准年度： 2016

项目学科： 数理科学和化学

项目作者： 周广艳

作者单位： 北京工商大学

项目金额： 3万元

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

中文关键词： MAX 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. T

英文关键词： MAX SAT；Phase transition；Weighting method；hypergraph；Propagation connectivity