探検


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

1すらいむ ★
垢版 |
2026/08/21(金) 23:51:32.32ID:/1KLJ6GA
33年未解決の「6分の5予想」を京都大学が証明、周期タスク設計に理論的上限

この記事のポイント

何が起きた: 京都大学数理解析研究所の河村彰星准教授が、輪番割当問題の「密度6分の5予想」(1993年提唱)を証明し、2026年8月7日にPNASへ掲載された。小林佑輔准教授との共著では被覆型の最適限界α* = 1.264...も確定した。
なぜ重要か: 実時間スケジューリング理論の30年来の未解決問題が解決し、組込み制御や通信処理など周期タスクの設計に理論的上限が与えられた。計算機支援証明の有効性も示した。
次に見るべき点: 人間が読める「きれいな」証明が存在するかは未解決。密度閾値が最小周期に依存するという新予想(Conjecture 8)の検証も残る。

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

xenospectrum 2026年8月21日
https://xenospectrum.com/pinwheel-scheduling-five-sixths-conjecture-proof/
2名無しのひみつ
垢版 |
2026/08/22(土) 00:04:42.20ID:Q6aco8Oo
東大って役立たずだよね
2026/08/22(土) 05:53:03.78ID:wGYICoJS
>>2
この理論を使って、機械の制御ばかりでなく、人間の制御をすることを推進するのが役目だから
2026/08/22(土) 05:55:19.54ID:tbi6cYRN
それは理解出来てない痴呆の妄想
5名無しのひみつ
垢版 |
2026/08/22(土) 06:47:40.49ID:0d7J2bIj
1989年、テキサス大学オースティン校のRobert Holte氏たちは、ある実務上の困りごとを数学の問題として定式化した。複数の人工衛星がそれぞれ決まった間隔でデータを送信してくる。地上局のアンテナは一度に一つの衛星しか受信できない。各衛星について「連続する日間に必ず1回は受信する」という条件を満たしつつ、無限に続く受信スケジュールを組めるか。この問いが輪番割当問題(pinwheel scheduling problem)の始まりだった。
問題の構造は単純だ。$k$個の仕事があり、仕事$i$は日ごとに必ず1回実行しなければならない。1日に実行できる仕事はちょうど1つ。スケジュールが存在するか否かを判定したい。
密度という量がこの問題の核心を握る。各仕事の「1日あたりの実行頻度」の合計であり、これが1を超えれば物理的にスケジュール不可能である。1日に1つしか仕事をこなせないのに、要求される総仕事量が1日あたり1を超えるのだから当然だ。
ところが密度1以下という条件は、スケジュール可能性を保証しない。最も有名な反例は$(2, 3, m)$()である。密度はであり、$m$を大きくすれば1にいくらでも近づけられるが、この組はどんな$m$を選んでもスケジュール不可能だ。2日周期の仕事と3日周期の仕事が互いに干渉し、3番目の仕事を割り込む隙間が永遠に残らない。
レスを投稿する


ニューススポーツなんでも実況