PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Sherzod Turaev, Mary John, Mamoun Awad

arXiv:2610.03392v1cs.DScs.CCcs.CY

TL;DR

Curricular complexity metrics abstract away features that catalogs specify, and the complexity of planning under those features has not been fully classified. This paper formalizes feasible study plans and analyzes time to degree, load, and curriculum comparison. Its results separate the sources of hardness and place capacity, rather than prerequisite logic, at the center of time-to-degree constraints in the studied curricula.

  • Problem

    Existing curricular metrics simplify catalog structure, and no account had formalized the language of feasible study plans or classified its planning questions and real-curriculum boundaries.

    Source: §1 · p. 2

  • Method

    The paper models curricula as generators of feasible-plan languages and analyzes recognition, time to degree, load, and comparison problems under prerequisite, requirement, and capacity constraints.

    Source: §1 · p. 2, §12 · p. 16

  • Results

    Across twenty-two universities, nearly nine in ten courses are purely conjunctive, curriculum-level disjunctive slack is zero, and capacity—not prerequisite logic—governs timely completion.

    Source: §10.3 · p. 13, §12 · p. 17

  • Takeaways & Limitations

    The results distinguish capacity as the hardness source for time to degree from disjunction or elective overlap as sources for load.

    Source: §12 · pp. 16–17

    For prerequisite-free, single-group load, elective choice yields only weak NP-hardness and admits a pseudo-polynomial subset-sum algorithm.

    Source: §8 · p. 9

Abstract

from arXiv · show

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.

1 Introduction

The paper replaces a prerequisite-graph view of curricula with a formal language of feasible study plans, then identifies which catalog features make planning hard. Its central distinction is that capacity governs time to degree, while prerequisite disjunction and elective overlap govern load.

1 Introduction

  • The graph abstraction omits catalog features: alternative prerequisite clauses, credit-threshold elective requirements, and term-by-term credit capacity.A plan is a sequence of terms, not simply a topological ordering of the prerequisite graph.Source: §1 · p. 2
  • The paper models a curriculum as a generator of the language of feasible study plans and attributes planning difficulty to its Boolean prerequisites, covering requirements, and term capacity.Plan recognition is linear, and on the conjunctive fragment the shortest plan is the longest prerequisite chain, computable in linear time.Source: §1 · p. 2
  • Time to degree is polynomial with unbounded capacity, even for arbitrary disjunctive prerequisites and electives, but strongly NP-hard when capacity binds, even without prerequisites.Disjunction does not contribute to the hardness of this objective.Source: §1 · p. 2
  • Load is polynomial on the conjunctive, mandatory fragment but strongly NP-hard from either disjunction or overlapping electives, independently of capacity.The two objectives therefore have disjoint sources of hardness.Source: §1 · p. 2
  • The delay-factor component of curricular complexity is a polynomially computable upper bound on time to degree, exact for conjunctive curricula and otherwise loose by the disjunctive slack.This formalizes a correction reported in the companion study.Source: §1 · p. 2
  • The paper proves program subsumption coNP-complete and consensus prerequisite recovery NP-complete, then locates real curricula on the tractable side of every boundary except capacity.The empirical corpus covers twenty-two universities.Source: §1 · p. 2

2 Related work

The paper connects curricular complexity to work on graph metrics, optimization, scheduling, knowledge spaces, and predictive analytics. It supplies a complexity-theoretic account of what those approaches leave unclassified.

Curricular analytics and complexity metrics

  • Curricular-complexity scores are functions of prerequisite graphs under an all-conjunctive reading, omitting disjunction, credit-threshold electives, and term capacity.The present work does not propose a new score; it formalizes what the delay-factor component measures and when it overstates time to degree.Source: §2 · p. 3

Degree-plan optimization

  • KnowPlan searches for personalized degree pathways, whereas this work classifies planning-question complexity and identifies capacity as the source of time-to-degree intractability.The complexity characterization is complementary and logically prior to an optimizer's work.Source: §2 · p. 3

Scheduling under precedence

  • Precedence-constrained scheduling supplies the source of capacity hardness, while the paper finds prerequisite AND/OR structure alone tractable for time to degree.Elective covering enters only the load objective.Source: §2 · p. 3

