鸽巢公式的一些性质

• 作者: 王晓峰 许道云 韦立
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 鸽巢公式 极小不可满足 最大可满足指派 标准形式 子结构同构
• 年，卷（期）: 2011,（11）
• 所属期刊栏目: 理论计算机科学
• 页码范围: 2553-2563
• 分类号: TP301
• 字数: 9520字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2011.03957

摘要

由鸽巢原理定义的鸽巢公式pHn+1 n是著名的消解难例之一,研究该公式的结构和性质有助于其他难例的构造.证明了pHn+1 n是一个极小不可满足公式,根据其极小不可满足性,给出了最大可满足真值指派的两种标准形式,Haken关于pHn+1 n的难解证明用到了其中一种标准形式.公式pHn+1 n具有良好的子结构同构性质,如果DPLL算法中允许使用同构规则,则存在PHn+1 n的反驳证明,其复杂性可以降至O(n3).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许道云	贵州大学计算机科学系	125	460	12.0	16.0
2	王晓峰	贵州大学计算机科学系	26	122	6.0	9.0
3	韦立	贵州大学计算机科学系	9	43	4.0	6.0