論文の概要: The Plan Language of a Curriculum: A Formal Model and the Complexity of Degree Planning
- arxiv url: http://arxiv.org/abs/2610.03392v1
- Date: Fri, 02 Oct 2026 14:41:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-06 00:14:30.427844
- Title: The Plan Language of a Curriculum: A Formal Model and the Complexity of Degree Planning
- Title（参考訳）: カリキュラムの計画言語:形式モデルと詳細計画の複雑さ
- Abstract要約: 我々は,学術カリキュラムを,実現可能な学習計画の言語生成としてモデル化する。
標準曲率-複素度計量の遅延因子成分は、時間と次数に応じて、ゆるやかに計算可能な上界であることが示される。
前提条件を満たすコースの88%は、純粋に結束的である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- 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.
- Abstract（参考訳）: 前提条件は単調な正規形式のブール式,次数要件は貸借制限,学習プランは長期単位の信用能力によって制限された項の列である。
本モデルでは, 両目標の複雑さ, 用語数, 信用負荷の合計を整理し, ハードネスの源泉に責任を負う構造的コミットメントを分離する。
次数は、任意の解離的前提条件と任意の選択条件に対して、各項の容量が非有界であるときに多項式であるので、解離はその硬さに寄与することはない。
負荷は相補的: 解離と重なり合う選択はそれぞれ独立してNPハードであり、その複雑さは容量に依存しないが、負荷は連結的で必須な断片上の多項式である。
したがって、2つの目的は不連続な硬さの源である。
標準曲率距離の遅延因子成分は、次数に応じて多項式計算可能な上界であり、整合フラグメントの正確な値であり、解離スラック(disjunctive slack)と命名する量によって他所で疎結合であることを示し、プログラムの仮定がcoNP完全であり、コンセンサス・前提条件回復がNP完全であることを証明した。
大学22校のコーパスでモデルを検証した結果,前提条件を満たす授業の88%は純粋に連結的であり,その能力は前提条件の論理ではなく,時間的・段階的制約であることがわかった。
カリキュラムコーパスは公開されている(https://doi.org/10.5281/zenodo.22334674)。
関連論文リスト
- When Can One Obtain Certificates of Optimality Using Positivstellensaetze? [4.213177311725992]
フィッシャーの構造的厳密で弱いPositivstzeの公理的核を分離する。
我々は、順序体上の抽象関数代数に対する結果の定理を証明する。
低バウンドおよび大域最適証明を導出し、拡張項長と共有計算グラフの複雑さを解析する。
論文 参考訳（メタデータ） (2026-09-08T13:30:18Z) - Stochasticity Is Not the Hard Part: Reduction and Complexity in Instructional Sequencing over Prerequisite DAGs [2.2660071841277962]
提案手法は,提案手法が状態依存確率で成功し,失敗しても学習者の状態が変化しない,最短経路問題であるシークエンシングについて検討する。
問題は決定論的最短パス問題に崩壊し、前提条件の次数イデアルの格子上の問題となる。
論文 参考訳（メタデータ） (2026-08-05T23:00:28Z) - Learning Conditional Averages [52.361762722359366]
本稿では,PACフレームワークにおける条件平均学習の問題を紹介する。
ターゲットのコンセプトそのものを学ぶのではなく、各インスタンスの平均ラベルをその周辺で予測することが目標だ。
より一般的には、PAC学習をいくつかのドメインで発生する学習タスクをキャプチャする設定に拡張する。
論文 参考訳（メタデータ） (2026-02-12T13:20:29Z) - The Topology of Hardship: Empirical Curriculum Graphs and Structural Bottlenecks in Engineering Degrees [0.0]
工学の学位はしばしば「硬い」と見なされるが、この難しさは通常、内容の難しさや学生の弱点の観点から議論される。
コース前提ネットワークとカリキュラムグラフに関する最近の研究は、学習計画が特定可能なハブとボトルネックを持つ複雑なネットワークとしてモデル化できることを示してきた。
本稿では,経験的学生軌跡から得られたカリキュラムの複雑さを定量的に記述した,難易度のトポロジについて紹介する。
論文 参考訳（メタデータ） (2025-12-05T09:34:29Z) - Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Training [76.12556589212666]
学習後のカリキュラムは指数関数的複雑性のボトルネックを回避していることを示す。
結果のみの報酬信号の下では、強化学習の微調整は、サンプルの複雑さを高い精度で達成する。
カリキュラムを意識したクエリにより、報奨託書の呼び出しとサンプリングコストの両方を指数関数的に削減するテストタイムスケーリングの保証を確立する。
論文 参考訳（メタデータ） (2025-11-10T18:29:54Z) - Polynomial-Time Approximability of Constrained Reinforcement Learning [1.223779595809275]
一般化されたマルコフ決定過程の近似の計算複雑性について検討する。
私たちの貢献は、最適に制約されたポリシーを見つけるための時間(0,epsilon)$-additive approximationの設計です。
論文 参考訳（メタデータ） (2025-02-11T18:47:53Z) - From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy [3.44747819522562]
PCHのレベルによって, NPPP, PSPACE, NEXP完全満足度の問題が生じることを示す。
一方、完全言語の場合、すなわち加法、余分化、乗算が可能である場合、反事実レベルの満足度は確率的・因果的なレベルと同じであることを示す。
論文 参考訳（メタデータ） (2024-05-12T20:25:36Z) - An Analysis of On-the-fly Determinization of Finite-state Automata [65.268245109828]
有限状態オートマトンをオンザフライで決定する手法の抽象化を確立し, オートマトンにどのように適用できるかを実証する。
我々の発見の特別な例は、多くの非決定論的遷移を持つオートマトンが、ほとんど常に複雑性の決定性を持っていることである。
論文 参考訳（メタデータ） (2023-08-27T11:51:27Z) - Semantic Probabilistic Layers for Neuro-Symbolic Learning [83.25785999205932]
我々は構造化出力予測(SOP)のための予測層を設計する。
予測が事前に定義されたシンボリック制約のセットと一致していることを保証するため、任意のニューラルネットワークにプラグインすることができる。
我々のセマンティック確率層(SPL)は、構造化された出力空間上で複雑な相関や制約をモデル化することができる。
論文 参考訳（メタデータ） (2022-06-01T12:02:38Z) - Lexically-constrained Text Generation through Commonsense Knowledge
Extraction and Injection [62.071938098215085]
我々は、ある入力概念のセットに対して妥当な文を生成することを目的としているcommongenベンチマークに焦点を当てる。
生成したテキストの意味的正しさを高めるための戦略を提案する。
論文 参考訳（メタデータ） (2020-12-19T23:23:40Z) - Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
この研究は、これらの硬度障壁が、部分観測可能決定過程(POMDP)の豊かで興味深いサブクラスに対する効率的な強化学習を妨げないことを示している。
提案手法は, 観測回数が潜伏状態の数よりも大きく, 探索が学習に不可欠であり, 先行研究と区別できるような, エピソード有限不完全POMDPに対するサンプル効率アルゴリズムOOM-UCBを提案する。
論文 参考訳（メタデータ） (2020-06-22T17:58:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。