とは擬似多項式時間? 多項式時間とどう違うのか？擬似多項式時間で実行されるアルゴリズムの中には、O(nW)のような実行時間を持つものがある（0/1 ナップサック問題) または O(√n) (裁判部門); なぜそれは多項式時間としてカウントされないのでしょうか?
ベストアンサー1
多項式時間と擬似多項式時間の違いを理解するには、まず「多項式時間」の意味を形式化することから始める必要があります。
多項式時間についての一般的な直感は「あるkに対してO(n k )の時間」です。例えば、選択ソートはO(n 2 )で実行され、これは多項式時間である。一方、ブルートフォース法ではTSPS の時間は O(n · n!) かかり、多項式時間ではありません。
これらの実行時間はすべて、入力のサイズを追跡する変数 n を参照します。たとえば、選択ソートでは、n は配列内の要素の数を参照しますが、TSP では、n はグラフ内のノードの数を参照します。このコンテキストで「n」が実際に意味する定義を標準化するために、時間計算量の正式な定義では、問題の「サイズ」を次のように定義します。
問題への入力のサイズは、その入力を書き出すために必要なビット数です。
たとえば、ソート アルゴリズムへの入力が 32 ビット整数の配列である場合、入力のサイズは 32n になります (n は配列内のエントリの数)。n 個のノードと m 個のエッジを持つグラフでは、入力はすべてのノードのリストとそれに続くすべてのエッジのリストとして指定される可能性があり、これには Ω(n + m) ビットが必要になります。
この定義に基づくと、多項式時間の正式な定義は次のようになります。
アルゴリズムは、ある定数 k に対して実行時間が O(x k ) である場合に多項式時間で実行されます。ここで、x はアルゴリズムに与えられた入力のビット数を表します。
グラフ、リスト、ツリーなどを処理するアルゴリズムを使用する場合、この定義は従来の定義とほぼ一致します。たとえば、32 ビット整数の配列をソートするソート アルゴリズムがあるとします。選択ソートなどを使用してこれを行うと、実行時間は、配列内の入力要素の数の関数として、O(n 2 ) になります。しかし、入力配列の要素数 n は、入力のビット数とどのように対応するのでしょうか。前述のように、入力のビット数は x = 32n になります。したがって、アルゴリズムの実行時間を n ではなく x で表すと、実行時間は O(x 2 ) となり、アルゴリズムは多項式時間で実行されます。
同様に、あなたが深さ優先探索グラフ上で、これには O(m + n) の時間がかかります。ここで、m はグラフのエッジの数、n はノードの数です。これは、与えられた入力のビット数とどのように関係しているのでしょうか。入力が隣接リスト (すべてのノードとエッジのリスト) として指定されていると仮定すると、前述のように、入力ビットの数は x = Ω(m + n) になります。したがって、実行時間は O(x) になり、アルゴリズムは多項式時間で実行されます。
しかし、数値を操作するアルゴリズムについて話し始めると、話は別です。数値が素数かどうかをテストする問題について考えてみましょう。数値 n が与えられた場合、次のアルゴリズムを使用して n が素数かどうかをテストできます。
function isPrime(n):
for i from 2 to n - 1:
if (n mod i) = 0, return false
return true
では、このコードの時間計算量はどれくらいでしょうか? 内部ループは O(n) 回実行され、そのたびに n mod i を計算する作業が行われます (非常に控えめな上限として、これは確実に O(n 3 ) の時間で実行できます)。したがって、このアルゴリズム全体は O(n 4 )の時間で実行され、おそらくそれよりはるかに高速です。
2004年に3人のコンピュータ科学者が「PRIMESはPにあります数が素数かどうかをテストするための多項式時間アルゴリズムを提供します。これは画期的な結果と見なされました。それで、何がすごいのでしょうか? これにはすでに多項式時間アルゴリズム、つまり上記のアルゴリズムがあるのではないでしょうか?
残念ながら、そうではありません。時間計算量の正式な定義はアルゴリズムの複雑さについて語っていることを思い出してください。入力ビット数の関数として。このアルゴリズムはO(n 4 )の時間で実行されますが、これは入力ビット数の関数としてはどうでしょうか。数nを書き出すにはO(log n)ビットかかります。したがって、入力nを書き出すために必要なビット数をxとすると、このアルゴリズムの実行時間は実際にはO(2 4x )となり、ないx の多項式。
これが多項式時間と擬似多項式時間の違いの核心です。一方では、私たちのアルゴリズムは O(n 4 ) であり、多項式のように見えますが、他方では、多項式時間の正式な定義では、多項式時間ではありません。
このアルゴリズムが多項式時間アルゴリズムではない理由を直感的に理解するには、次のことを考えてみてください。アルゴリズムに多くの作業を実行させたいとします。入力を次のように記述するとします。
10001010101011
すると、完了するまでに最悪の場合、例えば ほどの時間がかかりますT。ここで1ビット次のように数字の末尾に追加します。
100010101010111
実行時間は (最悪の場合) 2T になります。 1 ビット追加するだけで、アルゴリズムの作業量を 2 倍にすることができます。
アルゴリズムは擬似多項式時間実行時間が多項式である場合入力の数値、ではなく、それを表すために必要なビット数です。私たちの素数テストアルゴリズムは、実行時間 O(n 4 ) で実行されるため擬似多項式時間アルゴリズムですが、入力を書き出すために必要なビット数 x の関数として実行時間が O(2 4x ) であるため、多項式時間アルゴリズムではありません。「PRIMES is in P」論文が非常に重要だった理由は、その実行時間が (およそ) O(log 12 n)であり、ビット数の関数として O(x 12 ) であったためです。
では、なぜこれが重要なのでしょうか。整数を因数分解する擬似多項式時間アルゴリズムは数多くあります。しかし、これらのアルゴリズムは、技術的に言えば、指数時間アルゴリズムです。これは暗号化に非常に役立ちます。RSA 暗号化を使用する場合、数値を簡単に因数分解できないことを信頼できる必要があります。数値のビット数を非常に大きな値 (たとえば 1024 ビット) に増やすと、擬似多項式時間因数分解アルゴリズムにかかる時間が非常に長くなり、数値を因数分解することが完全に不可能になります。一方、多項式時間の因数分解アルゴリズムでは、必ずしもそうとは限りません。ビットを追加すると作業量が大幅に増加する可能性がありますが、増加は指数関数的増加ではなく多項式増加のみです。
とはいえ、多くの場合、数値のサイズが大きすぎないため、擬似多項式時間アルゴリズムはまったく問題ありません。たとえば、カウントソート実行時間はO(n + U)で、Uは配列の最大の数値です。これは擬似多項式時間です（Uの数値を書き出すにはO(log U)ビットが必要なので、実行時間は入力サイズに対して指数関数的になります）。Uが大きすぎないようにUを人為的に制限すると（たとえばUを2にすると）、実行時間はO(n)になり、実際には多項式時間になります。基数ソート1ビットずつ数値を処理することで、各ラウンドの実行時間はO(n)となり、全体の実行時間はO(n log U)となる。これは実際にはは多項式時間です。これは、ソートするために n 個の数値を書き出すと Ω(n) ビットが使用され、log U の値は配列内の最大値を書き出すために必要なビット数に正比例するためです。