论文部分内容阅读
３－ＳＡＴ问题有一个非常奇妙的变现象，对于固定的变量数Ｎ，合取范式的可满足概率随着子句个数Ｋ的变化而发生剧烈的变化，当Ｋ≈４．３＊Ｎ时，可满足概率急剧地从１变从０．相变现象决定了问题的难易分布，对于快速求解算法的设计有着非常重要的意义，文章着重讨论了ＳＡＴ问题的更一般形式，即２－３ＳＡＴ问题的相变现象，研究了相变点处的２－子句和３－了句个数的关系，发现２－子句和３－子句在约束能力意义下当量关系，并