多項式時間アルゴリズムの種類についてのメモ

昨日の記事で多項式時間アルゴリズムについて少し触れたのですが、その種類について書いていきたいと思います。

多項式時間アルゴリズムは強多項式時間アルゴリズムと弱多項式時間アルゴリズムに分かれます。

それぞれの定義から例題を通して理解を深めていきたいと思います。

まずはざっと定義を列挙していきます。

○強多項式時間アルゴリズム

問題 P を解くアルゴリズムが次を満たすとき，それを強多項式時間アルゴリズムと呼ぶ
　1. P を解くときに実行する四則演算と比較の回数がインスタンスの次元の多項式で抑えられる
　2. P を解くときに使用する領域量がインスタンスのサイズの多項式で抑えられる

○弱多項式時間アルゴリズム

多項式時間アルゴリズムで強多項式時間アルゴリズムでないものを弱多項式時間アルゴリズムと呼ぶ

○擬多項式時間アルゴリズム

入力数値が 1 進符号化されるとき，多項式時間で実行できるアルゴリズム

入力数値が1や2進数として仮定したときに多項式時間かどうかをみるというわけです。

入力数値が自然数 a1, a2, . . . , an であるときを考えましょう。

a1, a2, . . . , an

まずは入力サイズを調べなければ始まりません。

入力は10, 3 , 15, 23のように10進数の数字が4(=4)個並んでいます。

10進数を2進数で表記したときにbitの数は $log_2k$ (ex. 最初の要素は $log_210$ )になることを考慮しながら計算すると入力サイズは以下の式で表せます。

$\sum_{i=1}^n log_2a_i$

また $a_{max} = \max_{1 \leq i \leq n} a_i$ とすると以下のようにみなすこともできます。

$\sum_{i=1}^n log_2a_i = n・log_2a_{max}$

$O(nlog_2a_{max})$ という計算時間のアルゴリズムがあるとして、入力データと照らし合わせながらみてみると、入力データの多項式(定数cに対して $O(n^c)$ )で表らされている。つまりこの計算時間のアルゴリズムは多項式時間アルゴリズムとなります。

次に１進数だと仮定して入力サイズを考えてみましょう。

10進数の値，例えば10を考えた時に1進数にすると1が10個あることになります。つまりは10進数の値と1の数が一致しているというわけです。

このことから入力サイズを考えます。

$\sum_{i=1}^n a_i = na_{max}$

$O(na_{max})$ というアルゴリズムがあるとすると、入力データの多項式(定数cに対して $O(n^c)$ )で表らされているのでこの計算時間のアルゴリズムは擬多項式時間アルゴリズムとなります。

申し訳ないのですが、まだ強多項式時間アルゴリズムと弱多項式時間アルゴリズムの違いへの理解がないのでいずれその記事も書きたいと思います。

とりあえず入力サイズを調べることの大切さが伝われば幸いです。

ではまた。

はなちるのマイノート