| paper | d4-conf-ijcai-2009-0167 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\) for every fixed \(k\ge 2\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given Boolean variables \(V\), fixed \(k\ge 2\), and a support of report types \(q=(o_q^+,o_q^-)\) with positive rational masses \(\mu_q\) summing to \(1\), does there exist an acyclic \(N\in\mathcal N_k\) such that \(N\models o_q^+\succ o_q^-\) for every support type \(q\)?
Each respondent contributes one comparison-and-choice report \(q\); the society is the distribution \(\mu\) over these report types. Choose an acyclic \(N\in\mathcal N_k\) maximizing \(\sum_{q:N\models o_q^+\succ o_q^-}\mu_q\); exact representability asks whether this maximum is \(1\).
The paper’s formal setting learns one person’s model from observations, whereas the mirror interprets reports as coming from a cohort and fits one representative CP-net; the paper’s future-work discussion of imperfect fitting only indirectly supports that cohort interpretation.
fatal: False
The mirror covers Theorem 1’s exact representability question; it leaves the restricted-input learning algorithm, its soundness and completeness results, and the PAC-learning results aside.
My strongest case is a mirror of the paper’s representability check: can one bounded-indegree CP-net entail every comparison reported by a large respondent population?
Imagine a large preference study about configurations with \(n\) Boolean features. Each respondent is asked to choose between two complete configurations. A type for this problem is the exact pair of configurations and the reported choice; respondents with the same record are indistinguishable to the fitting procedure. The society is a rational distribution \(\mu\) over these types. It could represent millions of responses but have only \(\tau\) distinct types. The setting is plausible for a product segment or another cohort whose comparisons a designer wants to summarize with shared conditional preference rules.
Population CP-net Entailment is the lead question. An instance gives \(V\), the Boolean variables, a fixed \(k\ge2\), and support types \(q=(o_q^+,o_q^-)\) with positive rational masses \(\mu_q\) summing to \(1\). Ask whether there is an acyclic CP-net \(N\in\mathcal N_k\) such that \(N\models o_q^+\succ o_q^-\) for every type \(q\) of positive mass. A solution is that CP-net. Equivalently, it asks whether the maximum mass of comparisons entailed by a candidate network is \(1\):
\[
\max_{N\in\mathcal N_k}\sum_{q:\,N\models o_q^+\succ o_q^-}\mu_q=1.
\]
The runtime parameters are \(n,\tau\), and the bit length \(L\) of the masses.
The anchor is Theorem 1, proved in this paper by reduction from read-3 3-SAT. It says that, for each fixed \(k\ge2\), deciding whether any \(N\in\mathcal N_k\) entails every comparison in an input set \(P\) is NP-hard. The hardness holds even when each compared pair differs on at most two variables; it also holds with the stated positive-instance condition that whenever some CP-net entails \(P\), one in \(\mathcal N_2\) does. The reduction uses binary variables. The population problem inherits this hardness directly: replace each comparison in \(P\) with a type of mass \(1/|P|\). In the finite-population interpretation, repeat each type equally many times. Thus this mirror is expected to be Class B, with hardness transferring from the discrete comparison set.
The paper would have a good reason to recognize this question: it is the feasibility problem stated in Theorem 1 itself. I am mirroring that representability result, rather than claiming that the paper’s clean-target PAC setting has become a population problem. The paper’s conclusion also names imperfectly fitting data as a direction for future work, which makes population-level representability a plausible problem for its authors.
The scope is deliberately narrow: the mirror covers only whether one bounded-indegree CP-net can entail every observed comparison. It does not cover the paper’s soundness and completeness results, its restricted-input learning algorithm, or its PAC guarantees. Natural follow-ups include asking how well one can approximate the maximum entailed mass when exact agreement is impossible, and how the complexity changes with \(k\), \(\tau\), and \(L\).
The soft spot is that the mass values matter only through whether they are positive. A comparison with tiny positive mass is just as binding as one reported by half the population, and the reduction preserves the original discrete problem intact. There is also a modeling assumption: for a large population with heterogeneous or noisy preferences, a shared CP-net is a common explanation to test, rather than necessarily an individual user’s hidden target. So this is a credible continuous-population mirror, but its main result says the computational difficulty survives continuization.
The proposed mirror has one serious anchor, Theorem 1, but its population interpretation is the weak point. The paper learns one person’s conditional preference model from observations made in different situations. Those observations are not naturally different people. If the agents are respondents, a complete type should include their underlying preferences; the prompt they happened to receive is part of the data collection process. Treating each prompt and answer as a voter type instead turns a distribution over elicitation tasks into a distribution over people, and loses the connection between multiple answers from the same respondent.
For a homogeneous cohort with one shared target CP-net, exact fitting is either already guaranteed by the model assumption or reduces to the set of observed comparisons. In the latter case, the proposed mass objective at value \(1\) depends only on which comparisons have positive mass: it is precisely Theorem 1 applied to the support. Repeated reports change neither the constraint set nor the question. The paper’s PAC model already puts a distribution \(D\) over comparison situations, but its oracle assumes all observed orientations are entailed by one target network. That is a distribution over examples, not a continuous population of preference types.
A heterogeneous cohort is more genuinely population based, but then exact entailment asks whether everyone’s reports can be explained by one representative CP-net. That is a consensus or model-selection problem absent from the paper’s theorem. A more useful version might maximize
\[
\max_{N\in\mathcal N_k}\sum_{q:\,N\models o_q^+\succ o_q^-}\mu_q.
\]
Here the masses matter, but the objective needs a population-level interpretation: why should the representative network maximize the mass of entailed reports, rather than reflect pairwise majorities or account for respondents’ repeated answers? The paper’s future interest in imperfect data makes this a plausible extension, but does not supply that choice of objective.
So the strongest case against a continuous mirror is that Theorem 1’s exact-fit problem either remains a set-of-examples problem, with masses irrelevant, or becomes trivial under a shared realizable target; making mass consequential leads to a different aggregation problem. That defeats this anchor as a compelling continuization of the paper’s results. The negative case is not airtight, though: an explicitly motivated, population-weighted CP-net fitting problem could be worthwhile in its own right. I would call that a possible new research question, not a mirror established by this paper.
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.