Amazonが1日10億件解く問題 「NP困難だから無理」の落とし穴

3行まとめ

• 「NP困難NP困難効率よく解くアルゴリズムが知られていない問題の分類。難しさは最悪ケースを基準に測ります。だから解けない」は言いすぎだと、ある技術者がブログで論じています。
• 理論が語るのは最悪ケース最悪ケース考えうる入力のうち、一番時間がかかるもの。計算量の議論はここを基準にします。で、実務に出てくる入力では起きないことが多い、という主張です。
• Amazonは1日10億件のSMTSMTSATをさらに難しくした版だと記事は説明しています。問題を解いている、と記事は紹介しています。

何が起きたか

「NP困難だから解けない」という言い回しは実務ではほぼ当てはまらない、という記事が個人ブログに公開されました。日付は2026年8月13日、タイトルは「NP-Overrated」。筆者は大学で「NP困難な問題は理論上は解けるが、実務では絶望的に高くつく」と受け取ったと書いています。

同じ理解をしている人が周囲にもオンラインにも多い、とも書いています。教授は最終講義をこう締めたそうです。少し言い換えている、と筆者は断っています。

おもしろい問題のほとんどは決定不能で、残りのほとんどはNP困難です。計算機科学という営みにとって、これはとどめの一撃です。

この受け取り方が広まりすぎている、というのが筆者の見立てです。「それはNP困難だから無理」で議論が止まる場面を何度も見てきた、と書いています。

なぜ難しい・何がすごいか

理論が言う「難しい」は最悪ケースの話です。あらゆる入力に対して速い、という保証がないだけの主張。手元の入力で遅くなるとは言っていません。

筆者はこう整理します。どんなアルゴリズムを作っても、どこかの入力で計算は爆発する。それでも99.9%の入力では速く解けるかもしれないし、実際に関係のある入力なら全部速いかもしれない。

理論はその可能性を否定していない、というのが筆者の主張です。記事は Benjamin Brewster の言葉として、こう引用しています。

理論上は、理論と実践に違いはない。しかし実践では、違いがある。

たとえ話

地図の最大斜度だけを見て「この山は登れない」と決める人はいません。実際に歩くルートがその崖を通らなければ、数字は関係ないからです。

計算量の最悪ケースも、これに近い位置にあります。実務で投げられる入力が崖を通らないなら、理論上の急斜面は現れません。

用語ミニ辞典

• NP困難: 効率よく解くアルゴリズムが知られていない問題の分類。難しさは最悪ケースを基準に測ります。
• 最悪ケース: 考えうる入力のうち、一番時間がかかるもの。計算量の議論はここを基準にします。
• SAT: 与えられた条件を全部同時に満たす真偽の割り当てがあるかを判定する問題。NP困難の代表例として挙げられています。
• SMT: SATをさらに難しくした版だと記事は説明しています。
• 依存解決: パッケージマネージャが、ライブラリのバージョンの組み合わせを決める処理。

技術者向けの深掘り

筆者はNP困難の例を5つ挙げます。依存解決依存解決パッケージマネージャが、ライブラリのバージョンの組み合わせを決める処理。、型検査（すべての型システムではない）、スケジューリング、巡回セールスマン、SATSAT与えられた条件を全部同時に満たす真偽の割り当てがあるかを判定する問題。NP困難の代表例として挙げられています。です。

依存解決と型検査は、最悪ケースがそもそも起きないと書きます。インストールや型検査が遅くなることはあっても、天文学的な爆発はキャリアの中で見たことがない、と。

スケジューリングと巡回セールスマンは最適化問題です。ヒューリスティクスで殴れるのは知られていますが、最適性を捨てる必要はないと筆者は言います。証明つきの最適解を現実的な時間で出すツールが実際にある、という指摘です。

魔法も量子コンピュータも要りません。ここ数十年、アルゴリズムの高速化はハードウェアの進歩を上回ってきた、と筆者は書きます。根拠として、1991年から2015年で4500億倍の高速化を挙げた論文を引いています。

SATについては、Amazonが1日10億件のSMT問題を解いていると紹介します。SATのアルゴリズムは良くなりすぎて、いまでは簡単なパート扱いだそうです。

これは自分に関係ある？

エンジニアでない読者には、言葉の受け取り方が変わります。「計算量的に不可能」と聞いても、それは最悪ケースの話です。目の前のサービスが動かない理由にはなりません。

エンジニアには、設計判断の材料になります。NP困難を理由に機能を諦める前に、自分たちの入力で本当に爆発するのかを確かめる余地があります。

最悪ケースを引いたときの対処も、筆者は素っ気なく書いています。HTTPリクエストだって返ってこないことがある。タイムアウトを置いてエラーを出せばいい、と。