Pseudo-polynomial time とは

計算複雑性理論では、実行時間が入力の数値(入力に存在する最大の整数)の多項式である場合、数値アルゴリズムは擬似多項式時間で実行されますが、入力の長さ(必ずしも入力の長さそれを表現するのに必要なビット数)であり、これは多項式時間アルゴリズムの場合である。
一般に、入力の数値は入力長で指数関数であるため、擬似多項式時間アルゴリズムは必ずしも入力長に対して多項式時間で実行されるわけではありません。
既知の擬似多項式時間アルゴリズムのNP完全問題は、弱NP完全と呼ばれます。 NP完全問題は、P = NPでない限り、擬似多項式時間アルゴリズムによって解くことができないことが証明されれば、強くNP完全と呼ばれる。強い/弱い種類のNP硬度も同様に定義される。