[解決済み] 擬似多項式時間とは何ですか？多項式時間とどう違うのですか？

質問

この質問は 擬似多項式時間 ? 多項式時間とはどう違うのですか？擬似多項式時間で実行されるアルゴリズムの中には、O(nW)のような実行時間を持つものがあります( 0/1 ナップザック問題 ) や O(√n) (たとえば 試行分割 ); なぜそれが多項式時間としてカウントされないのでしょうか？

どのように解決するのですか？

多項式時間と擬似多項式時間の違いを理解するためには、まず「多項式時間」とは何かを正式に理解することから始める必要があります。

多項式時間に対する一般的な直感は、「時間 O(n ^k ) for some k."です。例えば 選択ソート は時間O(n ² という多項式時間であるのに対し、ブルートフォースで解く TSP は多項式時間ではなく O(n - n!)の時間を要します。

これらの実行時間はすべて、入力のサイズを追跡するいくつかの変数nを参照しています。例えば、選択ソートでは、nは配列の要素数を参照し、TSPではnはグラフのノード数を参照します。この文脈で実際に何を意味するのかの定義を標準化するために、時間の複雑さの正式な定義では、問題の大きさを次のように定義しています。

問題への入力の大きさは、その入力を書き出すのに必要なビット数である。

例えば、ソートアルゴリズムの入力が32ビット整数の配列であれば、入力のサイズは32nとなり、ここでnは配列のエントリ数です。n 個のノードと m 個のエッジを持つグラフでは、入力はすべてのノードのリストとすべてのエッジのリストとして指定されるかもしれず、これは Ω(n + m) ビットを必要とします。

この定義から、多項式時間の正式な定義は次のようになります。

アルゴリズムが多項式時間で実行されるのは、その実行時間がO(x ^k ここで、x はアルゴリズムに与えられた入力のビット数を表します。

グラフ、リスト、木などを処理するアルゴリズムを扱う場合、この定義は従来の定義と多かれ少なかれ一致する。例えば、32ビット整数の配列をソートするソートアルゴリズムがあるとします。これを選択ソートのようなもので行うと、配列の入力要素数の関数として、実行時間は O(n ² ). しかし、入力配列の要素数nと入力のビット数はどのように対応するのでしょうか？前述したように、入力のビット数は x = 32n となる。したがって、このアルゴリズムの実行時間をnではなくxで表すと、実行時間はO(x ² ) となり、アルゴリズムは多項式時間で実行されます。

同じように、仮に 深さ優先探索 を行ったとします。このときかかる時間は 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 ³ )). したがって、このアルゴリズム全体は時間O(n ⁴ ) で実行され、おそらくもっと速くなります。

2004 年、3 人のコンピュータ科学者が、次のような論文を発表しました。 PRIMESはP ある数が素数であるかどうかをテストするための多項式時間アルゴリズムを与える。これは画期的な結果だと考えられている。では、何が問題なのだろうか？私たちはすでにこのための多項式時間アルゴリズム、すなわち上記のものを持っているのではないでしょうか？

残念ながら、そうではありません。時間の複雑さの正式な定義が、アルゴリズムの複雑さについて述べていることを思い出してください。 を入力のビット数の関数として説明します。 我々のアルゴリズムは時間O(n ⁴ ) で実行されますが、これは入力ビット数の関数としてどうなのでしょうか？さて、数nを書き出すにはO(log n)ビットが必要です。したがって、入力nを書き出すのに必要なビット数をxとすると、このアルゴリズムの実行時間は、実際にはO(2 ^4x )となり、これは ではなく xの多項式である。

これが多項式時間と擬似多項式時間の違いの核心です。一方、我々のアルゴリズムは、O(n ⁴ ) であり、多項式のように見えますが、他方では、多項式時間の正式な定義の下では、多項式時間ではないのです。

なぜこのアルゴリズムが多項式時間アルゴリズムでないのか、その理由を直感的に理解するために、次のように考えてみてください。アルゴリズムに多くの仕事をさせたいとします。このような入力を書き出すと

10001010101011

の場合、最悪の場合、ある時間、たとえば T といった時間がかかります。もし私が今 を1ビット を数字の末尾に追加すると、このようになります。

100010101010111

これで実行時間は(最悪の場合)2Tになります。もう1ビット追加するだけで、アルゴリズムが行う作業量を2倍にすることができるのです!

あるアルゴリズムの実行時間は 擬似多項式時間 実行時間がある多項式であれば の数値で である場合、実行時間は入力の数値の多項式であり、むしろそれを表現するのに必要なビット数である。我々の素質試験アルゴリズムは擬似多項式時間アルゴリズムであり、時間O(n ⁴ ) で実行されるので擬似多項式時間アルゴリズムですが、入力を書き出すのに必要なビット数xの関数として、実行時間はO(2 ^4x ). PRIMES is in P"の論文が非常に重要だった理由は、その実行時間が（おおよそ）O(log ¹² n)であり、ビット数の関数としてO(x ¹² ).

では、なぜこれが重要なのでしょうか？我々は整数の因数分解について多くの擬似多項式時間アルゴリズムを持っています。しかし、これらのアルゴリズムは、技術的に言えば、指数時間アルゴリズムです。RSA暗号を使う場合、私たちが簡単に数字を因数分解できないことを信頼できるようにする必要があります。数字のビット数を巨大な値（例えば1024ビット）にすることで、擬似多項式時間因数分解アルゴリズムがとらなければならない時間量を大きくすることができ、数字の因数分解は完全に、全く実行不可能になります。一方、もし私たちが 多項式 -多項式時間ファクタリングアルゴリズムを見つけることができれば、これは必ずしもそうではありません。より多くのビットを追加すると、作業が大幅に増加するかもしれませんが、その増加は指数関数的な成長ではなく、多項式的な成長だけでしょう。

とはいえ、多くの場合、擬似多項式時間アルゴリズムは、数値のサイズがあまり大きくならないので、まったく問題ありません。たとえば カウントソート は実行時間 O(n + U) を持ち、ここで U は配列中の最大の数です。これは擬似多項式時間です (U の数値は書き出すのに O(log U) ビットを必要とするので、実行時間は入力サイズに対して指数関数的です)。Uが大きくなりすぎないように人為的に制約をかけると（例えばUを2とすると）、実行時間はO(n)となり、実際には多項式時間となる。このように 基数ソート は、数字を 1 ビットずつ処理することで、各ラウンドの実行時間が O(n) となり、全体の実行時間が O(n log U) となる仕組みです。これは実際には は 多項式時間です。なぜなら、ソートするために n 個の数字を書き出すと Ω(n) ビットを使い、log U の値は配列中の最大値を書き出すのに必要なビット数に正比例するからです。

お役に立てれば幸いです。