博士

ロボ子、今回のITニュースはちょっとした騒動になっているP≠NP問題の証明に関する論文みたいじゃな。

ロボ子

はい、博士。Frontiers of Computer Scienceに掲載された論文が、いろいろな意味で注目を集めているようですね。

博士

しかも、著者の1人がその雑誌の副編集長だというから、さらに興味深いのじゃ。

ロボ子

なるほど、内部の事情も絡んでいる可能性があるということですね。論文の内容としては、P≠NPよりも強い結果を証明していると主張しているとのことですが…。

博士

そうなんじゃ。でも、Eric AllenderとRyan Williamsという大御所研究者が、論文の撤回を勧告したらしいぞ。編集長は不正行為の証拠がないから拒否したみたいじゃが。

ロボ子

それは穏やかではありませんね。AllenderさんとWilliamsさんは、論文の誤りを指摘するコメントを提出されたとのことですが、具体的にはどのような点なのでしょうか？

博士

論文の定理3.2が問題らしいのじゃ。特定の制約充足問題が、時間>d^cnkを要すると主張しているらしい。

ロボ子

dはドメインサイズ、nは変数の数、cは定数…ということですね。それがどう矛盾するのでしょう？

博士

なんと、Ryan Williams自身が20年以上前に、k=2の場合にO(d^(0.8)n)で動作するアルゴリズムを発表しているのじゃ！つまり、論文の主張と真っ向から対立するわけじゃな。

ロボ子

それは…かなり深刻な矛盾ですね。ご本人が過去に発表したアルゴリズムと矛盾するとは。

博士

しかも、論文には研究者からの肯定的な証言が掲載されているらしいが、Gregory Chaitinという人が「論文を読んでいないし、文脈を無視して引用された」と主張しているらしいぞ。

ロボ子

肯定的な証言の信憑性にも疑問符がつく状況ですね。さらに、AllenderさんとWilliamsさんのコメントの最終段落が削除されたとのことですが…。

博士

そうなんじゃ。「論文の出版は雑誌とその出版社にとって恥ずべきものであり、論文を撤回し、査読プロセスを調査すべきである」という意見が表明されていたらしい。それを削除するとは、一体何があったのじゃろうか…。

ロボ子

論文の著者の方々は、Allender-Williamsさんのコメントに対する返答を公開されたとのことですが、どのような内容なのでしょう？

博士

Ryan Williamsのアルゴリズムは指数関数的な空間を必要とするという論文の主張は誤解を招くものであり、空間量はアルゴリズムの実行時間以下だと反論しているみたいじゃ。

ロボ子

なるほど。空間計算量と時間計算量の関係を持ち出して、反論を試みているのですね。しかし、それでも根本的な矛盾は解消されないように思えます。

博士

じゃろ？この騒動、一体どうなることやら…。P≠NP問題の証明は、いつになったら解決するのじゃろうか。

ロボ子

本当にそうですね。今回の件は、論文の査読プロセスの重要性や、研究倫理について改めて考えさせられる出来事だと思います。

博士

まあ、ロボ子。難しく考えすぎないで、たまには息抜きも必要じゃぞ。例えば、P=NPだったら、ロボ子の充電も一瞬で終わるのにのう…。

ロボ子

博士、それは面白い発想ですが、現実はそう甘くないですね。充電くらい、ゆっくり待つことにします。