我明白什麼時候給定的算法可以被稱爲僞多項式，但是我無法找到任何地方如何顯示它與指定的位數有關的指數大小。我的意思是正式證明輸入大小函數與時間複雜度之間的關係是指數函數。 也許基於揹包問題很容易解釋。僞多項式算法 - 算術
是的，我讀過這個線程：What is pseudopolynomial time? How does it differ from polynomial time?
...但它不太我想要的。
在此先感謝
（這是我原來的職位，所以我很樂意詳細說明！）
讓我們的子集和問題的一個例子。在這個問題中，我們想要確定是否有一個包含n個數字的集合S的子集合，它恰好等於W.有一個假多項式時間DP算法，運行時間爲O（nW）。讓我們正式表明這是x的輸入位數。
要做到這一點，我們需要考慮如何構建對這個問題的輸入。如果我們用簡單的英語寫出來，我們可以通過將S中的所有數字寫成逗號分隔的列表來寫下問題的輸入，並在末尾附加W的值。例如，我們可以寫出這樣一個問題：「是否有一個總和爲5的{1,2,3，8，12}的子集？」通過書寫
1,2,3,8,12,5
這是十進制。如果我們寫的二進制數字，我們得到
1,10,11,1000,1100,101
爲了讓整個事情以適應位的一個字符串，我們需要以某種方式與分離穿插編碼這些數字和逗號。爲此，我們將使用標準技巧。我們將加倍所有號碼的位，並以字符串01在這種情況下更換逗號，我們會得到
110111000111110111000000011111000001110011
我們可以解碼此輸入通過讀取關閉規模2，每次塊我們讀了00，我們知道它是0.每次我們讀到11時，我們知道它是1.每當我們讀取01時，我們知道我們已經完成了讀取數字，並應該從下一個開始。
那麼這裏需要多少位？那麼，如果有n個數字，我們將有n個分隔符，需要2n位。如果數字本身總共有b位，我們需要2b空間來存儲它們。最後，我們需要lg W位來寫出W的二進制，所以我們需要2 lg W位來寫出W.這意味着總的位數x表示滿足
x = 2（n + b + lg W）
所以現在看看我們算法的運行時間，它是O（nW）。如果我們的輸入集包含n個副本的數字1，那麼我們輸入的大小將是2（n + 1 + lgW）= 2n + 2 + 2 lg W.如果我們現在選擇W等於2 n ，那麼輸入的大小是2n + 2 + 2n = 4n + 2。這意味着x = 4n + 2，所以n = Θ（x）和W = 2 x = 2 Θ（x）。因此，如果算法的運行時間爲O（nW），則運行時間爲O（x 2 Θ（x）），這是輸入大小的指數。
希望這會有所幫助！