NとかNPとか困難とか完全とか（２）

前回、部分和問題とかナップサック問題を例にとって、NP困難とかNP完全を勉強したが、ちょっと気になることがあった。

ナップサック問題はNP-hard、部分和問題はNP-completeだが、アルゴリズマーとしては、「ん？でも動的計画で多項式時間で解けるじゃん？これってクラスPじゃないの？」って思った。
てか、NP-completeの一つであるナップサック問題が多項式時間で解けたら、他のすべてのNP-completeの問題も多項式時間で解けることになって、N=NPになるのでは？?
ん？何か勘違いしてる？

おーそうかDPで解けるのは、要素が整数の場合のみか。実数だとDPじゃ解けない。
てかこの疑似多項式時間ってのは多項式時間と何が違うの？いい情報発見。

強多項式時間問題Πに対するアルゴリズムはその実行時間のオーダーによって次のような名前が与えられる。とのこと。
1. 強多項式時間アルゴリズム (Strongly polynomial time algorithm)
時間計算量がインスタンスIの入力サイズの多項式で抑えられる

2. 弱多項式時間アルゴリズム (Weakly polynomial time algorithm)
時間計算量がインスタンスIの入力サイズ及び入力に含まれる数量のビット数の多項式で抑えられる

3. 擬多項式時間アルゴリズム (Pseudo-polynomial time algorithm)
時間計算量がインスタンスIの入力サイズ及び入力に含まれる数量の多項式で抑えられる

部分和問題の場合は、DPすると、O(ny)になるが、このyがあるから”擬多項式時間”になるわけか。(nとかyとかは前回のブログの問題定義のものです。)

てか、弱多項式時間の数量のビット数って何だ？この分かりにくい表現。要するに、数量のログオーダーって理解でいいのか？

んー、入力に含まれる数量のログオーダーっていう理解でよさそう。
ユークリッドの互除法はO((log a + log b)^2)で、これは、Weakly polynomial timeらしい。