正则3-SAT问题的相变现象

• 作者: 张明明 许道云
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 正则CNF公式 SAT问题 相变 变元自由度
• 年，卷（期）: 2016,（4）
• 所属期刊栏目: 2015年全国理论计算机科学学术年会
• 页码范围: 33-36
• 页数: 4页
• 分类号: TP301
• 字数: 5586字
• 语种: 中文
• DOI: 10.11896/j.issn.1002-137X.2016.4.006

摘要

通过对3-CNF公式加以限制,要求其中每个变元出现的次数相同,引出正则3-SAT问题.进一步,通过对两种子句产生机制形成的(3,s)-CNF公式进行可满足性观察,发现在规模较小的情况下,正则3-CNF公式比非正则3-CNF公式更容易满足.从而推测与非正则3-SAT问题相比,正则3-SAT问题的相变点有偏移现象.最后,从变元自由度的角度对这一现象给出了定性解释.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许道云	贵州大学计算机科学与技术学院	125	460	12.0	16.0
2	张明明	贵州大学计算机科学与技术学院	25	98	4.0	9.0