33年未解決の「6分の5予想」を京都大学が証明、周期タスク設計に理論的上限

33年未解決の「6分の5予想」を京都大学が証明、周期タスク設計に理論的上限

この記事のポイント

何が起きた: 京都大学数理解析研究所の河村彰星准教授が、輪番割当問題の「密度6分の5予想」（1993年提唱）を証明し、2026年8月7日にPNASへ掲載された。小林佑輔准教授との共著では被覆型の最適限界α* = 1.264...も確定した。

なぜ重要か: 実時間スケジューリング理論の30年来の未解決問題が解決し、組込み制御や通信処理など周期タスクの設計に理論的上限が与えられた。計算機支援証明の有効性も示した。

次に見るべき点: 人間が読める「きれいな」証明が存在するかは未解決。密度閾値が最小周期に依存するという新予想（Conjecture 8）の検証も残る。