Complexity of academic degree planning depends on credit capacity and course rules
The Plan Language of a Curriculum: A Formal Model and the Complexity of Degree Planning
Data Structures and AlgorithmsComputational ComplexityComputers and Society
Summary
Planning out the courses needed to finish a college degree can be complicated because of prerequisites and credit limits each term. The authors created a formal model that views an academic curriculum as a way to generate possible study plans. They found that when there's no limit on credits per term, figuring out the shortest time to graduate is easier, but adding credit limits makes it much harder. On the other hand, deciding the total course load is mostly hard because of how course requirements combine. They tested their model on data from many universities to understand these complexity sources better.
What this means in practice
- •For university academic planners: Identify which constraints most affect students’ time to degree and optimize course offerings accordingly.
- •For education software developers: Design degree planning tools that recognize cases when scheduling is computationally hard and adapt strategies accordingly.
Tested on one dataset.
Authors
Sherzod Turaev, Mary John, Mamoun Awad
Abstract
We model an academic curriculum as a generator of a language of feasible study plans: prerequisites are monotone Boolean formulas in conjunctive normal form, degree requirements are credit-threshold covering constraints, and a study plan is a sequence of terms bounded by a per-term credit capacity. Within this model, we settle the complexity of the two natural planning objectives, the number of terms to a degree and the total credit load, and we isolate the structural commitment responsible for each source of hardness. Time to degree is polynomial whenever the per-term capacity is unbounded, for arbitrary disjunctive prerequisites and arbitrary electives, so disjunction never contributes to its hardness, yet it becomes strongly NP-hard as soon as capacity binds, even without any prerequisite. Load is complementary: disjunction and overlapping electives are each strongly NP-hard in isolation and their complexity does not depend on capacity, while load is polynomial on the conjunctive, mandatory fragment. The two objectives therefore have disjoint sources of hardness. We show that the delay-factor component of the standard curricular-complexity metric is a polynomially computable upper bound on time to degree, exact on the conjunctive fragment and loose elsewhere by a quantity we name the disjunctive slack, and we prove that program subsumption is coNP-complete and consensus prerequisite recovery is NP-complete. Instantiating the model on a corpus of twenty-two universities, we find that 88 percent of prerequisite-bearing courses are purely conjunctive and that capacity, not prerequisite logic, is the operative constraint on time to degree. The curriculum corpus is openly available (https://doi.org/10.5281/zenodo.22334674), and the analysis and figure-generation code accompany the paper.