馬蘭 劉新 朱哲

摘 要：針對一個NP完全問題，即MSP問題，研究其問題的結(jié)構(gòu)性質(zhì)，猜想特殊的結(jié)構(gòu)可以使其算法證明得到簡化。以簡化證明為導(dǎo)引，提出一種特殊形式和結(jié)構(gòu)的MSP問題。而約束了形狀的特殊形式和結(jié)構(gòu)的MSP問題如果不具備NP完全性，會極大影響進(jìn)一步簡化算法證明的研究意義。因此，提出的特殊形式和結(jié)構(gòu)的MSP問題進(jìn)行了NP完全性質(zhì)證明。類比對SAT問題開展研究時，同樣開展特殊結(jié)構(gòu)的2-SAT問題、3-SAT問題、k-SAT、max-SAT問題研究，特殊形式和結(jié)構(gòu)的MSP問題同樣具有重要意義，并進(jìn)一步推動原問題的研究。

關(guān)鍵詞：MSP問題;多項式歸結(jié);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完全問題在科學(xué)研究和實際應(yīng)用中廣泛存在，是理論計算機(jī)領(lǐng)域最重要的問題。許多基礎(chǔ)性問題表現(xiàn)為NP完全問題，如0-1整數(shù)規(guī)劃、分團(tuán)問題、圖著色問題、最小頂點覆蓋，以及眾多工業(yè)中求最優(yōu)解問題等[2]。NP完全問題遍布人工智能、數(shù)據(jù)庫、程序語言、計算機(jī)網(wǎng)絡(luò)等計算機(jī)科學(xué)領(lǐng)域[3]。

一個問題的NP完全性研究一直是理論計算機(jī)領(lǐng)域重要的方向。上世紀(jì)70年代初Cook[4]給出了NP完全問題的定義，并證明了第一個NP完全問題—SAT問題。接著，Cook還證明了3-SAT問題、團(tuán)問題是NP完全的。幾乎同一時間，Leonid Levin[5]證明了集合覆蓋，及拼磚問題等是NP完全的。隨后Richard Karp[6]進(jìn)一步明確了NP完全的概念，并發(fā)展了多項式歸結(jié)技巧，極大推動了NP完全問題的研究，越來越多的問題被歸入NP完全類。

NP完全問題的研究在七八十年代達(dá)到高潮，隨后趨于平靜。MSP問題的最早提出實際可追溯到2010年[7，8]，隨后陸續(xù)有圍繞MSP問題的研究發(fā)表。如SAT問題歸結(jié)到MSP問題[9]，子集和問題歸結(jié)到MSP問題[10]，著色問題和子圖同構(gòu)問題歸結(jié)到MSP問題[11]等。

2020年發(fā)表的文獻(xiàn)全面論述了MSP問題的準(zhǔn)確定義、多項式時間算法、算法的正確性證明及將哈密頓圖判定問題歸結(jié)到MSP問題，使MSP問題一度成為NP完全問題研究中的新熱點。主要內(nèi)容是對任意輸入的圖G，文獻(xiàn)[1]的算法將計算得到一個判據(jù)，并依據(jù)判據(jù)是否為空，判定一種被稱為“簡單路徑”的路徑的存在性。為了歸納證明算法的正確性，文獻(xiàn)[1]給出了長篇幅的正確性證明。證明利用了MSP問題的結(jié)構(gòu)特性，通過歸納法，分情況討論，逐級分析。

在對證明的分析過程中發(fā)現(xiàn)，若MSP問題的結(jié)構(gòu)上增加一定的限制條件，可能使證明過程中一些需要重點論述的部分得到簡化，那么限制結(jié)構(gòu)以后的MSP問題的算法證明將變得簡單。

類比SAT問題。SAT問題被限制結(jié)構(gòu)成為2-SAT、3-SAT以后，3-SAT在保持了NP完全性的同時，發(fā)揮其結(jié)構(gòu)更簡的優(yōu)勢，應(yīng)用更廣，如今，3-SAT在邏輯推理、人工智能的專家系統(tǒng)、數(shù)據(jù)庫維護(hù)和檢索、VLSI設(shè)計及檢測等領(lǐng)域有廣泛的應(yīng)用，但同樣被限制了結(jié)構(gòu)的2-SAT問題卻不具備NP完全性。

限制了結(jié)構(gòu)的MSP問題被稱為特殊結(jié)構(gòu)的MSP問題。但特殊結(jié)構(gòu)的MSP問題是否仍然保留了NP完全性，需要進(jìn)一步證明，否則，對特殊結(jié)構(gòu)的MSP問題的討論將缺乏意義。所以主要工作包括兩個部分。一是提出一類特殊結(jié)構(gòu)的MSP問題，二是證明提出的問題具備NP完全性質(zhì)，目的是為尋找文獻(xiàn)[1]的算法的簡化提供新的研究方向。

1 特殊形式的MSP問題相關(guān)定義

下面是關(guān)于MSP問題相關(guān)定義的描述。

定義1：G=V，E，S，D，L，λ>表示加標(biāo)多級圖，其中，V表示頂點集合，E表示邊的集合，S表示多級圖中的唯一源點，D表示多級圖中的唯一匯點，L表示多級圖中的點的級別，〈u，v，l〉表示一條起點為u，終點為v，且v所在級為l的有向邊，λv表示頂點v的邊集。

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

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

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

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

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

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

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

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

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

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

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

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

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

（3） 構(gòu)造從 Q'到Q的多項式變換函數(shù) f。

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

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

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

2.1 SAT問題歸結(jié)到特殊形式和結(jié)構(gòu)的MSP

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

2.2 SAT問題歸結(jié)到特殊形式和結(jié)構(gòu)的MSP問題實例

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

3 結(jié) 論

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

參考文獻(xiàn)

[1] 姜新文.哈密頓圖判定問題的多項式時間算法[J].計算機(jī)科學(xué)，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].計算技術(shù)與自動化，2010，29（3）：35-48.

[9] 樊碩，姜新文.SAT問題可多項式歸結(jié)到MSP問題[J].計算機(jī)科學(xué)，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].計算機(jī)科學(xué)， 2015， 42 （7） ：12-14.

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