一些简化的NP完全实例类

• 作者: 肖华 许道云 龚平
• 来源期刊: 贵州大学学报（自然科学版）
• 学科: 工学
• 关键词: (k,s)-公式 NP-完全 MU(1) 树规则
• 年，卷（期）: 2005,（2）
• 所属期刊栏目: 专题研究
• 页码范围: 193-202,210
• 页数: 10页
• 分类号: TP301.6
• 字数: 2409字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-5269.2005.02.018

摘要

(k,s)-SAT是命题满足性问题限制在一种特殊的命题公式上, 该命题公式具有每个子句只有k个不同的文字且每个变元出现的次数少于s次的特点.已经验明对于正整数k,s存在一个指数函数f, 满足:对任意s≤f(k), 所有的(k,s)-SAT例都是可满足的, 而(k,f(k)+1)-SAT却是一个NP-完全问题.目前为止, 只知道f(3)和f(4)的精确值.对于f是否可计算是一个仍未解决的问题.由于每个满足某种条件的数值序列对应一个MU(1)中的公式, 在[2]中, 作者S. Horry和S. Seizder 通过对数值序列的运算来构造(k,s)-SAT中的MU(1)公式例, 得到了函数f的可计算上界函数.但当k比较大时, 该方法不太实用.作者定义了一种树规则来减少数值计算的步数, 得到了一个确定的实用的算法来计算函数f的上界, 该上界接近[2]中的上界,同时,也得到了一些NP-完全满足性问题类.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许道云	贵州大学计算机科学系	125	460	12.0	16.0
2	龚平	贵州大学计算机科学系	2	1	1.0	1.0
3	肖华	贵州大学计算机科学系	2	2	1.0	1.0