2-3-SAT问题相变现象剖析及其应用

• 作者: 卜东波 白硕
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: NP完全问题 合取范式 SAT问题 相变现象 可满足概率 2-3-当量
• 年，卷（期）: 1998,（11）
• 页码范围: 0
• 分类号: TP301
• 语种: 中文

摘要

3-SAT问题有一个非常奇妙的相变现象.对于固定的变量数N,合取范式的可满足概率随着子句个数K的变化而发生剧烈的变化;当K≈4.3*N 时,可满足概率急剧地从1变为0.相变现象决定了问题的难易分布,对于快速求解算法的设计有着非常重要的意义.文章着重讨论了SAT问题的更一般形式,即2-3-SAT问题的相变现象.研究了相变点处的2-子句和3-子句个数的关系,发现了2-子句和3-子句在约束能力意义下的当量关系,并提出了如何有效地利用2-3-SAT的相变现象.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	白硕		6	197	5.0	6.0
2	卜东波		1	4	1.0	1.0