擬似多項式時間

計算複雑性理論では、数値アルゴリズムの実行時間が入力の数値（入力に存在する最大の整数）の多項式である場合、そのアルゴリズムは擬似多項式時間で実行されますが、多項式時間アルゴリズムの場合のように入力の長さ（それを表すために必要なビット数）の多項式である必要はありません。^[1]

一般に、入力の数値は入力の長さに対して指数関数的であるため、疑似多項式時間アルゴリズムは必ずしも入力の長さに対して多項式時間で実行されるわけではありません。

既知の擬似多項式時間アルゴリズムによる NP 完全問題は、弱 NP 完全と呼ばれます。P = NPでない限り擬似多項式時間アルゴリズムでは解決できないことが証明されている場合、NP 完全問題は強 NP 完全と呼ばれます。 NP 困難性の強い種類と弱い種類も同様に定義されます。

数nが素数であるかどうかをテストする問題について考えてみましょう。これは、 の数を均等に割り切れるかどうか単純に調べることによって行われます。このアプローチは、最大で 回の除算を必要とします。これは、 n の値に対しては線形以下ですが、n の長さ（約）に対しては指数関数的です。たとえば、 10,000,000,000よりわずかに小さい数n は、 nの長さが 11 桁しかないにもかかわらず、最大で約 100,000 回の除算を必要とします。さらに、このアルゴリズムが実用的でない入力（たとえば、300 桁の数）を簡単に書き留めることができます。計算の複雑さは（エンコードされた）入力の長さに対する難しさの尺度となるため、この単純なアルゴリズムは実際には指数関数的です。ただし、これは擬似多項式時間 です。${\displaystyle \{2,3,\dots ,{\sqrt {n}}\}}$${\displaystyle n}$${\displaystyle {\sqrt {n}}-1}$${\displaystyle \log(n)}$

このアルゴリズムを、真の多項式数値アルゴリズム、つまり加算の簡単なアルゴリズムと比較してみましょう。2 つの 9 桁の数字を加算するには約 9 つの簡単な手順が必要で、一般にこのアルゴリズムは入力の長さに対して真に線形です。加算される実際の数字 (数十億単位) と比較すると、このアルゴリズムは「擬似対数時間」と呼ぶことができますが、このような用語は標準的ではありません。したがって、300 桁の数字を加算することは非現実的ではありません。同様に、長除算は 2 次式です。つまり、m桁の数字はn桁の数字で段階的に除算できます( Big O 表記法を参照)。 ${\displaystyle O(mn)}$

素数判定の場合、nが素数かどうかをテストするための別のアルゴリズム(2002 年に発見) があり、実行時間は であることがわかります。 ${\displaystyle O((\log {n})^{6})}$

ナップザック問題では、重さと価値のアイテムと、ナップザックの最大重量容量が与えられます。目標は、次の最適化問題を解決することです。非公式に言えば、価値を最大化するためにナップザックにアイテムを収める最適な方法は何でしょうか。 ${\displaystyle n}$${\displaystyle w_{i}}$${\displaystyle v_{i}}$${\displaystyle W}$

最大化する${\displaystyle \sum _{i=1}^{n}v_{i}x_{i}}$

および の対象となります。${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W}$${\displaystyle x_{i}\in \{0,1\}}$

この問題を解くのはNP 困難であるため、 P = NPでない限り、多項式時間アルゴリズムは不可能です。ただし、動的計画法を使用すれば時間アルゴリズムは可能です。数値を記述するにはビットのみが必要なので、このアルゴリズムは擬似多項式時間で実行されます。 ${\displaystyle O(nW)}$${\displaystyle W}$${\displaystyle \log W}$

擬似多項式時間の概念は、ほとんど数値問題にのみ使用されますが、この概念は一般化できます。関数mは、 m ( n ) が問題のサイズnの多項式関数と入力の追加プロパティk ( n )より大きくない場合、擬似多項式です 。(おそらく、k は問題に関連するものとして選択されます。) ^{[例が必要]これにより、} k を入力の数値と 見なすことで、数値多項式の問題が特別なケースになります。

数値の値とその長さの区別はエンコードの 1 つです。数値入力が常に単項式でエンコードされる場合、疑似多項式は多項式と一致します。

P≠NPと仮定すると、整数の計算問題では次のことが成り立つ。^[2]

• 問題が弱 NP 困難である場合、その問題には弱多項式時間アルゴリズム(整数の数と最大整数のビット数に関する多項式) はありませんが、擬似多項式時間アルゴリズム (整数の数と最大整数の大きさに関する多項式) は存在する可能性があります。例としては、分割問題があります。弱 NP 困難性と弱多項式時間はどちらも、入力エージェントをバイナリ コーディングでエンコードすることに対応します。

• 問題が強く NP 困難である場合、疑似多項式時間アルゴリズムすら存在しません。また、完全に多項式時間の近似スキームもありません。例としては、3 分割問題があります。強い NP 困難性と疑似多項式時間はどちらも、入力エージェントを単項符号化でエンコードすることに対応します。

• 強くNP完全
• 準多項式時間