「多項式時間」について

ここでは複雑性理論での「多項式時間」について話してみようと思います。

\(xもx^2もx^3もx\)の多項式です。もっと一般に、\(a_0+a_1x+a_2x^2+a_3x^3+...+a_nx^n \)の形の式を「xの多項式関数」と呼びます。それぞれの項が、\(x^n\)に係数\(a_n\)が掛かった形をしていて、それらの和で表される関数です。xの多項式関数を\(poly(x)\)で表します。

ただ、\(2^xや3^x\)は、xの多項式とは呼びません。\(a^x\)は、aについてみればaの多項式ですがxについてみればxの多項式ではありません。変数xが「x乗」の形である項の肩に現れる関数を「xの指数関数」と言います。

複雑性の理論では、多項式時間で計算される問題のクラスを Pで表します。

ただ、いくつか注意すべきことがあります。

第一に、何についての多項式かを決めておく必要があります。1+1よりは、1000+1000の方が計算には時間がかかります。一般に、入力に与えられるデータが単純なものより複雑なものに計算には時間がかかるはずです。入力の大きさをnで表した時、計算時間をnの関数\(f(n)\)で表します。「多項式時間で計算される」というのは、入力の大きさをnとする時、その計算時間が、多項式\( poly(n)\)で表せるということです。

第二に、注意すべきことは、計算量を時間ではかるには、二つのやり方があるということです。一つは、実際に実行時間を実時間ではかるやり方です。もう一つは、たとえて言えば、コンピュータで何クロックその処理にかかるのかをはかるやり方です。

複雑性理論での時間計算量は、後者のアプローチをとります。計算を、基本的な要素に分解して、その基本操作の何ステップで処理が終わるかで、時間をはかります。正確な定義は後で述べますが、直感的にいうとチューリングマシンの一命令の実行を時間の単位にします。

そうすると面白いことが起きます。

ある問題が多項式時間で計算される複雑性のクラスPに属するとします。ムーアの法則で、コンピュータの処理速度が指数関数的に増大したとしても、基本動作が早くなるだけで、処理に必要なステップが短くなる訳ではありません。ですので、実際の実行時間がいくら速くなっても、その問題が多項式時間のクラスPに属することに変わりはありません。

もっと面白いのは、こうした考えを進めていくと、「時間」について興味深いアプローチが可能になるということです。

nビットの入力を取るある電子「回路」を考えます。どんな処理を行う回路も、基本的な操作を行うANDゲート、ORゲート、NOTゲートの組み合わせで構成できます（多分、XORゲートだけで出来るはずです）。この時、この処理の実行時間は、ゲートの「個数」に対応します。「多項式時間」で実行される回路は、多項式\(poly(n)\)で表される数のゲートを持ちます。時間は、ゲートの数で表されます。

すこし、わき道に入ってしまいました。

実行時間ではかられる計算量と計算複雑性の時間計算量は、アプローチは違うことを強調したのですが、第三に注意したいことは、そうした違いにもかかわらず、両者は結びついているということです。関心の向いている方向が違うと思っていいと思います。

n個のものを大きさの順に並べ替えるSORTの処理を考えましょう。SORTには、様々なアルゴリズムがありますが、アルゴリズムに応じて計算量は異なります。例えば、単純なバブル・ソートでは実行時間は \(n^2\)に比例しますが、quick-sortでは、\(nlog(n)\)に高速化できます。

こうした時、\(n^2\) あるいは\(nlog(n)\)に対応した計算複雑性を考えることは、もちろんできます。\(n^2\)は、多項式時間のPに属しますが、\(nlog(n)\)は、nの多項式ではありません。Pとは別の、\(nlog(n)\)という計算複雑性を考えることは可能です。

ただ、アルゴリズムに注目する、実時間的アプローチの実践的な関心は、その高速化、計算時間の下限の追求にあります。一方、多項式時間 Pというクラスを設定した複雑性理論の関心は、もう少し別のところ、もう少し抽象的な複雑性の性質に向けられています。そのことをおいおい説明したいと思います。