證明稀疏圖是NP完全的

---

即使有無限的時間，也有一些計算問題是演算法無法解決的。NP完全問題是指其解法未知的問題。有趣的是，如果一個NP完全問題可以在多項式時間內解決，那麼所有其他NP完全問題也可以解決。

在本研究中，我們將定義稀疏圖，討論幾種複雜性類、獨立集，並證明稀疏圖是NP完全的。

什麼是稀疏圖？

稀疏圖是指邊數有限的圖。在這種情況下，邊的總數遠小於可能存在的邊數或最大可能的邊數。有向圖最多隻能包含n(n-1)條邊，其中n表示節點數。無向圖最多隻能有n(n-1)/2條邊。

稀疏圖和稠密圖之間的區別是任意的。稀疏圖的邊數幾乎與頂點數相同，而稠密圖的邊數接近最大可能的邊數。

複雜性類有哪些？

計算機科學中有一些問題尚未解決；這些問題被歸類為複雜性類。

它是計算機理論的一個領域，關注解決任務所需的資源。

基本資源包括時間和空間，它們指的是演算法解決問題需要多長時間以及需要多大的記憶體。

1. P類

P類中的字母P指的是多項式時間。P包含一組可以多項式時間內解決或產生結果的基於決策的問題（只有“是”或“否”答案的問題）。

多項式時間 - 我們在特定時間（例如一分鐘或一小時）內根據特定輸入生成輸出。這被稱為多項式時間。

特點

• P問題有簡單的答案。

• P類包含已解決且易處理的計算問題。

• 理論上和實踐上都可以解決的問題被認為是易處理的。雖然難處理的問題在實踐中無法解決，但原則上可以解決。

2. NP類

NP類包含所有不能在多項式時間內解決或產生結果的基於決策的問題，但可以在多項式時間內驗證其結果。NP類包含幾個子集，包括P類。

請記住，“NP”並不表示“非多項式”。這個術語的意思是“非確定性多項式”。它表示將根據單個輸入建立一定數量的輸出。

由於非確定性演算法可以解決NP問題，因此這類問題的解很難找到，儘管它們的驗證很容易。可以使用圖靈機在多項式時間內解決NP問題。

其他複雜性類

複雜性類	特點
NP-Hard	一些NP-hard問題屬於NP，並且檢查它們很耗時。
NP-完全	NP完全問題既是NP問題，也是NP-hard問題。
Co-NP	“否”答案可以在多項式時間內驗證

獨立集

獨立頂點集定義了圖的頂點的一個子集，其中任意兩個頂點之間都不構成一條邊。

不能被認為是另一個獨立集的合法子集的獨立集被稱為“極大獨立集”。

“最大獨立集”是給定圖中最大的可行獨立集。

如何證明“稀疏圖是NP完全的”？

證明一個問題是NP完全的需要兩個步驟：

證明給定的問題屬於NP類。

稀疏圖是NP-Hard問題之一

透過將問題歸約到另一個NP問題來證明問題的NP完全性可能具有挑戰性。這就是為什麼我們證明每個現有的NP完全問題都可以在多項式時間內歸約到該問題。

稀疏圖屬於NP類

考慮一個輸入G = (V, E)以及兩個整數變數a和b。

檢查特定解S是否滿足|S| = a需要O(|V|)的時間。

為了確保連線S中每一組節點的邊數不超過b，必須使用O(|V|^2)的演算法。

因此，驗證稀疏圖解最多需要O(|V|^2)的時間，因此是多項式時間。因此，稀疏圖屬於NP複雜性類。

接下來，我們將證明獨立集問題是NP完全的

為了確保解中的兩個頂點不相鄰，驗證結果只需要檢查解中的任意兩個頂點之間是否共享一條邊。使用圖G(V, E)的方法，這可以在多項式時間內完成。

flag=true
For each u, v pair in the subset V':
   Make certain that both of these do not have an edge between them.
   Set flag to false and break if there is an edge.
If the flag is set to true:
   Correct Answer.
Else:
   Incorrect answer.

可以從任何獨立集問題的例項建立一個團問題例項。因此，獨立集問題是NP-Hard的。

輸入轉換

獨立集將轉換為稀疏圖，如下所示：

"G' = G(V, E); a = k; b = 0" 

這是因為需要最大化獨立集的數量

此轉換將花費O(1)時間。因此，它是多項式時間的。

輸出轉換

The Sparse Graph solution must be converted into the Independent Set solution.

由於k = a，稀疏圖解產生的集合a是維度為k的獨立集。因此，獨立集可以使用稀疏圖的直接輸出。因為不需要轉換，所以它是多項式時間的。

正確性

預先考慮一個獨立集S。這也指的是稀疏圖，因為S的節點之間沒有任何邊，並且"|S| = k = a"。

稀疏圖的解也是獨立集（頂點之間由零條邊連線，“|S| = k = a”）。

因此，稀疏圖等價於獨立集。

獨立集是NP完全問題。因此，完全歸約需要多項式時間。

因此，稀疏圖也屬於NP完全類別。

結論

即使是工程師也可以從理解NP完全性中獲益。假設你被要求建立一個強大的演算法來解決公司的一個關鍵問題。如果理解NP完全性並證明該問題是NP完全的，則可以自信地暗示不太可能找到多項式時間的解。如果存在多項式時間的解，那麼它將解決計算機科學中的一個重大問題，許多人多年來一直在努力解決這個問題。