Knowledge spaces

  • Knowledge-space theory formalizes prerequisite states but focuses on assessment items, not credit-bearing courses scheduled into capacity-bounded terms.The plan language extends that picture to scheduling and degree requirements.Source: §2 · p. 3

Prediction from curriculum structure

  • Predictive curriculum models use prerequisite-network features empirically, while this work characterizes their computational meaning and supplies time, load, and disjunctive slack as quantities for such models.Source: §2 · p. 3

3 Preliminaries: notation and notions

The preliminaries establish notation and standard results used to formalize curricula and prove their complexity. They cover monotone Boolean formulas, directed acyclic graphs, complexity classes, and reference problems.

3.1 Sets, weights, and monotone Boolean formulas

  • The section fixes set, weight, and Boolean-formula notation and records clause-wise satisfaction and monotonicity of formula satisfaction.A monotone formula uses conjunction and disjunction without negation; a CNF clause is a disjunction of variables.Source: §3 · p. 3, §3.1 · p. 4

3.2 Digraphs, orders, and longest paths

  • For a DAG, a topological order and the longest-path length ending at every vertex are computable in O(|V| + |E|) time by one dynamic-programming pass.A digraph has a topological order exactly when it is acyclic.Source: §3.2 · p. 4

3.3 Computational complexity

  • The preliminaries define polynomial-time many-one reductions and the standard P, NP, coNP, NP-hard, NP-complete, and strong NP-hardness notions used in the proofs.Strong NP-hardness rules out a pseudo-polynomial algorithm unless P = NP.Source: §3.3 · p. 4

3.4 Reference problems

  • The reference problems include BIN PACKING, SET COVER, and precedence-constrained scheduling, with stated hardness results and scheduling boundaries.BIN PACKING is strongly NP-hard, SET COVER is NP-hard, and the scheduling problem is NP-hard when the number of machines is part of the input.Source: §3.4 · p. 4
  • For unit jobs under partial-order precedence, makespan minimization is NP-hard when the machine count is input, while deciding whether makespan is at most three is NP-complete.For two machines the problem is polynomial; the complexity for each fixed m ≥3 remains open.Source: §3.4 · pp. 4–5

4 The model

The model represents courses, prerequisite formulas, credit-threshold requirement groups, and a per-term capacity, then defines feasible plans and the time and load objectives. Its scope excludes several catalog constraints, with tractability claims tied to the stated model.

4 The model

  • A curriculum assigns positive credit weights and monotone CNF prerequisite formulas to courses, includes requirement groups with credit thresholds, and requires an acyclic support digraph.The model identifies Boolean prerequisite form, covering requirements, and per-term capacity as its structural commitments.Source: §4 · p. 5
  • A study plan is a sequence of pairwise-disjoint course sets; the language contains plans that are both feasible and complete for the curriculum.The model treats mandatory courses and free electives as extremes of a requirement group.Source: §4 · p. 5
  • Time to degree minimizes the number of terms, while load minimizes the total credits taken; the model also distinguishes conjunctive, mandatory, and free-capacity fragments.Plans need at most n nonempty terms, so the plan language is finite.Source: §4 · p. 5
  • The model omits term-offering patterns, same-term corequisite constraints, grade conditions, and additional credit floors or ceilings; tractability results would need re-examination if offering or same-term constraints were added.The passage states that the hardness results persist under the listed monotone additions.Source: §4 · pp. 5–6

5 Recognition is easy

Plan recognition is linear-time, so the theory’s complexity lies in optimization rather than checking a proposed plan. Both objective decision versions are in NP because a plan is a polynomial-size certificate that can be verified in polynomial time.

5 Recognition is easy

  • A proposed plan can be checked in linear time by testing term capacities, prerequisite satisfaction, and degree completeness.The verifier processes terms in order and checks each course, clause, and group membership a constant number of times.Source: §5 · p. 6
  • Recognition checks each course, clause, and group membership only a constant number of times.Source: §5 · p. 6
  • Both planning objectives’ decision versions lie in NP because an optimal plan is a polynomial-size certificate verified by the recognition procedure.Source: §5 · p. 6

