NPは過大評価されている

NPは過大評価されている 2026年8月13日 大学でNP困難問題について学んだとき、おそらく皆さんの結論はこうだったでしょう。NP困難問題は理論上は解けるが、実際には途方もなくコストがかかる。良いアルゴリズムは存在しないことが基本的に証明されている、と。少なくとも私はそう理解しました。そして、話したほとんどの人々も、そしてオンラインの多くの人々もそうです。「いや、それはできない。NP困難なんだ。ブルブル」といった議論を私は見かけ続けます。この神話は広まっていますが、これらの問題は手に負えないわけではありません。 当時、私の教授は最終講義を劇的な言葉で締めくくりました（少し言い換えています）。そして今、皆さんは、興味深い問題のほとんどすべてが決定不能であり、残りのものの大半がNP困難であることを学びました。コンピュータサイエンスというプロジェクトにとって、それは棺桶に最後の釘を打つようなものです。うーん。皆がそんな悲観的な捉え方をしたかどうかはわかりませんが、それなら説明がつきます。 理論は間違っていませんが、実際にはしばしば無関係です。確かに、どんなアルゴリズムを思いついても、ある入力に対しては破綻します。しかし、入力の99.9%で高速な解を得られるかもしれません。あるいは、関連する入力の100%で。理論はそれを排除しません。 理論上、理論と実践に違いはありません。しかし、実践上はあります。 -- Benjamin Brewster いくつかの著名なNP困難問題: 依存関係解決（パッケージマネージャーにおいて） 型チェック（すべての型システムではない） スケジューリング 巡回セールスマン問題 充足可能性問題（SAT） (1)と(2)については、最悪のケースは発生しません。つまり、パッケージのインストールや型チェックは確かに遅くなる可能性があります。しかし、少なくとも私のキャリアでは、銀河系規模の破綻を見たことはありません。 (3)と(4)は技術的には最適化問題です。これらはヒューリスティックで対処できることは誰もが知っていますが、最適性を犠牲にする必要はありません。私たちは、合理的な時間で証明可能な最適解を見つけることができるツールを間違いなく持っています。魔法はありません。量子コンピュータもありません。ただ、より深く考え、より良いアルゴリズムを思いつくだけです。そして、人々はそうしてきました。実際、アルゴリズムの高速化は、過去数十年間でハードウェアの進歩を上回っています。これらを合わせると、この論文は1991年から2015年の間に4500億倍の高速化を引用しています。 最後になりましたが、最も重要なことではありません。NP困難問題の典型である(5)でさえ、日常的に大規模に解決されています。Amazonは1日に10億ものSMT問題を解決しています。SMTはSATよりもさらに難しいバージョンです。SATアルゴリズムは非常に優れており、今では簡単な部分と見なされています。 しかし、最悪のケースに遭遇したらどうなるでしょうか？宇宙の熱的死まで待つ必要はありません。HTTPリクエストも時々返ってこないことがあります。タイムアウトを追加し、エラーメッセージを表示し…おなじみの手順です。