證明稠密子圖問題透過泛化是NP完全問題

---

即使有無限的時間，演算法也無法解決所有計算機問題。NP完全問題的答案仍然未知。值得注意的是，如果能夠在多項式時間內解決單個NP完全問題，那麼所有其他問題也可以得到解決。

稠密子圖

在圖論和計算機科學中，稠密子圖是指每個頂點都有很多邊的子圖。

團

團是一個圖的子圖，其中每個頂點都與其他每個頂點相連，使得“子圖”成為一個完全圖。

“最大團問題”的目標是在給定的圖G中找到最大的團，即G的一個子圖，它具有最多的節點。這主要是一個“最佳化”問題。

類似地，“團判定問題”旨在確定在所討論的圖中是否可以找到大小為K的團。

NP完全問題

NP集合中最難的問題是NP完全問題。當且僅當滿足以下條件時，判定問題L才是NP完全的：

• L屬於NP（任何給定的NP完全問題的答案都可以快速驗證，但沒有已知的有效解）。

• 在多項式時間內，所有NP問題都可以規約到L。

證明稠密子圖問題透過泛化是NP完全問題

我們將證明稠密子圖問題是已知NP完全問題的泛化，以建立稠密子圖問題的NP完全性。在本例中，我們將使用眾所周知的團問題作為NP完全基準，如下面的“證明團問題是NP完全問題”中所示，我們需要證明從團問題到稠密子圖問題的規約。

為了證明一個問題是NP完全的，我們必須證明該問題屬於NP類和NP難類。（因為NP完全問題是NP難問題，同時也是NP問題）

“團判定問題”屬於NP類

如果一個問題屬於“NP類”，它必須具有“多項式時間”驗證性，這意味著如果提供一個“證書”，則需要能夠在多項式時間內檢查它是否是該問題的解。

證明

證書 - 假設證書是一個團節點集S，S表示G的“子圖”。

驗證解包括確定圖中是否存在大小為k的團。因此，確定S中頂點的總數是否滿足k需要“O(1)時間”。確定每個頂點是否具有(k-1)的出度需要O(k²)時間。因為在完全圖中，每個頂點都透過一條邊與所有其他頂點相連。因此，完全圖中的邊總數為“kC2 = k*(k-1)/2)”。因此，確定由S中的k個頂點生成的圖是否是完全圖需要“O(k²) = O(n²)”時間（特別是當“k<=n”時，其中n是圖中節點的數量）。

因此，“團判定問題”可以在“多項式時間”內驗證。因此，它屬於“NP類”。

>

“團判定問題”是一個“NP難”問題

如果所有NP問題都在多項式時間內規約到L，那麼問題L就是NP難的。現在考慮Q的團判定問題。為了證明Q屬於NP難，應該選擇一個現有的NP難問題，例如P，並將該問題規約到Q的一個特定情況。如果這種規約需要多項式時間，那麼Q也是一個NP難問題。根據庫克定理，“布林可滿足性問題”（S）是一個NP完全問題。因此，所有NP問題都可以在多項式時間內規約到S。“如果S可以在多項式時間內規約到P，那麼所有NP問題都可以在多項式時間內規約到P”，這證明了Q的多項式時間可規約性。

布林可滿足性問題可以規約到團判定問題的證明

令“E = (y1 v y2) ^ (y1' v y2') ^ (y1 v y3)”是布林表示式，其中y1、y2和y3表示變數，“^”表示邏輯“與”，“v”表示邏輯“或”，y'表示“y的補”。令每個括號內的語句是一個子句。因此，我們有三個子句：P1、P2和P3。假設節點為 –“; ; ; ; ; ”，其中每個節點的第二個項指定它們所屬的子句編號。必須連線節點，以便 -

• 屬於同一子句的頂點之間沒有連線。

• 任何變數與其補之間沒有連線。

因此，根據以下方式組裝“圖G(V, E)” - {“ | a ∈ Ci} 和 E = {(, ) | i ≠ j; b ≠ a' "}。考慮具有節點; ; 的G子圖。它形成一個大小為3的團。因此，賦值 – “ = <0, 1, 1>”使E成立。因此，如果可滿足性表示式中有k個子句，則必須獲得一個大小為k的“最大團”，並且可滿足性表示式對於相關的賦值為真。因此，對於一個特定情況，可滿足性問題簡化為團判定問題。

輸入轉換

必須將團問題的輸入轉換為稠密子圖問題的輸入。

團問題的輸入是一個整數k和一個無向圖G(V, E)。

稠密子圖問題的輸入是一個無向圖G'(V, E)以及一對整數p和q。

我們將以這樣的方式將團問題的輸入資料轉換為稠密子圖問題的輸入資料：

p = k b = (k * (k - 1))/2 G' = G(V, E) p = k q = (k * (k - 1))/2

這種轉換需要O(1)時間，因此是多項式時間的。

輸出轉換

必須將稠密圖問題的解轉換為團問題的解。

由於k = a，稠密圖問題的解產生一個集合a，它是一個大小為k的團。因此，團問題可以直接使用稠密圖問題的輸出。因為不需要轉換，所以它是多項式時間的。

正確性

輸入值b的範圍被限制為(k²)等於(k * (k - 1))/2。

現在我們正在尋找一個具有k個節點和至少(k * (k - 1))/2條邊的子圖。

因為完全圖中的n個頂點最多可以包含(n * (n - 1))/2條邊，所以我們可以說我們的任務是找到一個具有恰好(k * (k - 1))/2條邊的k個節點的子圖，這意味著結果圖必須在每對頂點之間都有一條邊，這只不過是一個k個頂點的團。

同樣，圖G(V, E)上具有k個頂點的團必須包含(k * (k - 1))/2條邊，這意味著它只不過是圖G(V, E)的稠密子圖。

因此，這證明了團問題和稠密子圖問題都有解。

稠密子圖也是NP完全的，因為整個規約需要多項式時間。而且，團問題是NP完全的。

結論

NP完全性的概念與判定問題有關。之所以這樣設計，是因為比較判定問題的複雜性比比較最佳化問題的複雜性更容易。但是，能夠在多項式時間內解決判定問題通常允許我們在多項式時間內解決相關的最佳化問題。