%0 Journal Article
%T Proving NP-completeness of Polynomial Reduction from the SAT Problem to the MSP Problem<br>SAT问题可多项式归结到MSP问题
%A 樊硕
%A 姜新文
%J 计算机科学
%D 2012
%I 
%X 针对文献巨1]中提出的MSP问题(定义见正文)，从SA I'问题出发，给出sA}r问题到MSP问题的多项式归 结，进而给出MSP问题NP完全性质的另一种证明。
%K MSP problem
%K SAT problem
%K Polynomially reduction
%K NP-completeness<br>MSP问题，SAT问题，多项式归结，NP完全性
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=CBB24D9260C712BB67DA8D5E9CB1F3E0&yid=99E9153A83D4CB11&vid=7C3A4C1EE6A45749&iid=708DD6B15D2464E8&sid=E114CF9BB47B65BE&eid=B1F98368A47B8888&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=0