計算機科学最大の未解決問題：P vs NP

FireshipがP vs NPを解説：Clay Mathematics Instituteが懸ける賞金100万ドルの未解決問題。P≠NPの証明は数学的に不可能かもしれない。

• Clay Mathematics Instituteは、P vs NPの証明（どちらの方向でも）に100万ドルの懸賞金を設けている。
• P vs NPは1971年にSteven Cookが正式に定義した。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