6 Time to degree without a capacity bound

With free per-term capacity, time to degree is polynomial-time computable, even with arbitrary disjunctive prerequisites and credit-threshold requirements. The results give increasingly general characterizations, from longest prerequisite chains to a threshold test over courses’ levels.

6.1 The conjunctive, mandatory base case

  • For conjunctive mandatory curricula, the minimum number of terms is the longest prerequisite-chain length in the closure of the target courses.The value and an optimal plan are computable in O(n + |E|) time.Source: §6.1 · p. 6

6.2 Disjunction does not raise the cost of time

  • For mandatory targets with arbitrary prerequisites, time to degree equals the maximum AND/OR level among target courses and is computable in polynomial time.The level choice selects a lowest-level witness in each prerequisite clause; disjunctive width does not affect tractability.Source: §6.2 · pp. 6–7

6.3 Electives do not raise the cost of time

  • For arbitrary prerequisites and requirement groups, time to degree is polynomial-time computable by testing candidate level thresholds against each group’s credit quota.The course levels are computed once, and at most n distinct thresholds need testing.Source: §6.3 · p. 7

7 Time to degree with a capacity bound

A binding per-term capacity makes time-to-degree strongly NP-hard, even when all prerequisites are empty. The paper notes that this general hardness result does not settle complexity for the smaller credits and fixed capacities of realistic catalogs.

7 Time to degree with a capacity bound

  • TIME-TO-DEGREE is strongly NP-hard with conjunctive mandatory courses, even when every prerequisite is empty.Source: §7 · p. 8
  • The reduction maps item weights to course credits, making plans of at most B terms equivalent to packing items into B capacity-limited bins.Source: §7 · p. 8
  • The hardness result uses unbounded credit weights; with small credits and fixed capacity, the exact complexity for realistic parameter ranges remains open.For unit-credit courses with precedence constraints, the fixed-machine scheduling complexity is open for each fixed c ≥3.Source: §7 · p. 8

8 Load, and the duality of hardness

Load and time to degree have disjoint sources of hardness: capacity governs time to degree, while disjunction and overlapping electives govern load. Load is easy on the conjunctive, mandatory fragment, but each of those two commitments can make it strongly NP-hard.

8 Load, and the duality of hardness

  • For conjunctive, mandatory curricula with sufficient capacity, load equals the total weight of the prerequisite closure of the target courses.The closure and its weight are computable in O(n + |E|).Source: §8 · p. 8
  • Disjunction makes load strongly NP-hard even with mandatory requirements, free capacity, and disjunctive width two.The reduction uses polynomially bounded weights.Source: §8 · pp. 8–9
  • Electives alone make load NP-hard with one requirement group, but this restricted case admits a pseudo-polynomial subset-sum algorithm.The cited reduction establishes weak rather than strong NP-hardness.Source: §8 · p. 9
  • Overlapping requirement groups make load strongly NP-hard with unit credits, conjunctive prerequisites, no prerequisites, and free capacity.The construction encodes SET COVER: a complete plan selects courses covering every element.Source: §8 · p. 9
  • Time-to-degree hardness comes only from bounded capacity, whereas load hardness comes from disjunction or overlapping electives and does not depend on capacity.Load is polynomial on the conjunctive, mandatory fragment.Source: §8 · p. 9

9 The connection to the curricular-complexity metric

The paper relates the curricular-complexity metric’s delay-factor component to time to degree by evaluating a curriculum’s conjunctive collapse. The resulting upper bound is exact for conjunctive curricula and otherwise differs by the disjunctive slack.

9 The connection to the curricular-complexity metric

  • The conjunctive collapse replaces each prerequisite alternative with a required prerequisite while leaving the curriculum’s other data unchanged.The metric is defined under this all-conjunctive reading.Source: §9 · p. 10
  • The delay-factor component is a polynomially computable upper bound on time to degree, exact for conjunctive curricula.For mandatory, free-capacity curricula, the collapse’s chain length gives the bound.Source: §9 · p. 10
  • Disjunctive slack is the gap between time to degree in the conjunctive collapse and the true time; it is positive only when alternatives differ in level.Slack can propagate down the conjunctive chain above a disjunctive course.Source: §9 · p. 10

