| paper | d4-conf-ijcai-2003-0126 |
| 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}\)-complete, even with binary domains, unit importance weights, exact-match similarities, catalogue equal to support, and dyadic masses. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 4
Given a shared catalogue \(C\), attributes \(A\) with finite value sets, the paper’s similarity rule, and a finite set \(T\) of complete preference profiles with rational masses \(\mu_t\), find an adaptive question tree minimizing \(\sum_{t\in T}\mu_t\ell(t)\), where \(\ell(t)\) is the number of questions asked to type \(t\). Require that at every leaf, for every positive-mass type consistent with that path, the retrieval set for the partial query equals the retrieval set for that type’s complete query; equivalently, require Theorem 4’s safe-stopping test for each such type.
A high-multiplicity customer-service workload with users grouped by complete preference profile over a shared catalogue; rational mass represents each profile’s share, a shared adaptive policy chooses questions, and the objective is to minimize average questions while preserving every user’s full-query retrieval set.
Theorem 4 certifies whether each leaf is safe but does not optimize the shared adaptive question tree; the mirror adds a global policy-optimization problem.
fatal: False
The mirror uses Theorem 4’s exact-stopping guarantee and the paper’s average dialogue-length objective; it leaves the empirical comparisons of attribute-selection strategies and similarity thresholds aside.
There is no result here saying a problem is NP-hard, in P, FPT, or otherwise classifying its complexity. My strongest honest anchor is Theorem 4, proved in this paper: it gives a necessary and sufficient test for safely ending a recommendation dialogue. For a partial query \(Q\), let \(rs(Q)\) be the cases currently tied for highest similarity. The dialogue can be stopped without loss of precision or recall exactly when (a) all cases in \(rs(Q)\) agree on every unasked attribute, and (b) every case in \(rs(Q)\) dominates every case outside it—that is, no completion of the query lets an outsider tie or surpass the current winners. The paper’s proof also gives a useful checking shortcut: once (a) holds, it suffices to compare one current winner against the outsiders. The theorem is proved here, and the paper discusses testing its conditions in time linear in the case library’s size. It is the lead anchor because it underwrites the paper’s central promise: shorter dialogues with a guarantee of unchanged recommendation quality. [The paper](https://www.ijcai.org/Proceedings/03/Papers/017.pdf)
My proposed mirror is Mass-Weighted Exact Recommendation Dialogue. The instance has a shared product or service catalogue \(C\), attributes \(A\) with finite value sets, the paper’s similarity rule, and a population distribution \(\mu\) over complete user preference profiles \(T\). Each type \(t\in T\) specifies every preference that affects the query and its answers; \(\mu_t\) is the fraction of users of that type. A policy is an adaptive question tree: at each node it asks a still-unasked attribute, then splits the group by the answer. At a leaf it recommends the current retrieval set. Require every leaf to satisfy Theorem 4’s safe-stopping conditions, so the recommendation remains correct for every possible completion. The task is to find a policy minimizing \(\sum_{t\in T}\mu_t\,\ell(t)\), where \(\ell(t)\) is the number of questions that type is asked. A solution is the policy tree and its leaf recommendations. The natural parameters are \(|A|\), support size \(\tau=|T|\), \(|C|\), and the bit length of the rational masses and other input.
A plausible regime is a large retailer, travel service, or procurement portal with many users choosing from a shared catalogue. For example, millions of customers might fall into a comparatively small set of recurring preference profiles over attributes such as price band, region, duration, or product type. The type records the complete relevant preference profile, so grouping does not hide differences the problem uses. Mass is the share of users in each profile; the objective measures average questions per user, directly capturing the operational cost that motivates the paper. This extends the paper’s concern with average dialogue length and exact retrieval, rather than replacing it with a question about fractional products or uncertain outcomes. The authors could plausibly recognize it as their problem at population scale: their paper already evaluates dialogue lengths across many simulated recommendation dialogues, though it does not study shared cohort policies.
For this policy-optimization question, I would expect hardness to transfer if the corresponding finite-cohort optimization is hard: a finite cohort with \(n_t\) users of each type is exactly represented by \(\mu_t=n_t/N\), and minimizing average questions differs from minimizing the total only by the constant factor \(N\). Theorem 4 supplies a tractable stopping certificate; it does not solve the global problem of choosing the best adaptive tree. Further questions include whether the policy problem is FPT in \(\tau\) or \(|A|\), and how much dialogue burden can be saved if a small fraction of the population may receive a non-optimal recommendation.
The weak point is that the continuous mass mainly weights a collection of user dialogues; the similarity and safe-stopping mathematics still apply one query at a time. So this is a credible high-multiplicity service regime, but it does not yet reveal a new continuous-optimization structure like an LP with a pricing problem. Also, Theorem 4 is an algorithmic characterization, not a complexity-class result; if the anchor requirement is restricted strictly to named hardness or tractability classifications, this paper has no such anchor.
The cleanest objection is that Theorem 4 is a result about one user’s dialogue, not a population decision. Its stopping test takes a partial query \(Q\) and asks whether the currently best cases remain best for every relevant completion of that user’s preferences. For a population with exact types, the no-loss guarantee therefore applies separately along each user’s path. Repeating a type changes how many users follow that path; it does not change when that dialogue can safely stop. Allowing errors for a small share of users would make mass affect the objective, but that would replace the paper’s exact guarantee with a different problem.
The stronger version of the proponent’s idea is a retailer that uses one adaptive question policy for many customers and chooses the policy to minimize \(\sum_t \mu_t\ell(t)\), subject to safe recommendations. Repeated complete preference profiles are a plausible high-multiplicity regime, and fractional masses sensibly measure workload. But this is a new optimal decision-tree problem. Theorem 4 certifies when a leaf is safe; it does not characterize or optimize a population policy. More fundamentally, the paper recommends a product separately for each user. A distribution of customer profiles measures service workload; it does not create a collective choice among those users. Turning it into a shared social choice would require a new aggregation problem and a different outcome.
The paper also has no theorem classifying the complexity of a computational problem. That is not decisive by itself: Theorem 4 is a genuine algorithmic characterization, and the paper’s dialogue-efficiency objective gives the weighted-policy idea a clear connection to its subject. Nor is it credible to claim that user profiles cannot repeat or that the retailer scenario is implausible.
So the negative case is limited. The weighted-policy formulation is coherent and may be worth studying, but its strongest version is an adjacent population-level service-optimization problem, not a continuous mirror of Theorem 4’s per-user stopping result. If the programme counts that adjacent problem as a worthwhile mirror, this case against does not rule it out.
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.