山下（Seamless）
2014年から幅広い分野の研究論文をピックアップして解説しているメディア「Seamless」を個人運営。 X（@shiropen2）でも更新情報を発信中。
京都大学数理解析研究所の河村彰星准教授がPNASで発表した論文「Proof of the Density Threshold Conjecture for Pinwheel Scheduling」は、複数のタスクを期限通りにこなすための基礎となる「輪番割当」に関する30年来の数学の難問を証明した研究報告だ。
さらに関連する成果として、同研究所の小林佑輔准教授との共著論文が、2026年8月31日から9月4日(現地時間)にイタリアで開かれる欧州算法シンポジウム（ESA 2026）で発表される。
どんな仕事の組み合わせでもスケジュールが成立する「6分の5予想」
輪番割当とは、例えば「仕事Aは3日以内に1回」「仕事Bは4日以内に1回」「仕事Cは5日以内に1回」「仕事Dは8日以内に1回」といった複数の定期的なタスクを、毎日どれか1つだけ実行してコンピューター1台や作業員1人だけなどで、期限遅れにならずに永遠に回し続けられるかを問う問題である。
当然ながら、仕事の総量が多すぎると処理が追いつかずにパンクしてしまう。しかし1993年に、全体の仕事量（密度）が処理能力の6分の5、つまり約83.3%以下に収まっていれば、どんな仕事の組み合わせであっても絶対にスケジュールが組めるという「6分の5予想」が提唱された。
これはシステム設計において実用的な目安だが、いかなる場合でも絶対に破綻しないことを数学的に証明するのは難しく、30年以上の未解決問題となっていた。
全体の仕事量が約83.3%以下ならシステムはパンクしない
今回、数学的な理論とコンピューターによる膨⼤な探索を組み合わせるアプローチでこの予想を証明した。
まず、問題がもつ連続的な数理構造（許容周期を整数から実数へ拡張するなど）を利用し、検証すべきパターンを、比較的少数の仕事からなる有限個のケースへと理論的に絞り込む。そのうえで、検証プログラムにより計算機上で莫大な場合分け探索を実行し、6分の5予想が正しく成り立つことを証明した。
また、この手法を応用して、逆向きのルールを課した被覆型の輪番割当も解決した。こちらは毎日発生する1つの業務を複数の担当者で分担する設定で、例えば担当者ごとに3日に1回以下しか実行できないといった間隔の下限が課される。研究では、スケジュールが成立する限界の数値（密度が1.264…以上であればスケジュール可能）を割り出すことに成功している。
今回の証明により、全体の仕事量が約83.3%以下ならシステムはパンクしないという数学的なお墨付きが得られたことになる。この成果は、組込み機器の制御や通信のデータ処理、ドローン・ロボットの周回運⽤計画など、時間制約のある資源配分をより安全かつ無駄なく設計するための基礎的な指針となることが期待される。
Source: A. Kawamura, Proof of the density threshold conjecture for pinwheel scheduling, Proc. Natl. Acad. Sci. U.S.A. 123 (32) e2530214123, https://doi.org/10.1073/pnas.2530214123 (2026). Kawamura, A., & Kobayashi, Y. (2026). A computer-assisted proof of the optimal density bound for pinwheel covering. In 34th Annual European Symposium on Algorithms (ESA 2026)
