特殊形式和結構的MSP問題NP完全性研究

馬蘭 劉新 朱哲

摘 要：針對一個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，λ>表示加標多級圖，其中，V表示頂點集合，E表示邊的集合，S表示多級圖中的唯一源點，D表示多級圖中的唯一匯點，L表示多級圖中的點的級別，〈u，v，l〉表示一條起點為u，終點為v，且v所在級為l的有向邊，λv表示頂點v的邊集。

加標多級圖中每一級都是相互獨立的，且不相鄰的兩級的頂點之間不存在直接相連的邊。多級圖中所有的邊都是有向邊，方向由下面一級指向上面一級。每級都有一個及以上的頂點，且每個頂點都有指定的頂點邊集。點和邊的數量和層級決定了多級圖的形狀和結構，而邊集實際上是一種“控制”。

由簡單路徑的定義可知，簡單路徑是從源點S經過各個級中的某個頂點到達匯點D的路徑，且每個頂點的邊集都包含路徑中頂點所在層級以下的路徑上所有的邊。

判斷一個加標多級圖中簡單路徑的存在性。稱為MSP問題，即多級圖簡單路徑（Multistage-graph Simple Path）問題。

因為L-2級的點出度大于1，那么“撕裂”操作（如圖1）使得原來L-2級的點分為多個部分，在算法的計算過程中，CompESS1，D，RE≠φ的要求可能得不到滿足，歸納假設無法繼續進行。基于這個考慮，文獻[1]關于算法證明部分，要求了對輸入的圖和輸入的邊集ESS，必須滿足一個條件，即ESSL-1：L=EL-1：L。使得“撕裂”操作不會減少解。

但是這個要求ESSL-1：L包含更多的邊的條件，給壓縮過程（如圖2）帶來了問題，會使得壓縮后出現增加解（即增加簡單路徑）的情況，于是文獻[1]對于壓縮得到的圖又進行了一定改造，將可能增加的包含于ESS的簡單路徑消除。證明也隨之變得復雜。

經過對證明過程的研究，可以猜想對于一些特殊結構的圖，問題會變得簡單。例如，對于任意頂點b，如果b是多入度點時，b一定是單出度點，那么，對“撕裂”后的新圖G1，Comp（ESS1，D，R（E））≠？的要求完全可以滿足，因為在這樣的特殊結構下，從v到D只有一條路徑。因此，后續的修改就不再必要。在這種特殊結構下，在證明中省略一些性質，可以大大簡化討論。

基于這個想法，提出特殊形式的MSP問題。定義如下：

經計算得CompλD，D，RE≠φ，該圖存在簡單路徑。

由例1可以看出，特殊形式和結構的MSP問題與MSP問題在基本概念的定義、簡單路徑求解、約束關系等方面都是相同的。只有結構方面，特殊結構和形式的MSP問題中，奇數層級指向偶數層級的邊連接的兩級的頂點，點與點數量相等且一一相連。在這種結構下，多入度且多出度的點不復存在。因此，這種特殊結構下MSP問題算法的證明可能會變得簡潔。但只有提出的特殊結構的MSP問題仍然具備NP完全性質才能進行這樣的研究。如果不具備NP完全性質，研究這些特殊結構的MSP問題的多項式時間算法的意義將大打折扣。

2 特殊形式的MSP問題的NP完全性研究

COOK 定理之后，要證明一個問題Q是NP完全問題分為三步：

（1） 證明問題Q屬于NP。

（2） 選擇一個已知的 NP完全問題Q'。

（3） 構造從 Q'到Q的多項式變換函數 f。

首先是第一步，特殊形式的MSP問題顯然是NP問題，只要猜測一條路徑并代入驗證是否是簡單路徑即可。第二步和第三步，可以選擇SAT問題作為已知的NP完全問題，并構造SAT問題歸結到特殊形式的MSP問題的多項式變換函數。

