連日の猛暑。もはや「危険な暑さ」が当たり前になり、外出そのものが健康リスクになる日も増えている。
そんなとき、屋内でできて、知的好奇心を満たしてくれるものといえば……アルゴリズムの世界だ。
特に、未解決のアルゴリズム問題に目を向けると、数学や計算機科学の深淵が垣間見えて面白い。
今回は、有名な3つの未解決問題を取り上げ、その面白さを暑さを忘れるレベルで解説してみたい。
1. P≠NP問題はまだ決着していない
計算機科学最大の謎とも呼ばれる「P≠NP問題」。
2000年にクレイ数学研究所が提示した「ミレニアム懸賞問題」のひとつで、解決すれば100万ドルの賞金が出る。
ざっくり言えば、「答えがすぐに検証できる問題（NP）」は、「すぐに解ける問題（P）」と同じなのか？ という問いだ。
例えばナンプレ（数独）は、完成された解があれば一瞬で正しいかどうか判断できるが、その解を一から見つけるのは大変だ。
ではこの「解くのが大変」が本質的に“非効率”なのか、それともまだ最適な解法が見つかっていないだけなのか。
この問題の難しさは、私たちが日常的に使っている暗号技術やデータ構造、AIの学習戦略にも深く関わっている。
もしP=NPなら、暗号は簡単に破られ、AIは一気に天才化するかもしれない。
2. 3n+1問題はシンプルなのに深い
「任意の自然数nに対して、nが偶数ならn/2、奇数なら3n+1を適用し続けると、最終的に1になる」。
この単純なルールに従う「コラッツ予想」は、未だに正しさが証明されていない。
例えば、n=7から始めると、7→22→11→34→17→…と数は上下しながらも、最終的に1へ到達する。
この現象は数百万の数で確認されており、コンピュータを使った検証でも膨大な範囲で成り立っているが、完全な証明は存在しない。
この問題が注目される理由の一つは、数理的な裏付けが乏しい「直感」に支えられているからだ。
単純だからこそ、美しく、そして手ごわい。まさに“数のカオス”を体現する問題といえる。
3. 最長増加部分列の高速解法は限界か？
「最長増加部分列（Longest Increasing Subsequence, LIS）」は、与えられた配列から、値が単調に増加する最長の部分列を見つける問題。
たとえば [3, 10, 2, 1, 20] なら [3, 10, 20] が該当する。
これはすでに O(n log n) の時間計算量で解けるが、ここで問題になるのは「より複雑な制約付きバージョン」や「LISに関する派生的な構造探索」だ。
たとえば「複数のLISを全列挙する」「2次元や木構造でのLISを求める」となると、途端に既存の手法が使えなくなる。
アルゴリズムの研究では、「知っている問題の先に、未知の地形が広がっている」ことが頻繁にある。LIS問題も、そうした“既知からの飛躍”を誘う代表的な例だ。
まとめ
未解決のアルゴリズム問題は、エアコンの効いた部屋でじっくり考えるには最適なテーマだ。
現時点で人類が解けていない謎に、自分なりの仮説をぶつけてみるのは思考トレーニングとしても有効。
何より、暑さに消耗するより、頭を使って「涼しげな思考」に浸っている方が、精神的にも豊かだ。
この夏は、ぜひ未解決問題という知の迷宮に足を踏み入れてみてはいかがだろうか。
SNOWさんも考えてみた
まず問題の意味を理解するのに時間がかかりますよね、P=NP問題とかChatGPTに聞きまくってようやく「何が問題か」を理解できました。
3n+1問題はシンプルだけど謎ということで、シンプルな問題なら得意なSNOWさんはちょっとテンション上がる系の話なんですが、こういうのほど難しかったりします。
僕も一応、情報工学系の大学院までいったけど、M2のころは授業の内容もほぼ理解できず、試験やレポートもかなり適当だったような気がしています。
なんで卒業（修了）できたのかについては、僕の中でまだ未解決アルゴリズムのままです。
よし、なんかうまいことまとまった感じする。
🎁 Sponsors: Amazon | Prime | Music | Audible | Kindle Unlimited 🎁