| paper | d4-conf-ijcai-2009-0160 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\) · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
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.
Types are complete HTN request instances with rational population mass \(\mu_t\); decision variables \(x_{t\pi}\) allocate mass to valid indivisible plans; the objective minimizes average preference-metric cost under per-capita shared-service capacities.
The paper’s single-request theorem does not provide the resource-priced plan oracle needed by the aggregate LP, and cross-request capacity constraints are absent from the paper.
fatal: False
The mirror covers conditional optimality of preferred HTN-plan selection at the cohort allocation level. It leaves the paper’s language and preprocessing contributions, search heuristics, experimental comparisons, and any claim about aggregate running time outside the result.
The strongest honest anchor is Theorem 1, proved in this paper (its proof sketch follows the earlier HPLAN-P proof). It states: *if the algorithm performs sound pruning, then the last plan it returns, if any, is optimal.* Here “optimal” means minimum value of the PDDL3 preference metric among plans satisfying the HTN problem. The theorem is conditional on sound pruning and search exhausting the remaining space; it gives no polynomial-time bound. The paper has a named computational theorem, but no named result classifying the underlying problem as polynomial-time solvable or NP-hard.
A continuous problem I would put to a prover is High-Multiplicity Preferred HTN Allocation. An instance has a finite support \(T\) of complete request types, with rational masses \(\mu_t\geq 0\) summing to \(1\). A type includes everything that affects its planning problem: initial state, task network, applicable HTN domain, hard constraints, preferences, and metric. Assume each type has finitely many feasible primitive plans, represented implicitly by a finite decomposition search space. Each plan \(\pi\) must remain a valid, indivisible HTN plan for its type. Let \(M_t(\pi)\) be its preference-metric value, and let \(a_{t\pi r}\) be its use of shared service resource \(r\). Given per-capita capacities \(b_r\), choose rational masses \(x_{t\pi}\geq 0\) to solve
\[ \min \sum_{t\in T}\sum_{\pi} x_{t\pi}M_t(\pi) \]
subject to
\[ \sum_{\pi}x_{t\pi}=\mu_t \quad\text{for every }t, \qquad \sum_{t\in T}\sum_{\pi}x_{t\pi}a_{t\pi r}\leq b_r \quad\text{for every }r. \]
A solution is the allocation of each type’s population mass across valid plans. Thus every unit of mass gets a whole primitive plan; only the type-level allocation is fractional. The shared capacities are the population-level co-modification: for \(N\) requests, the corresponding physical supplies scale as \(N b_r\).
The regime is a travel or web-service platform handling many repeated requests: for example, a large cohort of users with a small number of travel templates and preference policies, choosing among services with limited capacity. The request count \(N\) is much larger than the number of complete types \(\tau=|T|\). That is plausible in the domains this paper itself discusses, especially repeated web-service composition. But the type count is small only if requests really share all planning-relevant details; different task networks, preferences, prices, or parameters mean different types.
This preserves the paper’s distinctive question: which primitive plan, task decomposition, method, and parameters produce a preferred valid plan? The preferences can still concern states, action occurrences, task or method occurrences, and temporal properties. The new decision is how much of each request type receives each such plan, subject to population-level supply. That makes the problem a natural cohort extension of preferred HTN planning, though not a restatement of the paper’s single-agent model. Theorem 1 motivates optimal plan generation for the implicit plan columns; it does not prove that this allocation problem is efficiently solvable.
For the general version, I would expect Class B, as a working prediction rather than a result of this paper. Set \(\tau=1\) and make capacities nonbinding. The optimal allocation value then equals the best individual plan metric: any plan receiving positive mass in an optimum is individually optimal. So solving the continuous problem solves the original single-instance optimization problem. Any hardness of that discrete problem transfers through this embedding; high multiplicity does not by itself remove the combinatorial choice among HTN decompositions. The paper’s theorem supplies no such hardness result, so the classification remains an open question here.
The main follow-up questions are whether the whole-plan pricing problem can be solved efficiently for useful HTN families; whether an LP over plan columns admits efficient separation in the domain size, \(\tau\), preference description length, and capacity parameters; and how the continuous optimum compares with assigning plans to a finite cohort of \(N\) indivisible requests.
My weakest point is the population coupling. Shared capacities make this a more substantial aggregate problem, but the paper does not study cross-request capacity constraints. Without them, the problem decomposes by type and the continuous formulation adds little beyond repeatedly solving the original problem. With them, the authors might regard it as multi-request service allocation rather than their preferred single-agent HTN planning problem. I think it remains a credible mirror because it keeps each request’s HTN problem and plan semantics intact, and the paper explicitly motivates its techniques with reusable services and travel planning. It mirrors Theorem 1’s optimal preferred-plan computation, not the paper’s experimental comparisons or a claimed complexity classification.
The proponent has identified the paper’s strongest anchor, but Theorem 1 is not a complexity result. It says that if pruning is sound and the search finishes, the last plan returned is optimal. Since the algorithm uses inadmissible heuristics, that can require exhausting the search space. The theorem gives no tractability or hardness claim for a continuous model to carry over.
For a faithful population version, give each request type a mass and let each request receive an individually valid HTN plan. Without constraints linking requests, the optimization separates by type. If everyone has the same type, the mass just scales the value of that type’s best plan; with several types, one solves the original planning problem once per type and weights the results. The population distribution adds little computational structure.
The proposed shared-capacity version is the strongest repair. A large platform with repeated travel or web-service requests and limited service capacity is plausible. But the capacities create a batch allocation problem absent from the paper, which plans for a single initial task network. The plan-column LP expresses that new coupling; it does not inherit an efficient pricing algorithm from Theorem 1. Pricing still requires finding good HTN plans, now with resource costs. This could be a worthwhile project, but its main question is resource-constrained allocation across plans, rather than a continuous mirror of the paper’s optimality theorem. Adding fairness or other population objectives would make that shift still larger.
So the best case against is that the mirror either preserves the paper’s independent planning problem and gains little from continuity, or gains a substantive population-level problem by adding constraints the paper does not study. I would reject this as a direct mirror of Theorem 1. The broader claim that no scenario yields a worthwhile mirror is harder to defend: repeated requests with shared capacity are credible, and the proponent’s version may be a valuable adjacent problem. The negative case is therefore strongest on fit to this paper, and weak on the universal claim.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.