命题逻辑的可满足性问题：复杂性和算法

发布时间：2021-07-03 08:16

　　可满足性问题（Satisfiablity问题）在数理逻辑、人工智能、机器学习、约束满足问题、VLSI集成电路设计与检测以及计算机科学理论等等领域具有广阔的应用背景。可满足性问题是第一个NP-Complete问题，并且是一大类NP-Complete问题的核心。大量的实践表明，许多NP-Complete问题无论是对于计算机科学理论还是工程应用都有着至关重要的意义。可满足性问题的重要性以及它的一些奇妙的性质促使我们从问题和算法两个角度来研究它。 我们主要从问题本身的固有性质和快速求解算法两个角度来研究可满足性问题。值得注意的是：这两方面的研究工作是相辅相成、互相促进、互相启发的。从问题的角度，我们着重研究可满足性问题的相变现象以及问题实例的难度。这方面的工作更加清晰地刻划出问题本身的固有属性，从而有助于对问题的完整认识和合理分类，并且针对于各个不同的问题子类可以开发出更有效的算法。从算法的角度，我们分析了完备性算法和不完备性算法的复杂性，比较了两者的优缺点和适用范围，进而提出了将以上两种算法更加完美的结合的思想。我们提出的算法CCSAT和USAT，即分别针对于利用不完备性算法为完备性算... 

【文章来源】：中国科学院大学(中国科学院计算技术研究所)北京市

【文章页数】：72 页

【学位级别】：硕士

【部分图文】：

2.13一AT问题的相变曲线和难度曲线

当问题规模稍大以后，相变曲线就变得非常陡峭，可满足概0.63的点和等于0.5的点靠得非常近，实验记录对这两点难度的不能做到十分得显著，于是这微小的差异常常被不足够精细的实略。但是，仍有一些工作发现了一个奇异的现象，即随着问题规加会观察到“传统”相变点(即Pr(c入，，=TRUE)=.05的点)向的现象。利用上述结果可以对相变点的向左漂移现象给出初步的解释。表中可以看出我们估计的相变点基本稳定在4.21处，因而可以足概率等于(l一1/e)的点看作一个枢轴，随着问题规模的增加，概率曲线慢慢转动，变得越来越陡峭，结果导致“传统”的相变向左漂移。下图是0.DuboiS针对不同的问题规模测得相变曲线数据〔v]l，从图中可以清楚地看出不同规模的相变曲线有一个交点，这个交点不是位于可满足概率等于0.5的地方，而是明显地高于且“传统”的相变点有明显的左漂移现象。

上式表明撇和K满足线性关系。对K求二阶偏导数可以得到同样的论。2一SAT和3一SAT可以视为2一3一SAT的两个特例，因而也必定满足(2)，将2一SAT和3一SAT的相变点作为特殊解代入式(2)，可得:K+加M=P0*N成立。其中:;=’go况g。3二.312……定理3.2.2表明2一3一SAT的相变点处的2一子句个数和3一子句个数足线性关系。其中，兄是2一子句3一子句的当量，它的直观含义是指统计意义下，一个2一子句有相当于兄个3一子句的约束能力。下图是变量数等于100的大量2一3一SAT实例相变点的统计结果。图中显示的可满足概率等于0.63的等值线，x轴表示相变点处的2一子句数目，轴表示相变点处的3一子句数目。从图中可以看出很好的线性，斜率大为一3.13，和我们理论上的预测非常接近。

【参考文献】：
期刊论文
[1]2-3-SAT问题相变现象剖析及其应用[J]. 白硕,卜东波.  软件学报. 1998(11)
[2]求解SAT问题的拟物拟人算法—Solar[J]. 黄文奇,金人超.  中国科学E辑:技术科学. 1997(02)
[3]一种求解合取范式可满足性问题的数学物理方法[J]. 李未,黄文奇.  中国科学（A辑 数学 物理学 天文学 技术科学）. 1994(11)



本文编号：3262208