2026-08-10 · paper-digest
Han et al.: Sorting Out When Learning Order Matters, by Computational Complexity — Fukai Reads
A paper by Han and four colleagues at UC Davis and partner institutions on the computational complexity of instructional sequencing. They formalise the ordering of prerequisite-linked concepts as a stochastic shortest-path problem, prove that the stochasticity of retry-after-failure collapses exactly by dividing cost by success probability, show that optimal ordering nonetheless remains NP-hard, and give a cheap diagnostic that upper-bounds the value of sequencing before any optimisation. On 70,893 real interactions from an introductory CS course that headroom was under 0.2%, while on a constructed trap greedy sequencing lost 28.3-45.1%. arXiv preprint, submitted 5 August 2026, not peer reviewed.
