Research map / Learning theory and algorithms / Combinatorial and search optimization
Was Fixing This Really That Hard? On the Complexity of Correcting HTN Domains
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Allow any nonempty subset of action insertion, action deletion, and ordering-constraint deletion | HTN domain correction for white-list plans · CHANGEX | computational complexity: NP-complete | Mixed |
| Supply decomposition forests for the white-list plans | HTN domain correction · CHANGEDFX | computational complexity: NP-hard | Mixed |
| Supply decomposition forests and task-to-plan mappings, while disallowing action insertion | HTN domain correction · CHANGEDFMX | computational complexity: in P | Helped |
| Allow action insertion even when decomposition forests and task-to-plan mappings are supplied | HTN domain correction · CHANGEDFMX | computational complexity: NP-hard | Hurt |
| Require both white-list acceptance and black-list rejection | HTN domain correction · CHANGEWBX | computational complexity: at least NP-hard; in Σp₂ | Mixed |
| Test whether an action sequence linearises a partially ordered task network | VALIDSEQ · VALIDSEQ | computational complexity: NP-complete | Mixed |
Closest papers by meaning
- Told You That Will Not Work: Optimal Corrections to Planning Domains Using Counter-Example Plans (AAAI 2025 · similarity 0.87)
- Learning Planning Domains from Non-redundant Fully-Observed Traces: Theoretical Foundations and Complexity Analysis (AAAI 2024 · similarity 0.85)
- On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence (AAAI 2024 · similarity 0.85)
- Hierarchical Planning for Complex Tasks with Knowledge Graph-RAG and Symbolic Verification (ICML 2025 · similarity 0.85)
- System 1.x: Learning to Balance Fast and Slow Planning with Language Models (ICLR 2025 · similarity 0.85)
- On the self-verification limitations of large language models on reasoning and planning tasks (ICLR 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.