严格随机正则(3,s)-SAT模型及其相变现象

摘要：

研究变元和文字出现次数受限制的规则3-SAT问题,提出了一种严格随机正则(3,s)-SAT问题,并给出了该问题的实例产生模型-SRR模型.结合一阶矩方法和生成函数展开项系数的渐近近似技术,证明了严格随机正则(3,s)-SAT问题相变点的上界,即当变元规模N较大且变元出现次数s＞11时,严格随机正则(3,s)-SAT实例是高概率不可满足的.实验结果表明:由SRR模型所生成的随机实例中,当N＞60且s＞11时,所有的(3,s)-SAT实例均是不可满足的,而当N＞150且s＜11时,所有的(3,s)-SAT实例均是可满足的,即严格随机正则(3,s)-SAT实例的相变点位于s=11处,且在s=11处(子句变元比为11/3)的严格随机正则(3,s)-SAT实例,比在相变点(子句变元比)4.267处同规模的均匀随机3-SAT实例更难求解,因此,SRR模型可以很方便地在s=11处构造难解的随机3-SAT实例.

关键词：严格正则(3,s)-SAT问题、相变性质、计算复杂性、难解实例产生模型、生成函数

所属期刊栏目：42

分类号：TP301.5(计算技术、计算机技术)

在线出版日期：2017-02-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：2563-2571