【ナゾロジー】大学生が40年間信じられてきたデータサイエンスの定説を覆した [すらいむ★]

大学生が40年間信じられてきたデータサイエンスの定説を覆した

　コンピューターサイエンスの世界には、1985年にアンドリュー・ヤオ（Andrew Yao）氏が残した一つの予想がありました。

　それは「目的のデータを探すとき、その手数には、これ以上減らせない理論的な下限が存在するはずだ」というものでした。

　以後40年にわたり、多くの研究者はこれを長く有力な予想として受け止め、計算機科学の議論に深く影響を与えてきました。

　多くの人が「これは破れないだろう」と考えていたのです。

　しかし、この40年来の予想を真正面から覆す結果が発表されました。

（以下略、続きはソースでご確認ください）

ナゾロジー　2026.04.09 17:00:22
https://nazology.kusuguru.co.jp/archives/193904

オープンに検索することには
グリーディって名前があったんだね

>>1の理論は量子力学にも適応できるのかな？

記事のコメントが辛辣で草

＞大変恐縮ですが、この記事の大半はAIによる翻訳かと思います。
抽象的な例えによってかえって定性的でわかりにくい表現になったり、なんとなくそれっぽいけどよく読んだら何を書いてあるのかわからない、という文章になっているあたり、非常にAI感が強いです。

ソートの性能はNが増えたときにO(logN), O(N^k), O(N!)などの表現で
どう表現されるかで決まるはず

この記事では、決まったN個の箱にn個(n≦N)の要素を入れるようなことをしているように読める
読み間違いかもしれないが