Research Summary: The Plan Language of a Curriculum: A Formal Model and the Complexity of Degree Planning

This research introduces a formal model for academic curricula, viewing them as generators of feasible study plans. It establishes the computational complexity of key degree planning objectives, specifically the number of terms to degree and total credit load, within this defined model. A significant finding is that while disjunctive prerequisites do not complicate 'time to degree' when per-term credit capacity is unlimited, this objective becomes strongly NP-hard under constrained per-term capacity.

Why it matters

This research provides a formal understanding of the computational challenges inherent in academic degree planning, highlighting specific structural elements that contribute to complexity. Understanding these complexities is crucial for designing efficient academic systems and student advisement tools, impacting institutional resource allocation and student success.

Key insights

• An academic curriculum is modeled as a generator of a language of feasible study plans.
• Prerequisites are represented as monotone Boolean formulas in conjunctive normal form.
• Degree requirements are modeled as credit-threshold covering constraints.
• A study plan is defined as a sequence of terms bounded by a per-term credit capacity.
• The complexity of two planning objectives—time to degree and total credit load—has been settled.
• Time to degree is polynomial with arbitrary disjunctive prerequisites and electives when per-term capacity is unbounded.
• Time to degree becomes strongly NP-hard when per-term credit capacity is bounded.

Source

arXiv — Computers and Society — https://arxiv.org/abs/2610.03392