【算法理論】N NP NPC 問題

算法分析中會把問題分為若幹類。

P問題：指存在多項式時間解法的問題，比如二分查找

NP問題：指存在多項式時間驗證的問題，比如獨立集問題，是否存在size至少為k的獨立集，那麼随便給定一個k大小的點集，驗證是否為獨立集肯定是多項式時間可以完成的。而且在NP中，一般都是針對判定性問題，即把一個optimization的問題轉化為decision的問題。也就是說我們要解決一個optimiazation的問題，比如說找最大的獨立集。那麼可以轉化為是否存在size至少為k的獨立集，然後我們對所有可能的k進行判斷就可以，當然這裡可以使用二分法。

P問題一定是NP的，因為隻需要判定給定的解是否等于計算得到的解就可以。

在可解性的研究中，人們感興趣的是NP是否等于P，即我們目前沒有找到多項式解法的問題是否真的有這樣的解。針對這樣的思考，人們引入了NPC的概念。

NPC：指所有的NP問題都可以多項式規約到它的問題。簡單來講就是NP中最難的問題，隻要這個有多項式解，那麼其餘的NP都有。

這裡的多項式規約是說，比如A問題可以多項式規約到B，那麼A的解決可以通過多項式次調用B來解決，而且這裡B的解法也要求是多項式的。那麼借助B，A可以多項式解決。舉個例子，比如獨立集規約到頂點覆寫。對于一個graph G=（V,E），如果S是頂點覆寫，那麼V-S就是獨立集。

一些簡單結論：（1）NPC問題同樣難，（2）隻要有一個NPC多項式可解，那麼全部NPC多項式可解，即N=NP。

那麼給定一個問題，我們如何證明它是NPC？

（1）首先要證明它是NP問題，給出多項式驗證程式。

（2）證明是NP-hard，找一個已知的NPC，證明這個NPC可以多項式規約到該問題

什麼是NP-hard？簡單來說就是至少比NPC問題還要難的問題，也即，有一個NPC的問題可以被歸約到這個問題。但是不要求存在多項式驗證算法，是以不一定是NP問題，可能是指數級别。是以這裡的（1）（2）一起可以證明是NPC問題。

那麼如何證明NPC可以歸約到這個問題？這是一個難點，我們首先要找到合适的NPC問題，然後指出任意一個這個NPC問題的執行個體均可以轉化成一個（并不要求全部）這個問題的執行個體。選擇合适的NPC問題會簡化這個轉換，不合适可能都無法建構轉換。最後需要證明這個轉換本身是多項時間的。