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

摘要：

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

关键词：MSP问题、SAT问题、多项式归结、NP完全性

所属期刊栏目：39

分类号：TP301.5(计算技术、计算机技术)

资助基金：国防科技大学校预研基金

在线出版日期：2013-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：179-182