확률성은 어려운 부분이 아니다: 선행 지식 의존성 그래프(Prerequisite DAG)에서의 교육 순서 결정 및 복잡성 연구

Stochasticity Is Not the Hard Part: Reduction and Complexity in Instructional Sequencing over Prerequisite DAGs

학생이 선행 관계에 의해 연결된 개념을 학습해야 할 때, 교육 순서가 언제 중요한 의미를 가지며, 최적의 순서를 찾는 데 얼마나 많은 비용이 들까요? 본 연구에서는 교육 순서 결정을 확률적 최단 경로 문제로 정의하고, 각 개념 학습 시도가 상태에 따라 다른 성공 확률을 가지며, 실패할 경우 학생의 상태는 변하지 않는다고 가정합니다. 먼저, 이 확률성을 완전히 제거할 수 있음을 증명하며, 문제가 선행 관계 이상(order ideal) 격자 상에서의 결정적 최단 경로 문제로 축소됨을 보입니다. 이때 최적 값과 행동은 유지됩니다. 이러한 축소를 통해 확률적 복잡성은 사라지지만 조합적 복잡성은 여전히 존재합니다. 즉, 최적 순서 결정을 위한 문제는 선행 관계가 없는 경우에도, 단위 비용, 균일한 양수 전이(transfer), 그리고 성공 확률이 최소 1/2인 경우에도 NP-hard 문제를 유지합니다. 이러한 어려움은 모든 경우에 적용되는 것은 아닙니다. 선호하는 전이 관계가 선행 지식과 함께 순환 그래프를 형성하지 않으면, 남은 연관 그래프의 임의의 위상 정렬(topological order)이 최적의 해가 됩니다. 또한, 고정된 선행 관계의 너비는 다항 시간 내에 정확한 동적 프로그래밍을 가능하게 합니다. 계산 가능한 진단 지표인 'mΔ'는 최적화 전에 순서 결정의 가치를 제한합니다. 실제 초급 컴퓨터 과학 강의에서 70,893건의 상호작용 데이터를 분석한 결과, 이 진단 지표는 매우 쉬운 경우를 나타냅니다. 즉, 최적화할 가치가 거의 없고 탐색해야 할 공간도 작습니다. 반면, 의도적으로 설계된 전이 관계에서는 어려운 경우가 발생하며, 이때 단기적인 순서 결정 방식은 큰 후회를 초래하지만, 일관성 있는 휴리스틱을 사용하는 A* 알고리즘은 해당 문제 유형에 대해 선형적으로만 상태를 확장합니다.

When a student must learn concepts connected by prerequisite dependencies, when does the order of instruction matter, and what does it cost to find the best one? We study instructional sequencing as a stochastic shortest-path problem in which attempting a concept succeeds with a state-dependent probability and failure leaves the learner state unchanged. We first prove that this stochasticity can be eliminated exactly: the problem collapses to a deterministic shortest-path problem on the lattice of prerequisite order ideals, preserving optimal values and actions. The collapse removes stochastic complexity but not combinatorial complexity: optimal sequencing remains NP-hard -- via reduction from feedback arc set in tournaments -- even with no prerequisite edges, unit costs, uniform binary nonnegative transfer, and success probabilities at least $1/2$. Hardness is not uniform: when realizable transfer preferences remain jointly acyclic with the prerequisites, any topological order of the residual joint graph is optimal, and fixed prerequisite width yields polynomial-time exact dynamic programming. A computable diagnostic, $mΔ$, bounds the value of sequencing before optimization. On 70,893 interactions from an introductory CS course, the diagnostic certifies a doubly easy regime -- little value to optimize and little space to search -- while constructed transfer instances realize the challenging regime, where myopic sequencing suffers large regret yet exact A* with a consistent heuristic expands only linearly many states on that family.