| 特殊形式和结构的MSP问题NP完全性研究 |
投稿时间：2020-12-18 修订日期：2021-01-20  点此下载全文 |
| 引用本文： |
| 摘要点击次数: 36 |
| 全文下载次数: 0 |
|
| 基金项目:国家自然科学基金项目（面上项目，重点项目，重大项目） |
|
| 中文摘要:针对一个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 MSP problem 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-SAT problems, 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阅读器 |
|
|
|
位访问者,今日访问