10 The empirical boundary across the corpus

Across latest-catalog data from 22 UAE universities, the analysis finds that prerequisite disjunction is uncommon, while capacity is the operative constraint on time to degree. Course-level slack can propagate beyond courses with disjunction, even though curriculum-level slack is zero throughout the corpus.

10 The empirical boundary across the corpus

  • The cross-section covers the latest catalog editions of 22 universities; institution-level figures focus on 17 with at least 20 prerequisite-bearing courses.Corequisites are excluded; removing prerequisite arcs within strongly connected components can only understate reported chain depth.Source: §10 · p. 10, §10.4 · p. 13

10.1 Real curricula inhabit the tractable fragment

  • 88.0 percent of the 6,422 prerequisite-bearing courses are purely conjunctive; disjunction appears in 12.0 percent.The disjunctive width has median two and ninetieth percentile four, but load is already NP-hard at width two.Source: §10.1 · p. 11

10.2 Disjunction is concentrated, not spread

  • Disjunction is concentrated: Khalifa University has a 45.0 percent share and the American University of Sharjah 34.3 percent, well above most institutions.The two institutions also have the largest disjunctive correction in the companion measurement.Source: §10.2 · p. 11, Figure 2 · p. 12

10.3 The slack is real, and shallow chains leave capacity to bind

  • Curriculum-level slack is zero at every institution, although 573 courses have positive course-level slack, averaging 1.55 terms and reaching five.The deepest chains run through mandatory conjunctive courses, while slack propagates to conjunctive descendants.Source: §10.3 · p. 13

10.4 Data cautions

  • The latest-edition disjunctive share of 12.0 percent agrees with the 10.7 percent measured across all editions, with the difference reflecting growth in expressive notation.The degraded-flat-list annotation affects no course in the analysed cross-section.Source: §10.4 · pp. 13–14

11 Two comparison problems: subsumption and consensus

The section formalizes two curriculum-comparison questions: whether completion of one program also completes another after credit transfer, and how to reconcile prerequisite assignments.

11.1 Completions, and why naïve transfer is vacuous

  • Under free capacity, taking every course completes a curriculum, making it vacuous to ask only whether transferred courses can be retained while completing the receiving program.The substantive question is whether completing the sending program already completes the receiving one.Source: §11.1 · pp. 14–15

11.2 Program subsumption

  • Subsumption asks whether every completion of C1 maps to a completion of C2; it is coNP-complete even for prerequisite-free curricula under free capacity and bijective matching.The free-capacity membership argument does not settle bounded-capacity subsumption.Source: §11.2 · p. 15

11.3 Consensus prerequisite recovery

  • Consensus prerequisite recovery is NP-complete even with one input; its hardness comes from requiring the reconciled prerequisite graph to be acyclic.Hardness for the empirically relevant case of three or more individually acyclic inputs remains conjectural.Source: §11.3 · p. 16

12 Conclusion

The paper attributes degree-planning hardness to distinct curriculum commitments and finds that capacity, rather than prerequisite logic, governs timely completion in the university corpus.

12 Conclusion

  • Time to degree is polynomial with unbounded capacity but strongly NP-hard when capacity binds, even without prerequisites.The result holds for arbitrary disjunctive prerequisites and electives when capacity is unbounded.Source: §12 · p. 16
  • Load is polynomial for conjunctive, mandatory curricula and strongly NP-hard through either disjunction or overlapping electives, separating its hardness sources from time to degree.The two objectives therefore have disjoint sources of hardness: capacity governs time, while disjunction or electives govern load.Source: §12 · p. 16
  • The delay-factor component is a polynomial upper bound on time to degree, exact for conjunctive curricula; subsumption is coNP-complete and consensus recovery NP-complete.The delay-factor bound is loose elsewhere by the disjunctive slack.Source: §12 · p. 16
  • Across 22 universities, nearly nine in ten courses are purely conjunctive, and capacity—not prerequisite logic—governs timely completion.Curriculum-level disjunctive slack is zero throughout; course-level slack is positive on roughly one course in eleven.Source: §12 · p. 17
Loading 2610.03392v1…