P vs NP 問題

🧩 ホモ・サピエンス最後の難問

P vs NP問題は21世紀の数学の7大難問（ミレニアム懸賞問題）の一つで、賞金はなんと100万ドルです。簡単に言えば「検算が簡単な問題は、解くのも簡単か？」という問いです。掛け算は計算も検算も簡単ですが（P問題）、巨大な数の素因数分解は答えがわかっていれば検算は簡単ですが、その答えを見つけ出すのは非常に困難です（NP問題）。

🔐 暗号の安全装置

私たちが使うインターネットバンキングや仮想通貨のセキュリティは、P≠NPという仮定の上に成り立っています。もし誰かがP=NPであることを証明すれば（つまり、難しい問題も簡単に解くアルゴリズムを発見すれば）、世界中のすべての暗号システムは瞬く間に崩壊するでしょう。

💻 コンピューターの限界

この問題はコンピューターができることの限界を問うものでもあります。巡回セールスマン問題 (TSP) のように都市が増えるほど計算量が指数関数的に爆発するNP問題に、実は効率的な近道（P問題）が存在するのでしょうか？多くの学者は「そうではない (P≠NP)」と信じていますが、まだ証明されていません。