1この「入力サイズ」の定義の下で、多項式時間の形式的な定義は以下のようになります。入力として与えられるビット長のことである。グラフやリスト、木などを扱うアルゴリズムであれば、この定義は、直感的なよく用いられる定義とある程度は一致します。整数の配列をソートするアルゴリズムがあるとしましょう。入力のビット長とどのような対応関係があったでしょうか。なり、このアルゴリズムは多項式時間と言えます。することを考えてみましょう。これらの変数は入力ビット長とどのような対応関係があるでしょうか。いうことになり、このアルゴリズムは多項式時間と言えます。ところが、数に対して何らかの操作をするアルゴリズムを考えだすと、話はうまくいかなくなります。ある数が素数か否かを判定する問題を考えてみましょう。素数かどうかは以下のような擬似コードで確かめられますね。trueではこのコードの時間計算量はどの程度なのでしょうか。程度あれば間違いなく計算できる量でしょう)。程度の時間で実行できることになります(おそらくこれよりも断然速く動くでしょう)。ある数が素数か否かを検査する多項式時間アルゴリズムを提唱する論文を発表しました。これは画期的な成果だと受け止められたわけですが、一体なにがすごいのでしょうか。私たちだって、例えば上のコードのような多項式時間アルゴリズムを知っているじゃないですか。残念ながらそれは違うのです。アルゴリズムの計算量の形式的な定義は、入力のビット長の関数として考えなければならないのです。時間計算量ですが、入力のビット長から見たときどうなるのでしょうか。多項式ではないのです。これが、多項式時間と擬多項式時間の違いの核心です。あり、多項式時間のように見えます。形式的な定義のもとにおいては、それは多項式時間ではないのです。してこのアルゴリズムが多項式時間アルゴリズムではないかを直感的に理解するために、以下のように考えてみてください。プログラムに長大な計算をさせることを考えます。入力として10001010101011を与えたとしましょう。100010101010111と付け加えたとします。アルゴリズムがすべき計算の量が2倍になってしまうのです!あるアルゴリズムが擬多項式時間アルゴリズムであるとは、実行時間が、入力に必要なビット長ではなく入力の数値の多項式で表されることを意味します。多項式時間アルゴリズムではないのです。表されることを示したからです。してこの擬多項式時間を多項式時間と区別するのに意味があるのでしょうか。私たちは数を操作する擬多項式時間アルゴリズムをたくさん知っています。それらは厳密に言えば指数時間アルゴリズムです。この事実は暗号論的に重要です。暗号を使いたければ、私たちは暗号に使う数が簡単には素因数分解できないことを信じなければなりません。擬多項式時間アルゴリズムでは到底実行不可能なほど長くすることができます。その一方で、もし私たちが多項式時間アルゴリズムを発見してしまえば、これは成り立たなくなります。入力のビット数を増やすことで計算量を増やすことはできますが、その増加速度はたかが多項式的な増加量であり、指数的に増えるわけではありませんから。言ったものの、多くの場合において、入力サイズがそこまで大きくなることはないので、擬多項式時間アルゴリズムを使っても全く問題ありません。あり、実行時間は入力のビット長に対して指数時間です)。すると多項式時間アルゴリズムになります。うまくいく仕組みにもなっています。これは確かに多項式時間アルゴリズムになっています。その最大値を書き下すのに必要なビット数と比例しているからです。付け加えても上から抑える値を大きく取ることになるだけなので問題ないはず。