強多項式時間

コンピュータサイエンスにおいて、多項式時間アルゴリズムとは、一般的に、実行時間が入力サイズの多項式関数で上限が定められるアルゴリズムのことである。この定義は、実行時間の測定方法と入力サイズの測定方法を決定する計算モデルに自然に依存する。代表的な計算モデルとして、チューリングマシンモデルと算術モデルが挙げられる。強多項式時間アルゴリズムは、どちらのモデルにおいても多項式時間となるが、弱多項式時間アルゴリズムは、チューリングマシンモデルにおいてのみ多項式時間となる。

強多項式時間と弱多項式時間の違いは、アルゴリズムへの入力が整数または有理数である場合に生じます。これは最適化において特に一般的です。

一般的な計算モデルとしては、チューリングマシンモデルと算術モデルがある。^{[ 1 ] : 32}

• 算術モデルでは、すべての実数に単一のメモリセルが必要であるのに対し、チューリングモデルでは、実数の記憶容量は、それを表現するために必要なビット数によって決まる。
• 算術モデルでは、実数に対する基本的な算術演算（加算、減算、乗算、除算）はすべて1ステップで実行できますが、チューリングモデルでは、各算術演算の実行時間はオペランドの長さに依存します。

あるアルゴリズムは、一方のモデルでは多項式時間で実行されるが、もう一方のモデルではそうではない。例えば、次のようになる。

• ユークリッドアルゴリズムはチューリングモデルでは多項式時間で実行されるが、算術モデルではそうではない。
• n個の数値を読み込んで計算するアルゴリズム$2^2^n$算術モデルでは、繰り返し二乗演算を行うことで多項式時間で実現できるが、チューリングモデルではそうではない。これは、結果を表すために必要なビット数が入力サイズに対して指数関数的に増加するためである。

しかし、アルゴリズムが算術モデルにおいて多項式時間で実行され、かつ、すべての入力、出力、および中間値のバイナリ長が入力値の数の多項式である場合、そのアルゴリズムはチューリングモデルにおいても常に多項式時間で実行されます。このようなアルゴリズムは、強多項式時間で実行されると言われます。

強多項式時間は、計算の算術モデルで定義されます。この計算モデルでは、基本的な算術演算（加算、減算、乗算、除算、比較）は、オペランドのサイズに関係なく、単位時間ステップで実行されます。アルゴリズムが強多項式時間で実行されるのは、次の条件を満たす場合です。^{[ 1 ]}

1. 計算の算術モデルにおける演算回数は、入力インスタンスの整数の数に関する多項式によって制限される。
2. アルゴリズムが使用する空間は、入力サイズに関する多項式によって制限される。

これら2つの特性を持つアルゴリズムは、算術演算をチューリングマシン上で算術演算を実行するための適切なアルゴリズムに置き換えることで、多項式時間アルゴリズムに変換できます。2番目の条件は厳密に必要です。整数が与えられた場合、$2n$（チューリングマシンモデルではnに比例するスペースを占める）計算が可能$2^2^n$繰り返し二乗法を用いたn 回の乗算で表現する。ただし、表現に使用されるスペースは$2^2^n$に比例する$2n$そのため、入力を表すために使用される空間は多項式ではなく指数関数的になります。したがって、この計算をチューリングマシン上で多項式時間で実行することは不可能ですが、多項式回数の算術演算によって計算することは可能です。

しかし、最初の条件については、バイナリエンコードされた入力の長さの多項式で制限されるチューリングマシンステップ数で実行されるが、入力数値の数の多項式で制限される算術演算数を必要としないアルゴリズムが存在する。2つの整数の最大公約数を計算するユークリッドアルゴリズムはその一例である。2つの整数が与えられた場合、${\displaystyle a}$そして${\displaystyle b}$アルゴリズムは、${\displaystyle O(\log a+\log b)}$最大で${\displaystyle O(\log a+\log b)}$ビット。同時に、算術演算の数は入力の整数の数（この場合、入力には常に 2 つの整数しかないため、これは一定）によって制限することはできません。後者の観察により、アルゴリズムは強い多項式時間で実行されません。実際の実行時間は、ビットの長さに依存します。${\displaystyle a}$そして${\displaystyle b}$入力に含まれる整数の数だけでなく、ビット数も考慮する。

多項式時間で実行されるが、強多項式ではないアルゴリズムは、弱多項式時間で実行されると言われます。^{[ 2 ]}弱多項式時間アルゴリズムは知られているが、強多項式時間アルゴリズムを持つことが知られていない問題のよく知られた例は、線形計画法です。弱多項式時間は、問題における値の大きさに依存し、長さに依存しないため真の多項式時間ではない擬似多項式時間と混同してはいけません。