😸

拙訳: 擬多項式時間アルゴリズムとは何か

2021/10/14に公開

上記の記事が分かりやすかったので訳してみます。翻訳に問題がある場合はコメントにてご指摘お願いいたします。

質問

擬多項式時間とは何でしょうか。多項式時間とは何が違うのでしょうか。
擬多項式時間アルゴリズムとして、例えば 0-1 ナップザック問題を $O(nW)$ で解くアルゴリズムや、
$O(\sqrt{n})$ で素数判定を行う試し割り法などがありますが、
これらはなぜ多項式時間とみなされないのでしょうか。

回答

多項式時間と擬多項式時間の違いを理解するために、まず「多項式時間」とは何を意味するのかをきちんと形式的に把握する必要があります。

直感的には、多項式時間とは、ある $k$ に対して時間計算量が $O(n^k)$ と書けることですね。
例えば選択ソートは
$O(n^2)$ の多項式時間アルゴリズムです。一方、巡回セールスマン問題
をしらみつぶしに解く方法は $O(n \cdot n!)$ かかり、多項式時間ではありません。

これらの実行時間はいずれも、入力サイズを記録する変数 $n$ にもとづいて表現されています。
例えば、選択ソートでは $n$ は配列の要素数を指します。また、巡回セールスマン問題では $n$ はグラフの点の数を指します。
この文脈において $n$ が実際に何を意味するかの定義を統一するために、時間計算量の形式的な定義においては、
問題の「入力サイズ」を以下のように定めます。

例えば、仮にソートアルゴリズムの入力が 32bit 整数の配列であれば、入力サイズは、配列の長さを $n$ として $32n$ となります。
また、点の数が $n$ 、辺の数が $m$ のグラフにおいては、入力として与えられるのはおそらく全ての点と辺を表現したリストになり、必要なビット長は
$\Omega(n + m)$ になります。^[1]

この「入力サイズ」の定義の下で、多項式時間の形式的な定義は以下のようになります。

グラフやリスト、木などを扱うアルゴリズムであれば、この定義は、直感的なよく用いられる定義とある程度は一致します。
例えば、32bit 整数の配列をソートするアルゴリズムがあるとしましょう。選択ソートなどを使えば、
実行時間は配列の要素数 $n$ の関数として表す場合 $O(n^2)$ になります。
ところで、配列の要素数 $n$ は入力のビット長とどのような対応関係があったでしょうか。先ほど説明した通り、
入力のビット長 $x$ は $x = 32n$ と書けたのですね。したがって、アルゴリズムの実行時間を $n$ ではなく $x$ で
表しても $O(x^2)$ となり、このアルゴリズムは多項式時間と言えます。

同様に、あるグラフに対して深さ優先探索をすることを考えてみましょう。
時間計算量は、グラフの辺の数を $m$ 、点の数を $n$ として $O(m+n)$ と書けます。^[2] これらの変数は入力ビット長とどのような対応関係があるでしょうか。
もし、入力のグラフが隣接リストで表現されていれば、先ほど説明した通り、必要なビット長は $x = \Omega(n + m)$ で書けます。
したがって、実行時間は $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 is in P という、
ある数が素数か否かを検査する多項式時間アルゴリズムを提唱する論文を発表しました。
これは画期的な成果だと受け止められたわけですが、一体なにがすごいのでしょうか。私たちだって、例えば上のコードのような多項式時間アルゴリズムを知っているじゃないですか。

残念ながらそれは違うのです。思い出してください。アルゴリズムの計算量の形式的な定義は、入力のビット長の関数として考えなければならないのです。
私たちの知っているアルゴリズムは確かに $O(n^4)$ の時間計算量ですが、入力のビット長から見たときどうなるのでしょうか。
ある数 $n$ を表現するのに必要なビット長は $O(\log n)$ です。したがって、もし入力の $n$ を書き下すために必要なビット長が $x$ であった場合、
このアルゴリズムの実行時間は $O(2^{4x})$ ということになるので、 $x$ の多項式ではないのです。

これが、多項式時間と擬多項式時間の違いの核心です。ある面では、私たちの知るアルゴリズムは $O(n^4)$ であり、多項式時間のように見えます。
しかしながら、形式的な定義のもとにおいては、それは多項式時間ではないのです。

どうしてこのアルゴリズムが多項式時間アルゴリズムではないかを直感的に理解するために、以下のように考えてみてください。
プログラムに長大な計算をさせることを考えます。入力として

10001010101011

を与えたとしましょう。これによって、完了するまでの最悪計算量が $T$ であったとします。
仮に、この入力にたった 1bit を

100010101010111

と付け加えたとします。すると最悪計算量は $2T$ になります。つまり、1bit 入力を増やすだけで、
アルゴリズムがすべき計算の量が2倍になってしまうのです！

あるアルゴリズムが擬多項式時間アルゴリズムであるとは、実行時間が、入力に必要なビット長ではなく入力の数値の多項式で表されることを意味します。
私たちの知る素数判定アルゴリズムは $O(n^4)$ なので擬多項式時間アルゴリズムですが、
入力のビット長 $x$ の関数としてみたとき $O(2^{4x})$ なので多項式時間アルゴリズムではないのです。
"PRIMES is in P" という論文がなぜ画期的なのかというと、その実行時間がおよそ $O((\log n)^{12})$ で表されることを示したからです。
これは入力のビット長の関数で表すと $O(x^{12})$ です。

では、どうしてこの擬多項式時間を多項式時間と区別するのに意味があるのでしょうか。私たちは数を操作する擬多項式時間アルゴリズムをたくさん知っています。
しかしながら、それらは厳密に言えば指数時間アルゴリズムです。この事実は暗号論的に重要です。
もし RSA 暗号を使いたければ、私たちは暗号に使う数が簡単には素因数分解できないことを信じなければなりません。
入力のビット長を巨大な数へと（例えば 1024bit など）増やすことによって、解くのに必要な時間を、
擬多項式時間アルゴリズムでは到底実行不可能なほど長くすることができます。
その一方で、もし私たちが多項式時間アルゴリズムを発見してしまえば、これは成り立たなくなります。
入力のビット数を増やすことで計算量を増やすことはできますが、その増加速度はたかが多項式的な増加量であり、指数的に増えるわけではありませんから。

そうは言ったものの、多くの場合において、入力サイズがそこまで大きくなることはないので、擬多項式時間アルゴリズムを使っても全く問題ありません。
例えばバケットソートの実行時間は、
ソートする配列の最大値を $U$ として $O(n + U)$ です。これは擬多項式時間アルゴリズムです（ $U$ を表現するのに必要なビット長は $O(\log U)$ であり、実行時間は入力のビット長に対して指数時間です）。
もし $U$ が大きくなりすぎないように $U$ を（例えば $2$ などの定数値に）制限するよう手を加えてしまえば、実行時間は $O(n)$ と書けるようになり、
こうすると多項式時間アルゴリズムになります。これは基数ソートがうまくいく仕組みにもなっています。
基数ソートにおいては、数を1桁ずつ処理していくことで、それぞれの桁の処理時間が $O(n)$ になり、全体として $O(n \log U)$ で動作します。
これは確かに多項式時間アルゴリズムになっています。なぜならソートする $n$ 個の数を書き下すのに必要なビット長は $\Omega(n)$ であり、
$\log U$ はその最大値を書き下すのに必要なビット数と比例しているからです。

参考になれば幸いです！

脚注

$n+m$ で下から抑えられるということ ↩︎
$O(m)$ で書けるはずですが、 $n$ を付け加えても上から抑える値を大きく取ることになるだけなので問題ないはず ↩︎

質問

回答

Discussion