強多項式時間と弱多項式時間

強多項式時間と弱多項式時間について紹介します．
　
＊関数問題と判定問題を同一視してよいのかなど曖昧な箇所があるので後で訂正します

問題のインスタンスがいくつかの数値からなるとき，その問題の多項式時間アルゴリズムをより詳細に，強多項式時間と弱多項式時間のどちらなのかという分類を行います．Time complexity - Wikipedia を参考に書いています．

多項式時間アルゴリズムとはステップ数がインスタンスのサイズの多項式回で抑えられるアルゴリズムのことを言い，インスタンスのサイズとはそのインスタンスを記述するのに必要な総ビット数です．ここでは，問題のインスタンスがいくつかの数値からなる問題を扱います．このとき，数値の個数をインスタンスの次元と呼ぶことにします．また，数値は有理数と仮定します（無理数だとムズカシイ）．下にいくつかの問題の例を挙げます．

例．複数の数値からなる問題

例1. ソーティング問題
　入力　： $n$ 個の整数 $a = (a_1, a_2, \ldots, a_n)$
　出力　： $a'_1 \le a'_2 \le \ldots a'_n$ となる $a$ の並び替え
　サイズ： $\log n + \sum_{i = 1}^{n} \log a_i \le \log n + n A$ 　（ $\,A = \max\{a_1, a_2, \ldots, a_n\}$ ）
　次元　： $n$

例2. 2の冪乗
　入力　：整数 $n$
　出力　： $2^n$
　サイズ： $\log n$
　次元　： $1$

例3. 最大公約数
　入力　：整数 $a, b$
　出力　： $a$ と $b$ の最大公約数
　サイズ： $\log a + \log b$
　次元　： $2$

強多項式時間・弱多項式時間とは？

上のソーティング問題ではインスタンスのサイズが $\log n + n A$ なので，入力の数値を大きくするとサイズも大きくなります．なので，そのような問題のアルゴリズムで計算時間が $O\left((n A)^3 \right)$ となるものも多項式時間アルゴリズムとなります．このとき，次に気になることとして数値によらない多項式時間アルゴリズムが存在するのかということがあります．すなわち，数値の四則演算と比較が単位時間で行える計算モデルを考えたときに，アルゴリズムのステップ数がインスタンスの次元の多項式回で終了するものが存在するかという疑問があります．このような概念を定式化したものが強多項式時間で次の定義になります．

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

定義．弱多項式時間（weakly polynomial time）
多項式時間アルゴリズムで強多項式時間アルゴリズムでないものを弱多項式時間アルゴリズムと呼ぶ

インスタンスのサイズは次元以上になるので，強多項式時間ならば多項式時間となります．したがって，弱多項式時間の定義から強多項式時間と弱多項式時間の関係は次のようになります．
　　　　　　 f:id:tatanaideyo:20190107180042p:plain:w300

上のソーティング問題のアルゴリズムとしてマージソートを考えると，比較回数が $O(n \log n)$ で，領域量が $O(\log n + n A)$ なので強多項式時間アルゴリズムです．

先程，強多項式時間ならば多項式時間が成立つと言いましたが，強多項式時間の定義の条件2を取り除くとこれは成り立たなくなります．上の例題にある2の冪乗の問題が反例となります．入力を $2^n$ とします．このとき，繰返し自乗法を用いると四則演算の回数は $O(n)$ となります．しかし，領域量は少なくとも $2^{2^n}$ 必要となり，これは入力のサイズの指数関数となります．したがって，条件1を満たし，条件2を満たさなく，また使用する領域がサイズの指数関数なので多項式時間アルゴリズムではありません．

次にに弱多項式時間アルゴリズムが存在することを示します．これは例3の最大公約数が対応します．ユークリッドの互除法は $O\left(\log (\min\{a, b\}) \right)$ 時間アルゴリズムです．したがって，最大公約数のサイズ $\log a + \log b$ の多項式なので多項式時間アルゴリズムです．しかし，インスタンスの次元が2なので四則演算の回数を定数回で抑えることができません．したがって，ユークリッドの互除法のこの解析は弱多項式時間となります．ここで注意が必要なのですが，アルゴリズムが弱多項式時間であることを言うためには計算時間の下界を示す必要があります．最大公約数の問題では，少なくとも入力を見る必要があるので $\Omega(\log a + \log b)$ 時間必要であることは明らかです．したがって，ユークリッドの互除法は弱多項式時間アルゴリズムであることが分かります．

まとめ

数値を含む問題に対しては，強多項式時間のアルゴリズムが存在するのかが興味の対象の１つとなります．有名な未解決問題として線形計画問題に強多項式時間アルゴリズムが存在するのかがあります．線形計画問題に弱多項式時間アルゴリズムが存在することは知られています．詳しい文献に藤重先生の資料があるので次を参照してください．
　藤重悟：「線形計画法の最近の発展　線形計画問題の強多項式解法について」
　
================================================
今までよく分からなかったのでまとめた．目指せ強強打破！！