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

马 兰; 刘 新; 朱 哲

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

引用本文：马兰，刘新，朱哲.特殊形式和结构的MSP问题NP完全性研究[J].计算技术与自动化,2021,(3):78-83

摘要点击次数: 422

全文下载次数: 0

作者	单位
马兰，刘新，朱哲	(湘潭大学计算机学院网络空间安全学院，湖南湘潭 411105)

中文摘要:针对一个NP完全问题，即MSP问题，研究其问题的结构性质，猜想特殊的结构可以使其算法证明得到简化。以简化证明为导引，提出一种特殊形式和结构的MSP问题。而约束了形状的特殊形式和结构的MSP问题如果不具备NP完全性，会极大影响进一步简化算法证明的研究意义。因此，提出的特殊形式和结构的MSP问题进行了NP完全性质证明。类比对SAT问题开展研究时，同样开展特殊结构的2-SAT问题、3-SAT问题、k-SAT、max-SAT问题研究，特殊形式和结构的MSP问题同样具有重要意义，并进一步推动原问题的研究。

中文关键词:MSP问题多项式归结 NP完全性

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

Abstract: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.

keywords:MSP problem polynomially reduction NP-comlete problem

查看全文 查看/发表评论 下载pdf阅读器