SAT问题可多项式归结到MSP问题

• 作者: 姜新文 樊硕
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: MSP问题 SAT问题 多项式归结 NP完全性
• 年，卷（期）: 2012,（11）
• 所属期刊栏目: 人工智能
• 页码范围: 179-182
• 分类号: TP301.5
• 字数: 5097字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2012.11.041

摘要

针对文献[1]中提出的MSP问题(定义见正文),从SAT问题出发,给出SAT问题到MSP问题的多项式归结,进而给出MSP问题NP完全性质的另一种证明.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	姜新文	国防科技大学计算机学院	18	101	6.0	8.0
2	樊硕	国防科技大学计算机学院	2	11	2.0	2.0