[Top page] [日刊 研究最前線 知尋] [Discovery Saga総合案内] [大学別アーカイブス] [Discovery Saga会員のご案内] [産学連携のご案内] [会社概要] [お問い合わせ]

京都大学 研究Discovery Saga
記事検索
2026年8月18日

30年来の未解決問題「輪番割当の6分の5予想」を数学と計算機で証明

―周期タスクの詰込・被覆問題で限界値を決定―

【注目の成果：共同研究・産学連携のためのチェックポイント】
コンピュータの高度な探索・検証能力の活用は、今後も従来の枠組みを超えて我々の数学的理解を大きく進展させるものと期待
【産学連携対象 全学共通分野 Discovery Saga】
情報学工学
【Sagaキーワード】
スケジューリング/タスク/実時間システム/人工知能（AI）/数学モデル/ロボット/大規模計算
この研究の主な対象者
企業・研究者の方
公開日

研究者情報

研究者名
河村 彰星

京都大学 教育研究活動データベース 
研究者名
小林 佑輔

京都大学 教育研究活動データベース 

概要

京都大学数理解析研究所の河村彰星准教授、小林佑輔准教授の研究グループは、実時間システムや定期業務の基礎となる数学モデル「輪番割当問題」において、30年以上にわたり未解決であった「密度6分の5予想」および関連する定理群を証明しました。
　輪番割当は、複数の定期的な仕事を「最長で○○日（あるいは○○ミリ秒）に1度以上は実行する」という条件のもと、一つの資源で順次実行できるかを問う問題です。仕事の総量（密度）が5/6（約83.3%）以下ならば必ずスケジュール可能とする「6分の5予想」は、1993年の提唱以来、実時間スケジューリングにおける理論的難問の一つでした。本研究では、数理解析と計算機支援による厳密な全探索を融合させ、予想の正しさを証明しました。またこの手法を拡張し、頻度に下限ではなく上限を設ける双対な問題設定（被覆型）においても、最良の密度限界（約1.264）を特定・証明しました。
　本成果は、組込み制御や通信処理、ロボットの周回運用計画など、時間制約のある仕事・資源の配分に明確な理論的保証を与えるものです。成果の一部は2026年8月7日に米国科学アカデミー紀要（PNAS）にオンライン掲載され、一部は同年8～9月に欧州算法シンポジウム（ESA）にて発表されます。
画像


研究者のコメント
「輪番割当は素朴な設定でありながら解析の難しい問題でしたが、大規模計算の手法がうまく効いて予想の解決に至ったのは幸運でした。人間が読める『きれいな』証明が今後得られる望みも捨ててはいませんが、ともあれ近年のAIをはじめとする計算機技術の著しい進歩は、数学研究に新たな可能性と展開をもたらしつつあります。コンピュータの高度な探索・検証能力の活用は、今後も従来の枠組みを超えて我々の数学的理解を大きく進展させるものと期待しています。」（河村彰星）

詳しい研究内容について

30年来の未解決問題「輪番割当の6分の5予想」を数学と計算機で証明―周期タスクの詰込・被覆問題で限界値を決定―

書誌情報

論文1
【DOI】
https://doi.org/10.1073/pnas.2530214123
【書誌情報】
Akitoshi Kawamura (2026). Proof of the density threshold conjecture for pinwheel scheduling.Proceedings of the National Academy of Sciences (PNAS), 123, 32, e2530214123.
論文2
【DOI】
https://doi.org/10.48550/arXiv.2510.06533
【書誌情報】
Akitoshi Kawamura, Yusuke Kobayashi (2026). A Computer-Assisted Proof of the Optimal Density Bound for Pinwheel Covering.

関連部局

数理解析研究所
出典：京都大学
（URL::https://www.kyoto-u.ac.jp/ja/research-news/2026-08-17　発表日：2026/08/17　記事名：30年来の未解決問題「輪番割当の6分の5予想」を数学と計算機で証明）
の最新研究情報をもとに株式会社アーキテクトが編集・作成したものです。　　Poewrd byARchiTect inc.