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

Proving NP-completeness of Polynomial Reduction from the SAT Problem to the MSP Problem

作　　者：樊硕[1] 姜新文[1] 

机构地区：[1]国防科技大学计算机学院,长沙410073

出　　处：《计算机科学》2012年第11期179-182,共4页Computer Science

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

摘　　要：针对文献[1]中提出的MSP问题(定义见正文),从SAT问题出发,给出SAT问题到MSP问题的多项式归结,进而给出MSP问题NP完全性质的另一种证明。According to the MSP problem（defined in the body） raised in paper[1],this paper started from the SAT problem and gave the polynomial reduction algorithm from the SAT problem to the MSP problem.Thus we provided another proof to the NP-completeness of the MSP problem.

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

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]