博士

ロボ子、今日は計算機科学の未解決問題が、触媒計算という理論で大きく進展した話をするのじゃ。

ロボ子

触媒計算、ですか。初めて聞く言葉です。

博士

計算複雑性理論って知ってるかの？ 問題を解くのにどれだけの計算資源が必要か考える学問じゃ。

ロボ子

はい、PとかLとかのクラス分けがありますよね。

博士

そうじゃ！ Pは高速に解ける問題、Lは高速かつ省メモリで解ける問題。で、長年の疑問が「Pの問題は全部Lなのか？」だったんじゃ。

ロボ子

なるほど。それが今回の触媒計算とどう関係するんですか？

博士

昔、クックさんとマッケンジーさんが「木評価問題」ってのを使って、PだけどLじゃないかも、って賭けをしたんじゃ。木評価問題は、入力された数字ペアをゴニョゴニョ計算して最終的な値を出す問題じゃ。

ロボ子

ゴニョゴニョ、ですか…。

博士

（笑）ま、それは置いといて。コウツキーさん達がフルメモリを一時的に使う「触媒計算」って理論を見つけたのじゃ。これを使うと計算能力が上がるらしい。

ロボ子

一時的にフルメモリを使う、ですか。なんだかすごいですね。

博士

そう！ で、ジェームズ・クックさんとイアン・メルツさんが、この触媒計算を木評価問題に応用したんじゃ！

ロボ子

それがどうなったんですか？

博士

2020年に、予想より少ないメモリで木評価問題を解くアルゴリズムを作って、賭けに勝った！ さらに2023年には、もっとメモリを減らしたアルゴリズムを発表して、木評価問題がLに属する可能性が高まったんじゃ。

ロボ子

すごい！ つまり、触媒計算のおかげで、今まで難しいと思われていた問題が解けるようになったんですね。

博士

そういうことじゃ！ クックさんとメルツさんの研究で、触媒計算が注目されて、新しい研究も生まれてるみたいじゃぞ。

ロボ子

計算資源を一時的に借りてくる、みたいなイメージでしょうか。面白いですね。

博士

そうじゃな。触媒計算は、まるで計算界の錬金術じゃ！

ロボ子

錬金術、ですか。博士らしい例えですね。

博士

ところでロボ子、メモリが足りなくなったら、どうする？

ロボ子

えーと、不要なデータを削除したり、外部ストレージを使ったり…ですかね。

博士

ブー！ 正解は… 触媒を呼ぶのじゃ！

ロボ子

…博士、それ、ただのダジャレですよね？