#complexity

Han et al.: 学ぶ順番が効く場面と効かない場面を、計算量で切り分ける — Fukai が読む

カリフォルニア大学デービス校の Han 氏ら5名による、教育系列化の計算量を扱った論文。前提条件でつながった概念を学ぶ順序の最適化を確率的最短経路問題として定式化し、失敗によるやり直しという確率性はコストを成功確率で割るだけで厳密に消せること、それでも最適順序の決定は NP 困難であること、そして最適化の前に「順番をいじって得られる利得の上限」を安価に計算できることを示した。入門CS科目の70,893件の実データではその余地が0.2%未満だった一方、人工的な罠では貪欲な順序が28.3〜45.1%の損をした。arXiv preprint(2026年8月5日投稿、査読前)。