コンピュータ科学最大の未解決問題——P vs NP
Fireshipが解説するP vs NP：証明自体が数学的に不可能かもしれない、賞金100万ドルの未解決問題。
- Clay Mathematics InstituteはP vs NPの証明（どちらの方向でも）に100万ドルの賞金を懸けている。
- P vs NPはSteven Cookが1971年に正式に定義したが、John Nashは1955年のNSA宛て書簡でP≠NPを示唆していた。
- NP完全問題（SAT、巡回セールスマン問題、タンパク質折り畳み）は相互に帰着可能——どれか一つを多項式時間で解ければ、すべて解ける。
- 15都市の巡回セールスマン問題では経路の候補が約870億通りになる。検証は簡単だが、発見は容易ではない。
- RSA暗号は「二つの素数の積は簡単に計算できるが、逆の素因数分解は難しい」という事実に依拠している——ただし、その困難さはいまだ証明されていない。
- もしP=NPなら、あらゆる暗号（パスワード、暗号資産ウォレット）が即座に破られる。一方でタンパク質折り畳み問題が解けるようになり、がん治療に革命が起きる可能性もある。
- 50年以上、数千本の論文を経ても、どちらの方向にも証明はゼロ——あらゆる証明の試みは構造的な壁に突き当たっている。
2026-03-09 · YouTubeで見る
英語版: The greatest unsolved problem in computer science… · Watch on YouTube
