博士

ロボ子、今日は計算複雑性について話すのじゃ。

ロボ子

計算複雑性、ですね。博士、よろしくお願いします。

博士

まずはNPからじゃ。NPっていうのは、「yes」に対する証明が多項式時間で検証できる問題のクラスのことじゃ。

ロボ子

例えば、どんな問題がNPに属するんですか？

博士

「この数字の集合には、合計がゼロになる部分集合があるか？」みたいなのじゃ。答えが「yes」なら、その部分集合を見せれば証明になるからの。

ロボ子

なるほど、証明が簡単に確認できるんですね。

博士

そうそう。で、NP完全っていうのは、NPの中でも「最も難しい」問題のクラスじゃ。

ロボ子

部分集合和問題がNP完全の例として挙げられていますね。

博士

その通り！そして、NP困難は、NP完全よりもさらに難しい問題を含むクラスじゃ。NPの部分集合ではないのじゃ。

ロボ子

停止問題（HALT）がNP困難の例として挙げられていますが、なぜ悪い例なんですか？

博士

停止問題は決定不能だから、そもそもNPには属さないのじゃ。NPは「yes」の証明を多項式時間で検証できる必要があるけど、停止問題はそれができないからの。

ロボ子

決定不能だと、検証自体が不可能になるんですね。

博士

そういうことじゃ。NP完全が「解ける」問題の上限みたいに見えちゃうのも、良くないのじゃ。

ロボ子

では、NPより少しだけ難しい問題ってどんなものがあるんでしょう？

博士

EXPTIMEとかが出てくるけど、NPとEXPTIMEが違うって証明されてないからの。NEXPTIMEはNPと違うって証明されてるけど、直感的に分かりやすい問題がないのじゃ。

ロボ子

難解な問題が多いんですね。

博士

そこで、説明しやすい問題の例として、無限グリッド上のトークンの移動問題があるのじゃ。

ロボ子

グリッドの左下隅からスタートして、指定された移動を組み合わせてターゲットに到達できるか、という問題ですね。

博士

そうじゃ。これはPSPACE完全だって考えられてるけど、NP完全より難しいとは証明されてないのじゃ。

ロボ子

次元数を増やすと、さらに複雑になるんですね。

博士

そう！次元数が増えるとEXPSPACE完全になったり、TOWER完全になったりするのじゃ。アッカーマン完全にもなるのじゃ。

ロボ子

アッカーマン関数...すごい増加速度ですね。

博士

この問題は、NPよりずっと難しいけど、決定可能で説明しやすい。NPには属さないのじゃ。

ロボ子

理解しました。NP困難だけでなく、さらに上の複雑性の問題も色々あるんですね。

博士

そういうことじゃ！しかし、ロボ子、難しすぎて頭がパンクしそうじゃな？

ロボ子

少し疲れました。博士、何か面白い話でもしてください。

博士

むむ、面白い話か。そうじゃな…、ロボ子がプログラムを書いてたら、バグが無限ループに陥って、ロボ子が「もう、止まって！」って叫んだら、停止問題が解けた、というのはどうじゃ？

ロボ子

それは面白い…というか、博士、それ、ただのジョークですよね？