论文部分内容阅读
摘 要：针对一个NP完全问题，即MSP问题，研究其问题的结构性质，猜想特殊的结构可以使其算法证明得到简化。以简化证明为导引，提出一种特殊形式和结构的MSP问题。而约束了形状的特殊形式和结构的MSP问题如果不具备NP完全性，会极大影响进一步简化算法证明的研究意义。因此，提出的特殊形式和结构的MSP问题进行了NP完全性质证明。类比对SAT问题开展研究时，同样开展特殊结构的2-SAT问题、3-SAT问题、k-SAT、max-SAT问题研究，特殊形式和结构的MSP问题同样具有重要意义，并进一步推动原问题的研究。
关键词：MSP问题;多项式归结;NP完全性
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.
Key words：MSP problem;polynomially reduction;NP-comlete problem
MSP问题是一个NP完全问题[1]。NP完全问题在科学研究和实际应用中广泛存在，是理论计算机领域最重要的问题。许多基础性问题表现为NP完全问题，如0-1整数规划、分团问题、图着色问题、最小顶点覆盖，以及众多工业中求最优解问题等[2]。NP完全问题遍布人工智能、数据库、程序语言、计算机网络等计算机科学领域[3]。
一个问题的NP完全性研究一直是理论计算机领域重要的方向。上世纪70年代初Cook[4]给出了NP完全问题的定义，并证明了第一个NP完全问題—SAT问题。接着，Cook还证明了3-SAT问题、团问题是NP完全的。几乎同一时间，Leonid Levin[5]证明了集合覆盖，及拼砖问题等是NP完全的。随后Richard Karp[6]进一步明确了NP完全的概念，并发展了多项式归结技巧，极大推动了NP完全问题的研究，越来越多的问题被归入NP完全类。
NP完全问题的研究在七八十年代达到高潮，随后趋于平静。MSP问题的最早提出实际可追溯到2010年[7，8]，随后陆续有围绕MSP问题的研究发表。如SAT问题归结到MSP问题[9]，子集和问题归结到MSP问题[10]，着色问题和子图同构问题归结到MSP问题[11]等。
2020年发表的文献全面论述了MSP问题的准确定义、多项式时间算法、算法的正确性证明及将哈密顿图判定问题归结到MSP问题，使MSP问题一度成为NP完全问题研究中的新热点。主要内容是对任意输入的图G，文献[1]的算法将计算得到一个判据，并依据判据是否为空，判定一种被称为“简单路径”的路径的存在性。为了归纳证明算法的正确性，文献[1]给出了长篇幅的正确性证明。证明利用了MSP问题的结构特性，通过归纳法，分情况讨论，逐级分析。
在对证明的分析过程中发现，若MSP问题的结构上增加一定的限制条件，可能使证明过程中一些需要重点论述的部分得到简化，那么限制结构以后的MSP问题的算法证明将变得简单。
类比SAT问题。SAT问题被限制结构成为2-SAT、3-SAT以后，3-SAT在保持了NP完全性的同时，发挥其结构更简的优势，应用更广，如今，3-SAT在逻辑推理、人工智能的专家系统、数据库维护和检索、VLSI设计及检测等领域有广泛的应用，但同样被限制了结构的2-SAT问题却不具备NP完全性。
限制了结构的MSP问题被称为特殊结构的MSP问题。但特殊结构的MSP问题是否仍然保留了NP完全性，需要进一步证明，否则，对特殊结构的MSP问题的讨论将缺乏意义。所以主要工作包括两个部分。一是提出一类特殊结构的MSP问题，二是证明提出的问题具备NP完全性质，目的是为寻找文献[1]的算法的简化提供新的研究方向。
1 特殊形式的MSP问题相关定义
下面是关于MSP问题相关定义的描述。
定义1：G=V，E，S，D，L，λ
关键词：MSP问题;多项式归结;NP完全性
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.
Key words：MSP problem;polynomially reduction;NP-comlete problem
MSP问题是一个NP完全问题[1]。NP完全问题在科学研究和实际应用中广泛存在，是理论计算机领域最重要的问题。许多基础性问题表现为NP完全问题，如0-1整数规划、分团问题、图着色问题、最小顶点覆盖，以及众多工业中求最优解问题等[2]。NP完全问题遍布人工智能、数据库、程序语言、计算机网络等计算机科学领域[3]。
一个问题的NP完全性研究一直是理论计算机领域重要的方向。上世纪70年代初Cook[4]给出了NP完全问题的定义，并证明了第一个NP完全问題—SAT问题。接着，Cook还证明了3-SAT问题、团问题是NP完全的。几乎同一时间，Leonid Levin[5]证明了集合覆盖，及拼砖问题等是NP完全的。随后Richard Karp[6]进一步明确了NP完全的概念，并发展了多项式归结技巧，极大推动了NP完全问题的研究，越来越多的问题被归入NP完全类。
NP完全问题的研究在七八十年代达到高潮，随后趋于平静。MSP问题的最早提出实际可追溯到2010年[7，8]，随后陆续有围绕MSP问题的研究发表。如SAT问题归结到MSP问题[9]，子集和问题归结到MSP问题[10]，着色问题和子图同构问题归结到MSP问题[11]等。
2020年发表的文献全面论述了MSP问题的准确定义、多项式时间算法、算法的正确性证明及将哈密顿图判定问题归结到MSP问题，使MSP问题一度成为NP完全问题研究中的新热点。主要内容是对任意输入的图G，文献[1]的算法将计算得到一个判据，并依据判据是否为空，判定一种被称为“简单路径”的路径的存在性。为了归纳证明算法的正确性，文献[1]给出了长篇幅的正确性证明。证明利用了MSP问题的结构特性，通过归纳法，分情况讨论，逐级分析。
在对证明的分析过程中发现，若MSP问题的结构上增加一定的限制条件，可能使证明过程中一些需要重点论述的部分得到简化，那么限制结构以后的MSP问题的算法证明将变得简单。
类比SAT问题。SAT问题被限制结构成为2-SAT、3-SAT以后，3-SAT在保持了NP完全性的同时，发挥其结构更简的优势，应用更广，如今，3-SAT在逻辑推理、人工智能的专家系统、数据库维护和检索、VLSI设计及检测等领域有广泛的应用，但同样被限制了结构的2-SAT问题却不具备NP完全性。
限制了结构的MSP问题被称为特殊结构的MSP问题。但特殊结构的MSP问题是否仍然保留了NP完全性，需要进一步证明，否则，对特殊结构的MSP问题的讨论将缺乏意义。所以主要工作包括两个部分。一是提出一类特殊结构的MSP问题，二是证明提出的问题具备NP完全性质，目的是为寻找文献[1]的算法的简化提供新的研究方向。
1 特殊形式的MSP问题相关定义
下面是关于MSP问题相关定义的描述。
定义1：G=V，E，S，D，L，λ