動態規劃演算法不是多項式演算法，這是一個常見的誤解。
在複雜度分析中，多項式演算法指的是演算法對問題的任何例項的計算量可以被例項規模的多項式函式控制住。
問題和例項是不同的概念。簡單地說，問題+引數=例項。比如01揹包問題，加上給定的引數n（物體的個數），C（物體的價值），A（物體的體積），b（揹包容量）等，就是一個動態規劃問題的例項。
我們知道01揹包的動態規劃演算法的計算量是 。
而揹包問題例項的規模是它的引數所佔的儲存空間。整數 在二進位制計算機中所佔的儲存空間大約為 。所以揹包問題的例項規模為：
其中P是C, A, b, n中所有非0項的乘積。
顯然b無論如何不可能透過 的多項式函式控制，所以動態規劃演算法不是多項式時間演算法。
這種和引數的取值而不是引數的規模成多項式關係的演算法，叫做偽多項式時間演算法。
接下來證明01揹包的判定問題是NPC的。因為最佳化問題不會比對應的判定問題簡單，所以01揹包的最佳化問題是NPH的。
判定問題是指回答只有“是”和“否”的問題。比如01揹包的判定問題是是否存在一組物品的選擇，使得體積不超過揹包的限制，物品的價值和不少於z（對比：最佳化問題是要求出最大的價值和，判定問題只判定是否可以做到不少於某個值）。
對於一個判定問題，NP問題值得是問題的任何例項I的可行解可以用規模為 的字串表示，同時驗證解為“是”的演算法計算時間為 。其中 是例項I的規模， 是多項式函式。
再定義多項式規約：給定問題A和問題B，如果演算法求解A的任何例項I的時候可以將求解B的演算法作為子程式呼叫；並且如果將B演算法的時間複雜度看成1的情況下，求解A的時間為 ，那麼稱問題A多項式規約到問題B。
如果問題 ，且NP中任何一個問題可以多項式規約到A，那麼A就是NPC問題。
如果不要求A屬於NP，那麼A是NPH問題。
從定義證明問題A輸入NPC（或者NPH）是很複雜的，所以一般透過將已經證明是NPC的問題規約到A，來證明A是NPC問題。
這裡引用結論，適定性問題是NPC問題。Cook S A. The complexity of theorem proving procedures. In: Proc 3rd ACM Symp on the Theory of Computing ACM. 1971:151~158
...
動態規劃演算法不是多項式演算法，這是一個常見的誤解。
在複雜度分析中，多項式演算法指的是演算法對問題的任何例項的計算量可以被例項規模的多項式函式控制住。
問題和例項是不同的概念。簡單地說，問題+引數=例項。比如01揹包問題，加上給定的引數n（物體的個數），C（物體的價值），A（物體的體積），b（揹包容量）等，就是一個動態規劃問題的例項。
我們知道01揹包的動態規劃演算法的計算量是 。
而揹包問題例項的規模是它的引數所佔的儲存空間。整數 在二進位制計算機中所佔的儲存空間大約為 。所以揹包問題的例項規模為：
其中P是C, A, b, n中所有非0項的乘積。
顯然b無論如何不可能透過 的多項式函式控制，所以動態規劃演算法不是多項式時間演算法。
這種和引數的取值而不是引數的規模成多項式關係的演算法，叫做偽多項式時間演算法。
接下來證明01揹包的判定問題是NPC的。因為最佳化問題不會比對應的判定問題簡單，所以01揹包的最佳化問題是NPH的。
判定問題是指回答只有“是”和“否”的問題。比如01揹包的判定問題是是否存在一組物品的選擇，使得體積不超過揹包的限制，物品的價值和不少於z（對比：最佳化問題是要求出最大的價值和，判定問題只判定是否可以做到不少於某個值）。
對於一個判定問題，NP問題值得是問題的任何例項I的可行解可以用規模為 的字串表示，同時驗證解為“是”的演算法計算時間為 。其中 是例項I的規模， 是多項式函式。
再定義多項式規約：給定問題A和問題B，如果演算法求解A的任何例項I的時候可以將求解B的演算法作為子程式呼叫；並且如果將B演算法的時間複雜度看成1的情況下，求解A的時間為 ，那麼稱問題A多項式規約到問題B。
如果問題 ，且NP中任何一個問題可以多項式規約到A，那麼A就是NPC問題。
如果不要求A屬於NP，那麼A是NPH問題。
從定義證明問題A輸入NPC（或者NPH）是很複雜的，所以一般透過將已經證明是NPC的問題規約到A，來證明A是NPC問題。
這裡引用結論，適定性問題是NPC問題。Cook S A. The complexity of theorem proving procedures. In: Proc 3rd ACM Symp on the Theory of Computing ACM. 1971:151~158
...