一見すると、今夏の計算理論会議で発表された大きなニュースは、やや期待外れに見えた。40年以上にわたり、研究者たちは、DNA分子内の化学記号の長い並びのような任意の二つの文字列を比較する、より良い方法を見つけようとしてきた。最も広く使われているアルゴリズムは遅く、あまり賢いとは言えない。二つのリストを一段ずつ下り、各段階で値を比較していくのである。この「編集距離」を計算するより良い方法が見つかれば、研究者は完全なゲノムや大規模データセットを素早く比較できるようになり、コンピュータ科学者は、この分野のさらなる問題に取り組むための強力な新しいツールを手にすることになるだろう。
しかし、次の学会で発表された論文では、 ACM Symposium on Theory of Computingにおいて、マサチューセッツ工科大学の研究者2名が、 数学的証明 を提示し、現行の最良のアルゴリズムが「最適」であること、言い換えれば、編集距離をより効率的に計算する方法を見つけることは数学的に不可能であることを示した。 The Boston Globe は、地元の研究者による成果を称え、 見出し を掲げ、「40年にわたり、コンピュータ科学者は存在しない解決策を探し続けていた」と報じた。
しかし、研究者たちはまだ死亡時刻を記録する段階には至っていない。残された重大な抜け道が一つある。この不可能性の結果は、強指数時間仮説（SETH）と呼ばれる、別の有名な未証明の命題も真である場合にのみ成り立つ。計算量理論の研究者の多くはこれが成り立つと想定しており、その中には Piotr Indyk と Artūrs Bačkurs （いずれもMIT所属で、この編集距離の知見を発表した）も含まれる。ただし、SETHの妥当性は依然として未解決の問いである。このため、編集距離に関するこの記事は、マーク・トウェインの死をめぐる伝説的な報道の数学版のようなものであり、大いに誇張されたものに見える。
編集距離をめぐるメディアの混乱は、計算量理論 そのものの深部にある不明瞭さを反映している。数学者やコンピュータ科学者は、何が計算可能で、何が 現実的には計算不可能 なのかを、まるで深海探検家が海溝の底を測量するかのように描き出そうとしている。このアルゴリズムの地形は、実際の海底と同じくらい広大で、十分に理解されていない、と Russell Impagliazzoは語った。彼は計算量理論の研究者であり、最初に指数時間仮説を Ramamohan Paturiと共に1999年に定式化した人物である。「この比喩は適切だ」と彼は述べた。「海洋こそ計算困難性が存在する場所だ。私たちがしようとしているのは、より精密な道具を使い、さまざまな場所で海の深さを測ることである。」
続きを読むには、 Quanta Magazineにアクセスしてください。掲載は世界経済フォーラムの見解への支持を意味するものではありません。
アジェンダの最新情報を入手するには、 週刊ニュースレターに登録してください。
著者：John Pavlusは、作家・映画制作者であり、その作品は Scientific American、Bloomberg Businessweek、そして The Best American Science and Nature Writing シリーズなどに掲載されている。
画像：ワルシャワのオフィスで、ノートパソコンを持つ男性にバイナリコードが投影された図解画像。REUTERS/Kacper Pempel
