P
多項式時間內(nèi)能求解的問題
多項式時間的算法的形式化定義是叨橱，對于規(guī)模為n的輸入典蜕，在最壞情況下的運行時間是O(n的k次冪）断盛，其中k為某一確定常數(shù)。
相對應(yīng)的愉舔，有偽多項式時間算法钢猛，典型的0-1背包問題算法復(fù)雜度為O(nW)，其運行時間與輸入的規(guī)模相關(guān)屑宠，是偽多項式的厢洞。
NP
多項式時間內(nèi)能驗證的問題
驗證方法
驗證方法.png
NPC
是多項式時間內(nèi)能驗證的問題，而且是一個最難的問題典奉。兩個特點1.NP躺翻，2.NP-Hard
關(guān)系
關(guān)系圖.png
證明一個問題是NPC
證明過程.png
NPC問題.png
這些問題時如何通過歸約的技巧證明是NPC的，往下看卫玖。
多項式歸約
目的
我們希望在多項式時間內(nèi)解決一個判斷問題公你。如果這個問題還是NP的，那么它就是一個NPC問題假瞬。
方法
-
簡單恒等
就是說問題A和問題B在時間上是等價的陕靠，這里有一個獨立集和點覆蓋問題
的簡單恒等方式的歸約過程。 -
將特例歸約到一般化的例子
某一特定問題（A）的輸入為該問題的實例脱茉。假設(shè)有另一不同的判定問題B剪芥，已知在多項式時間解決它的算法。我們將A的任何實例 α 轉(zhuǎn)化成B的實例琴许，而且轉(zhuǎn)化過程是多項式時間的税肪，且兩個實例的解相同，也就是說需要證明雙向歸約榜田。
這里是例子：點覆蓋到集合覆蓋的歸約
