Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIf the algorithm performs sound pruning, then the last plan returned, if any, is optimal.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support \(T\) of complete HTN request types, rational masses \(\mu_t\ge 0\) with \(\sum_t\mu_t=1\), a finite implicitly represented plan set \(\Pi_t\) for each type, plan metrics \(M_t(\pi)\), resource use \(a_{t\pi r}\), and per-capita capacities \(b_r\), find an optimal rational allocation \(x_{t\pi}\ge 0\) minimizing \(\sum_{t\in T}\sum_{\pi\in\Pi_t}x_{t\pi}M_t(\pi)\), subject to \(\sum_{\pi\in\Pi_t}x_{t\pi}=\mu_t\) for every \(t\) and \(\sum_{t\in T}\sum_{\pi\in\Pi_t}x_{t\pi}a_{t\pi r}\le b_r\) for every resource \(r\). Each unit of mass receives an indivisible valid plan; allocation across a type’s population may be fractional.
A society is given by its support: a list \(T\) of \(\tau\) request types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) counts supported types, not possible types.
Each type supplies a finite-domain HTN request: initial state, initial task network, primitive operators with preconditions and effects, decomposition methods with task-network constraints, hard constraints, preferences, and a metric expression. All applicable methods are alternatives; a valid plan must complete the initial network, execute legally, and satisfy every hard constraint.
Plans retain their decomposition and its start/end annotations. Preferences use finite-trace PDDL3 semantics, extended by \(\operatorname{occ}(a)\) at a primitive action's occurrence and \(\operatorname{initiate}(X),\operatorname{terminate}(X)\) at a task or method instance's start/end; for primitive tasks these coincide with occurrence. These extensions are excluded from precondition preferences.
The input promises that each implicitly represented set \(\Pi_t\) of complete annotated valid plans is finite; it may be empty. No enumeration of \(\Pi_t\) is supplied.
Metric and resource expressions are rational arithmetic circuits over named preference-violation counts, primitive-action occurrence counts, and final-state fluent values, using rational constants and arithmetic operations; they must be defined on every valid plan. Preference-family violations count individual ground instances, and precondition violations count failed occurrences. Metrics \(M_t(\pi)\) may be signed; resource uses \(a_{t\pi r}\) and binary-rational capacities \(b_r\) are nonnegative.
An allocation consists of rational masses \(x_{t\pi}\geq0\) satisfying \(\sum_{\pi\in\Pi_t}x_{t\pi}=\mu_t\) and \(\sum_{t,\pi}x_{t\pi}a_{t\pi r}\leq b_r\) for every resource \(r\). Each mass unit receives one complete plan; a type's mass may be split among plans. Minimize \(\sum_{t,\pi}x_{t\pi}M_t(\pi)\), with all objective ties allowed.
Let \(m\) denote the total structural description size of the requests and expression circuits, \(R\) the number of resources, and \(L\) the total binary input length, including numerical data and a rational threshold \(K\).
Is deciding whether a feasible allocation has objective at most \(K\) solvable in polynomial time in \(m,\tau,R,L\), or is it NP-hard?
For a single discrete HTN request, exhaustive branch-and-bound search with sound pruning returns an optimal last plan when it terminates; this is an optimality guarantee, not a polynomial-time bound. [Verified source](https://www.cs.toronto.edu/kr/publications/1242050782_Sohrabi-IJCAI09.pdf)
Discrete HTN plan existence is NP-complete even for primitive propositional task networks with unrestricted ordering. [Verified source](https://www.cs.umd.edu/~nau/papers/erol1996complexity.pdf) No result settling this exact mass-allocation problem was identified in the search.
The decision problem is NP-hard, even with one supported type, one unused resource, no preferences or hard constraints, and an acyclic, totally ordered HTN. The reduction below also guarantees that every constructed instance has a feasible allocation.
Consequently, a polynomial-time algorithm in \(m,\tau,R,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
The supplied [HTN complexity result](https://www.cs.umd.edu/~nau/papers/erol1996complexity.pdf) establishes NP-completeness of primitive propositional plan existence with unrestricted ordering. Here we give a direct reduction that additionally guarantees feasibility and checks the finiteness promise.
We reduce from the standard NP-complete problem \(3\text{-}\mathrm{SAT}\). Let the input formula be \(\varphi=\bigwedge_{j=1}^{q}C_j\), with variables \(z_1,\ldots,z_n\), where every clause contains three literals. We may restrict to \(n,q\geq 1\).
Create one supported request type \(t\), with mass \(\mu_t=1\).
Its initial task network consists of compound tasks \(X_1,\ldots,X_n\), ordered as \(X_1\prec\cdots\prec X_n\). For each \(i\), give \(X_i\) exactly two unconditional alternative methods:
Every primitive operator has empty preconditions and empty effects. There are no additional hard constraints or preferences. The state can therefore be a single fixed state.
Completing the initial network executes exactly one of \(T_i,F_i\) for each \(i\), in increasing order of \(i\). Every selection of these alternatives is valid.
Define \(c_i(\pi)\) to be the primitive-action occurrence count of \(T_i\) in plan \(\pi\). Thus \(c_i(\pi)\in\{0,1\}\), and the assignment represented by \(\pi\) is \(z_i=c_i(\pi)\). Every Boolean assignment is represented by a valid complete plan.
The construction contains no recursive methods. Every complete decomposition makes exactly \(n\) method choices and produces exactly \(n\) primitive occurrences. There are only \(2^n\) possible selections of alternatives.
The retained decomposition contains only a bounded number of task and method instances. Their start/end annotations lie on the finite execution trace; there are no numerical scheduling variables in this construction. Consequently, only finitely many annotated complete plans exist.
In particular, \(\Pi_t\) is finite and nonempty, as required.
For a literal \(\ell\), define its falsity indicator by \(u_{z_i}(\pi)=1-c_i(\pi)\) and \(u_{\neg z_i}(\pi)=c_i(\pi)\).
Because \(c_i(\pi)\) is Boolean, \(u_\ell(\pi)\) equals \(1\) exactly when \(\ell\) is false under the represented assignment, and equals \(0\) otherwise.
If \(C_j=\ell_{j1}\lor\ell_{j2}\lor\ell_{j3}\), define \(d_j(\pi)=u_{\ell_{j1}}(\pi)u_{\ell_{j2}}(\pi)u_{\ell_{j3}}(\pi)\). This product equals \(1\) exactly when all three literals are false, which is exactly when \(C_j\) is unsatisfied.
Set the request’s metric to \(M_t(\pi)=\sum_{j=1}^{q}d_j(\pi)\). This is an allowed rational arithmetic circuit over named primitive-action occurrence counts, using only subtraction, multiplication, addition, and the constant \(1\). It is defined on every valid plan.
We have therefore proved:
Use one resource with constant usage \(a_{t\pi 1}=0\) and capacity \(b_1=0\). Set the threshold to \(K=0\). All masses, capacities, and thresholds have valid binary-rational encodings.
If \(\varphi\) is satisfiable, choose a valid plan \(\pi^\star\) representing a satisfying assignment. Set \(x_{t\pi^\star}=1\) and every other allocation mass to \(0\). These masses are rational, satisfy the type-mass equality, and satisfy the resource constraint. Their objective is \(M_t(\pi^\star)=0\), so the allocation instance is a yes-instance.
Conversely, suppose a feasible allocation has objective at most \(0\). Each term \(x_{t\pi}M_t(\pi)\) is nonnegative. Therefore, every plan receiving positive mass must have metric \(0\). Since \(\Pi_t\) is finite and \(\sum_{\pi\in\Pi_t}x_{t\pi}=1\), at least one plan receives positive mass. Its represented assignment satisfies \(\varphi\).
Equivalently, if \(\varphi\) is unsatisfiable, every valid plan has \(M_t(\pi)\geq 1\), and every feasible allocation has objective at least \(\sum_{\pi\in\Pi_t}x_{t\pi}=1\). Thus splitting mass cannot meet the threshold.
Every constructed instance is feasible: any assignment supplies a valid plan to which all mass can be allocated.
The construction uses \(n\) compound tasks, \(2n\) methods, \(2n\) primitive operators, and an arithmetic circuit with a number of gates linear in \(n+q\). Including identifiers, its binary description length is polynomial in the formula’s input length. Moreover, \(\tau=R=1\), and all added rational constants have constant encoding length.
This is a polynomial-time many-one reduction from \(3\text{-}\mathrm{SAT}\). It proves NP-hardness of the requested decision problem under every stated promise, including on instances whose feasibility is guaranteed. No membership claim for the unrestricted problem is needed to settle the question.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the task. It establishes NP-hardness by a polynomial-time many-one reduction from \(3\text{-}\mathrm{SAT}\), including the stronger restriction that every constructed allocation instance is feasible. No major or minor issues were found.
The invoked source theorem is that satisfiability of Boolean formulas in conjunctive normal form with exactly three literals per clause is NP-complete. The stated restriction \(n,q\geq 1\) does not affect NP-hardness.
The constructed request correctly represents assignments:
Consequently, every complete plan contains exactly one of \(T_i,F_i\) for each \(i\), and every Boolean assignment has a representing plan. The claimed occurrence-count restriction \(c_i(\pi)\in\{0,1\}\) follows.
The single positive mass \(\mu_t=1\) satisfies the support and normalization requirements.
The finiteness argument accounts for both execution and retained decomposition.
There is no recursion, every complete decomposition makes exactly \(n\) method choices, and every resulting execution contains exactly \(n\) primitive occurrences. Thus there are finitely many decomposition structures and primitive sequences.
The prover explicitly places start/end annotations on the finite execution trace and excludes numerical scheduling variables from the construction. Under the task’s finite-trace interpretation, boundedly many instances each have finitely many possible annotation positions. Hence retaining annotations does not invalidate finiteness.
The proof appropriately claims only \(2^n\) alternative selections, rather than asserting that the number of annotated plans is exactly \(2^n\). Nonemptiness also follows from the validity of every selection.
The literal indicators have the asserted values:
All factors are Boolean, so their product is \(1\) exactly when all three literals of the clause are false. Summing these products therefore counts unsatisfied clauses.
This calculation remains valid for repeated literals and clauses containing complementary literals. No distinctness assumption is needed.
The metric uses only permitted occurrence counts, rational constants, and arithmetic operations. There is no division or other domain restriction, so it is defined on every valid plan. Its range is indeed \(\{0,\ldots,q\}\), and metric zero is equivalent to satisfaction of the formula.
Although the general task permits signed metrics, the reduction legitimately uses the nonnegative subclass.
Constant usage \(a_{t\pi 1}=0\) and capacity \(b_1=0\) satisfy the required nonnegativity conditions. Every allocation satisfies the resource constraint.
Any valid plan can receive the entire mass \(1\). This gives a rational feasible allocation regardless of whether the formula is satisfiable. The claimed guarantee of feasibility is therefore established.
Both directions of the reduction are valid.
If the formula is satisfiable, assigning mass \(1\) to a representing plan yields objective zero and meets the threshold \(K=0\).
Conversely, every summand \(x_{t\pi}M_t(\pi)\) is nonnegative. An objective at most zero therefore forces every positive-mass plan to have metric zero. Finiteness and total mass \(1\) ensure that at least one such plan exists, yielding a satisfying assignment.
The alternative unsatisfiable-case calculation is also correct: every plan then has metric at least \(1\), so every feasible allocation has objective at least \(1\). Fractional splitting cannot evade the threshold.
The task, method, and operator counts are linear in \(n\). The circuit has linear gate count in \(n+q\); binary identifiers contribute only polynomial encoding overhead. No enumeration of plans is required.
All numerical constants have constant encoding length, and \(\tau=R=1\). Thus construction time and output length are polynomial in the formula’s input length.
The reduction preserves yes-instances and no-instances and satisfies every stated promise. It proves NP-hardness of the requested decision problem. Membership in NP is neither established nor needed for this conclusion.
The ancillary HTN citation is accurately described: Theorem 8 states NP-completeness for primitive propositional plan existence without imposing total ordering. It is background, not an unverified application supporting this reduction. [Erol, Hendler, and Nau, Theorem 8](https://www.cs.umd.edu/~nau/papers/erol1996complexity.pdf)
None is required. The proof resolves the assigned complexity question without relying on exhaustive search having polynomial running time.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.