アークナイツで学ぶ「非決定性多項式時間の問題」前編

ﾌｨﾘｵﾌﾟｼｽｶﾜｲｲﾔｯﾀｰ !!!

「高難易度のマップも攻略できるドクターであれば、いつか非決定性多項式時間の問題も、解明できると予想されます。」

ということで、難解な言葉が多いアークナイツの中でも毛色の違う難解さを誇る「非決定性多項式時間の問題」についての解説です。

0. そもそもどの分野の言葉なのか

計算理論において、時間計算量に関する問題のクラスに言及する時に使います。……といきなり言っても分からんちんなので、自力で調べたい人以外は忘れてください。

ものすごくラフに言うと、ある「問題」を解くのに必要な計算にすごく時間がかかる時に「非決定性多項式時間の問題」とか言ったりします。

ここで言ってる「問題」は、例えばバラバラになった漫画を順番に並べてください、とか観光地を一周していけどどうやったら移動距離が短くなるよ？とかいった、与えられた情報から解答が客観的に決められるものになります。場合によっては解答が一意じゃないかもしれません。この意味で、アークナイツのステージ攻略も「問題」の一例だったりします。

今回注目するのは、こういった「問題」に対する解答をある決まった手順で計算すると導けるような場合に、「問題のサイズ」が大きくなるとどのくらい計算が長くなるか？　という点になります。「バラバラになった漫画を順番に並べる」という「問題」の場合には、「問題のサイズ」は漫画の巻数になります。アークナイツの場合の「問題のサイズ」は……多分ですが、スタージ内の配置可能マスとか、最後の敵が出現するまでの時間とかです。

用語

「問題」に対する解答をある決まった手順で計算すると導けるような場合に、そのような手順のことをアルゴリズムと言います。
ある「問題」をあるアルゴリズムで解くのに必要な計算の量を、その「問題」の時間計算量と言います。計算の途中でどれだけのことを覚えてる必要があるかは空間計算量と言います。
上の用語を使って「非決定性多項式時間」が何なのかと言うと、ある「問題」をあるアルゴリズムで解く時に、その時間計算量がその問題のサイズに対して多項式的に増えていく、ということになります。意味が分かりませんね。これから解説します。

1. 多項式時間とは

多項式、覚えてますか？　私は真面目な定義は若干……というかかなり怪しいです。
今回の話だと、$${x}$$とか$${x^2}$$とか$${x^3}$$とかあったなー……くらいで大丈夫だと思います。

グラフ3種盛り

青が$${x}$$、緑が$${x^2}$$、赤が$${x^3}$$のグラフになります。$${x}$$が大きくなるとともに$${x}$$、$${x^2}$$、$${x^3}$$のどれも大きくなっていくのですけど、肩についてる小さな数字が大きいもの方が急に大きくなっていくのが分かるかと思います。この大きくなりかたが違うことを利用して、注目しているアルゴリズムの時間計算量が問題のサイズについてどのくらい急激に大きくなっていくかを記述したりしたりします。問題のサイズが$${x}$$である時に時間計算量が$${x^2}$$になる、とかそういった具合。

「バラバラになった漫画を順番に並べる」問題の場合、時間計算量は遅いアルゴリズムで$${x^2}$$で、実用的なアルゴリズムだと$${x \mathrm{log} x}$$ くらいになります。(一応条件付きでもっと速いアルゴリズムがあったり、意図的に遅くしたアルゴリズムもあるのはありますが……)

このように、時間計算量をざっくり$${x^n}$$の形で書けるアルゴリズムを、多項式時間で動作するアルゴリズムなどと言います。

そして、なんで多項式時間なんて言ったりするかというと、ものすごく性質の悪い問題には、多項式時間では解けない問題があったりするためです。

グラフ4種盛り。黄色は指数関数。

上のグラフは黄色の線で$${10^x}$$を追加したものです。このような肩に$${x}$$が乗ってるタイプの関数は非常に速く大きくなってしまうため、多項式とは区別されます。

「移動距離を短かくするように観光地を一周する」問題の場合、最適な順番を求めるアルゴリズムの時間計算量はこのような形で非常に速く大きくなってしまうことが知られているため、多項式時間とは呼ばれません。

ここまでをまとめて、「非決定性多項式時間の問題」とは、「(何かが)非決定性であれば、問題のサイズに対して時間計算量が多項式の程度でしか増えない問題」ということになります。

そして次は何が非決定性なのか……という点なのですが、これは結構面倒な話になるので、また今度。