We study the complexity-theoretic boundaries of tractability for three
classical problems in the context of Hierarchical Task Network Planning: the
validation of a provided plan, whether an executable plan exists, and whether a
given state can be reached by some plan. We show that all three problems can be
solved in polynomial time on primitive task networks of constant partial order
width (and a generalization thereof), whereas for the latter two problems this
holds only under a provably necessary restriction to the state space. Next, we
obtain an algorithmic meta-theorem along with corresponding lower bounds to
identify tight conditions under which general polynomial-time solvability
results can be lifted from primitive to general task networks. Finally, we
enrich our investigation by analyzing the parameterized complexity of the three
considered problems, and show that (1) fixed-parameter tractability for all
three problems can be achieved by replacing the partial order width with the
vertex cover number of the network as the parameter, and (2) other classical
graph-theoretic parameters of the network (including treewidth, treedepth, and
the aforementioned partial order width) do not yield fixed-parameter
tractability for any of the three problems.

层次任务网络规划中的复杂理论界限研究，包括提供计划的验证、可执行计划的存在性和给定状态是否可以通过某个计划到达等三个经典问题。研究发现，在常数偏序宽度（及其推广）的原始任务网络上，这三个问题均可以在多项式时间内解决，而对于后两个问题，只有在有关状态空间的明显必要限制下才成立。然后，提出了一个算法元定理和相应的下界，以确定使得一般多项式时间可解性结果从原始任务网络推广到一般任务网络的紧密条件。最后，通过分析三个问题的参数化复杂性，表明通过将网络的偏序宽度替换为网络的点覆盖数可以实现这三个问题的固定参数可解性，而网络的其他经典图论参数（包括树宽、树深度和前述的偏序宽度）则无法实现这三个问题的固定参数可解性。