SAT問題是指對于一個給定的、由n個不同命題變元組成的集合的M={x1，x2……xn}，以及M上的一個合取范式φ，是否存在對M中命題變元的一組為TRUE或FALSE的指派，使得φ的值為真。選擇SAT問題的原因是，SAT問題中合取范式的子句和文字的構造，與多級圖中的層級以及每級的頂點的構造有異曲同工之妙。同時，對于SAT問題中的合取范式，含有互補文字的子句之間存在約束，而對于MSP問題中的多級圖，有著頂點邊集的約束，以及不同層級之間不存在直接相連的邊的約束。因此，SAT問題與MSP問題結構與約束都十分相似。因此選擇SAT問題作為已知的NP完全問題，并構造SAT問題歸結到特殊形式的MSP問題的多項式變換函數。

根據MSP問題和SAT問題的相似性，將合取范式中的子句轉化為多級圖中的層級，子句中的文字用每級的頂點表示，由于合取范式φ中有文字存在互補關系的約束條件，將多級圖頂點的邊集設置為除去所有與該頂點互補的頂點相連的邊之外的所有的邊的集合的任一子集。記為λvilEe∨e∈E，e包含頂點vjl，1≤j≤L}。

2.1 SAT問題歸結到特殊形式和結構的MSP

特殊形式的MSP問題顯然是NP問題，任意非確定圖靈機只要猜想一條從源點S到匯點D的路徑，再驗證是否為簡單路徑即可，這種猜想和驗證均在多項式時間內完成，因此是NP問題。SAT問題可以在多項式時間O（K3）內歸結到這種特殊形式的MSP問題，因此，綜上所述，特殊形式的MSP問題是NP完全問題。

2.2 SAT問題歸結到特殊形式和結構的MSP問題實例

計算得到CompλD，D，RE≠φ，即圖中存在簡單路徑，也就是說存在一組對變量x，y，z，r的TRUE或FALSE的指派，使得F為真。

3 結 論

定義了一種特殊形式和結構的MSP問題，并將SAT問題歸結到了特殊形式和結構的MSP問題。同時給出了特殊形式和結構的MSP問題的NP完全性證明。這將為MSP問題的研究提供新參考。同時，這種歸結的產生，也為MSP問題算法正確性證明提供一種新思路，即通過特殊形式和結構的MSP問題來歸納證明。關于這方面，已經做了初步的工作，針對文獻[1]中提出的算法，編程實現并進行特殊形式和結構的MSP問題實例測試，采用歸納假設的思路對文獻[1]證明過程進行重寫等。

參考文獻

[1] 姜新文.哈密頓圖判定問題的多項式時間算法[J].計算機科學，2020，47（7）：8-20.

[2] FORTNOW L. The status of the P versus NP problem[J]. Communications of the ACM， 2009， 52（9）：78-86.

[3] COOK S. The importance of the P versus NP question[J]. Journal of the ACM （JACM）， 2003， 50（1）： 27-29.

[4] COOK S. The complexity of theorem proving procedures[J]. Theory of Computing， 1971， 151-158.

[5] LEVIN L A. Universal sequential search problems[J].Problemy Peredachi Informatsii，1973，9（3）：115-116.

[6] KARP R M. Reducibility among combinatorial problems[C].Complexity of Computer Computations， 1972， 85-103.

[7] JIANG Xin-wen， PENG Li-hong， WANG Qi. MSP problem：its NP-completeness and its algorithm[A]. 2010 Proceedings of the 5th International Conference on Ubiquitous Information Technologies and Applications，2010.

[8] 姜新文，王琪，姜子恒.Z-H算法正確性證明第四次改寫[J].計算技術與自動化，2010，29（3）：35-48.

[9] 樊碩，姜新文.SAT問題可多項式歸結到MSP問題[J].計算機科學，2012，39（11）：179-182.

[10]JIANG Xin-wen， LIU Wan-wei， WU Tian-jun， et al. Reductions from MSP to SAT and from SUBSET SUM to MSP[J]. Journal of Computational Information Systems， 2014， 10（3）： 1287-1295.

[11]吳添君，姜新文.MSP問題NP完全性研究[J].計算機科學， 2015， 42 （7） ：12-14.

[12]姜新文，吳添君，李鵬坤，等.MSP問題的一個求解算法[J].計算技術與自動化，2016，35（1）：60-70.