| paper | d4-conf-aaai-2013-0145 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard under polynomial-time Turing reductions, already for \(p=1\) and \(\tau=O(n^2)\). A learner with the stated polynomial query and computation bounds would imply \(\mathrm{P}=\mathrm{NP}\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given oracle access to exact rational fractions of a society preferring each response to any queried pair of outcomes, where the society is an unknown distribution with support size \(\tau\) over acyclic binary CP-nets with at most \(p\) parents per node, can an adaptive learner output a rational distribution over CP-net types that matches the oracle on every outcome pair using polynomially many queries and computation in \(n^p\), \(\tau\), and response-mass bit length \(L\)?
Agents are typed by their complete CP-net preference model, and \(\mu_t\) is the fraction of society of type \(t\). A query presents an outcome pair to the population and returns the mass preferring each order or reporting indifference. The learner outputs a rational distribution over CP-net types with the same aggregate responses on every outcome pair.
The mirror hides the support and replaces individual answers with aggregate fractions, whereas the paper learns one CP-net from one user's answers; this limits theorem transfer, though it does not erase the recognizable population-level preference-learning question.
fatal: False
The mirror extends Theorem 1's query-based learning task to a population distribution; the paper's experiments on individual-model agreement and computation time are not covered by a corresponding guarantee.
The most defensible mirror is Mass-Weighted CP-Net Population Learning. Imagine a large recommender system serving many users with preferences over the same \(n\) binary product attributes. A user’s type is their complete, stable query behavior, represented by an acyclic CP-net with at most \(p\) parents per node. Users of the same type share that behavior; \(\mu_t\) is the fraction of users of type \(t\). The intended regime has many users but relatively few distinct types, so \(N\gg\tau\), where \(\tau=|\operatorname{supp}(\mu)|\).
A query presents the same pair of outcomes \((o_1,o_2)\) to the population and returns the exact fractions who prefer the first, prefer the second, or report indifference. The learner adaptively chooses queries and must output an explicit rational distribution \(\hat\mu\) over CP-net types whose aggregate response agrees with the population’s response on every possible outcome pair. The question is whether this can be done with polynomially many queries and computation in \(n^p,\tau\), and the response-mass bit length \(L\). The society is the continuous object: each response is a fraction of population mass. Outcomes and queries remain discrete.
The anchor is Theorem 1, stated by the authors; its proof is omitted in the paper. It says that LEARN-CP-NET is resolute—it is guaranteed to output a CP-net consistent with the user’s responses—and runs in time polynomial in \(n^p\) and \(q\) in the worst case, where \(p\) bounds the number of parents and \(q\) is the confidence parameter. Thus, for constant \(p\), the stated running time is polynomial in \(n\) and \(q\). This is the paper’s named computational result; it offers no comparable named hardness result.
The mirror preserves the paper’s central task: infer a compact conditional-preference model from outcome-comparison queries. It changes the queried subject from one user to a population, and the object to be learned from one CP-net to a mass-weighted collection of user types. I think the authors could recognize this as a natural population-level extension of their problem, though the theorem itself does not establish its complexity.
My provisional expectation is continuum-specific difficulty (Class C) for the latent-support version. The individual-type learner’s polynomial guarantee does not imply that aggregate responses reveal the underlying mixture, or that a sparse mixture can be recovered efficiently. Those are new identifiability and computation questions. If the support types were already known, estimating masses would instead look like a linear-programming problem and could plausibly be tractable. Further questions are whether the mixture is identifiable up to aggregate-query equivalence, whether approximate response matching is easier than exact matching, and how complexity changes when support is known.
The weakest point is the change in learning target. The paper learns one user’s CP-net from that user’s responses; my mirror learns a population’s mixture from aggregate responses. That is a real extension, not a consequence of Theorem 1. The positive case rests on its close connection to the paper’s query-and-modeling problem and on a credible regime of many users sharing relatively few complete preference types. It should not be presented as a result already implied by the paper.
Theorem 1 is a genuine computational anchor, so the “no named result” objection does not apply. The problem is that its computation is about one user: the algorithm asks that user comparisons and returns a CP-net consistent with that user’s evidence. Its running time depends on \(n,p,q\), with no population parameter.
The most faithful population version has little population content. If everyone has the same query behavior, \(\mu=\delta_N\), the aggregate response to every query is just that one user’s response, and Theorem 1 applies unchanged. If there are \(\tau\) known types and users can be queried by type, run the learner for each type; the masses do not affect the task. In either case, population size and mass add no new computational question.
The proponent makes mass matter by changing the interface and the target: each query returns fractions of the population in three response categories, and the learner reconstructs a mixture of CP-nets. That is a coherent possible problem, but the theorem does not address it. Its single-user consistency tests and 2-SAT construction have no stated guarantee for aggregate evidence from potentially conflicting users. Asking individuals sampled from the population would avoid the aggregate oracle, but then the task needs a new sampling and output objective—such as learning a representative model or an ensemble—and a way to handle hidden types. Those are new choices, not consequences of Theorem 1.
The recommender scenario makes repeated user types plausible, so I would not reject it on high-multiplicity grounds. The harder issue is whether the authors would recognize latent-mixture recovery as their problem. Under the programme’s explicit support-list model, the support types are already given as complete descriptions; hiding them and supplying only aggregate query access changes the input model that makes learning necessary. The proposed version may be worthwhile adjacent research, but its computational question is built by changing both what a query returns and what the learner must produce. That leaves Theorem 1 without a continuous mirror anchored in the paper.
This is a scope argument, not a proof that no such extension could interest the authors. Its weak point is precisely that they might embrace population preference learning as a natural extension of their online-learning problem; the paper alone cannot rule that 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.