特殊形式和结构的MSP问题NP完全性研究  

On the NP-completeness of MSP Problem with a Special Form and Structure

作　　者：马兰 刘新[1] 朱哲[1] MA Lan;LIU Xin;ZHU Zhe(School of Computer Science&School of Cyberspace Science,Xiangtan University,Xiangtan,Hunan 41105,China)

机构地区：[1]湘潭大学计算机学院网络空间安全学院,湖南湘潭411105

出　　处：《计算技术与自动化》2021年第3期78-83,共6页Computing Technology and Automation

基　　金：国家自然科学基金资助项目(61272010)。

摘　　要：针对一个NP完全问题,即MSP问题,研究其问题的结构性质,猜想特殊的结构可以使其算法证明得到简化。以简化证明为导引,提出一种特殊形式和结构的MSP问题。而约束了形状的特殊形式和结构的MSP问题如果不具备NP完全性,会极大影响进一步简化算法证明的研究意义。因此,提出的特殊形式和结构的MSP问题进行了NP完全性质证明。类比对SAT问题开展研究时,同样开展特殊结构的2-SAT问题、3-SAT问题、k-SAT、max-SAT问题研究,特殊形式和结构的MSP问题同样具有重要意义,并进一步推动原问题的研究。An NP-complete problem named MSP problem was found to be structurally reducible.The reduction can simplify the algorithm proof of MSP problem.So we present a MSPproblem with a special form and structure(the special MSP,for short).However,if the special MSP is not NP complete.The subsequent research on simplified proof will be meaningless,so we present the NP-complete proof of the special MSP in this paper.The research of the special MSP is just like when we study SAT problems,we also study SAT problems with special structure such as 3-SATproblems,2-SAT problems,k-SAT problems.Similarly,the special MSP problem is of great significance,and further promotes the research of the MSP problem.

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

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