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/
33年未解決の「6分の5予想」を京都大学が証明、周期タスク設計に理論的上限 [すらいむ★]
1すらいむ ★
2026/08/21(金) 23:51:32.32ID:/1KLJ6GA2名無しのひみつ
2026/08/22(土) 00:04:42.20ID:Q6aco8Oo 東大って役立たずだよね
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番目の仕事を割り込む隙間が永遠に残らない。
問題の構造は単純だ。$k$個の仕事があり、仕事$i$は日ごとに必ず1回実行しなければならない。1日に実行できる仕事はちょうど1つ。スケジュールが存在するか否かを判定したい。
密度という量がこの問題の核心を握る。各仕事の「1日あたりの実行頻度」の合計であり、これが1を超えれば物理的にスケジュール不可能である。1日に1つしか仕事をこなせないのに、要求される総仕事量が1日あたり1を超えるのだから当然だ。
ところが密度1以下という条件は、スケジュール可能性を保証しない。最も有名な反例は$(2, 3, m)$()である。密度はであり、$m$を大きくすれば1にいくらでも近づけられるが、この組はどんな$m$を選んでもスケジュール不可能だ。2日周期の仕事と3日周期の仕事が互いに干渉し、3番目の仕事を割り込む隙間が永遠に残らない。
6名無しのひみつ
2026/08/22(土) 06:50:09.13ID:0d7J2bIj7名無しのひみつ
2026/08/22(土) 06:52:10.03ID:0d7J2bIj2026/08/22(土) 07:01:28.88ID:UIF1uL2n
どっちにしろ光の速度は超えられない
それを超えたいなら量子テレポーテーション原理とか使った配線方法や回路素子を考えないと
それを超えたいなら量子テレポーテーション原理とか使った配線方法や回路素子を考えないと
9名無しのひみつ
2026/08/22(土) 09:37:44.60ID:2X6uXqdm10名無しのひみつ
2026/08/22(土) 14:46:08.05ID:0d7J2bIjレスを投稿する
ニュース
- 【速報】元ジャンポケ斉藤慎二被告に懲役4年の実刑判決 ★6 [Anonymous★]
- GDP速報値は年率0.1%マイナス 4期ぶりのマイナス成長 個人消費は低調 ★2 [首都圏の虎★]
- 東京が「世界で最も魅力的な都市」1位に! 日本は国別で世界2位 北海道は「魅力的な地域」10位に [首都圏の虎★]
- 【後だしジャンケン】インド高速鉄道は「日本の新幹線」を選んだはずが…「車両はインド製、信号はドイツ製」のワケ [煮卵★]
- 【テレビ】 ブラジル撃破 サッカー日本代表戦は高視聴率 18・0%! 瞬間最高23・6% 久保建英が結婚公表後初ゴール ★2 [阿弥陀ヶ峰★]
- 【訃報】女優・中田乃愛さん急逝 23歳 「ウルトラマンテオ」出演中 東宝シンデレラ出身 ★2 [Ailuropoda melanoleuca★]
- 【実況】博衣こよりのえちえちこより実は◯◯◯🧪
- 🤥ア...ア...
👕
👖
💩ポロッ
🏡
- 【悲報】日本の消費「コロナ前」を下回る [256556981]
- 【悲報】松崎しげる、海外で大炎上wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww [841411289]
- 【悲報】米中露「我々はファシズムジャップを倒すため共に戦った!」 [431136663]
- 元アリスソフト開発者による新作ゲームキタ━━━━━━(゚∀゚)━━━━━━!!!!! [303493227]