| paper | d4-conf-ecai-2014-0305 |
| 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}\), even with one type and an empty evidence profile; more strongly, \(\#\mathrm{P}\text{-hard}\) under polynomial-time reductions recovering a counting answer from one exact probability. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite object set \(H\), a query \(Q\), and supported preference-evidence profiles \(P_t\) with binary-rational masses \(\mu_t\) summing to \(1\), compute the exact expected fraction of the population whose sampled ranking satisfies \(Q\): \(\operatorname{Prev}_{\mu}(Q)=\sum_t\mu_t\frac{\sum_{\lambda\models Q}\exp(s_t(\lambda))}{\sum_{\lambda\in W}\exp(s_t(\lambda))}\), where \(s_t(\lambda)=\sum_{(F,w)\in P_t}w\,\mathbf{1}[\lambda\models F]\).
A continuous society is a distribution \(\mu\) over complete preference-evidence profiles \(P_t\); each person of type \(t\) has the paper's PPLN distribution over rankings, and the objective is the population-mass-weighted probability of query satisfaction.
The prevalence statistic separates across types, so the continuous population adds no interaction or optimization structure and can be computed with at most calls to the original inference task.
fatal: False
It lifts Theorem 1's query-probability problem to group prevalence; Theorem 2's world-probability problem and Theorems 6–8's approximation and exact algorithms are not separately claimed.
My lead is Continuous PPLN Query Prevalence. Consider a platform with many users comparing items from a common finite set \(H\). A user’s type is their complete PPLN evidence profile \(P_t\): the same weighted preference statements over \(H\). This is plausible when a large service uses standardized preference prompts and many users fall into a relatively small number \(\tau\) of recurring profiles. The society is a distribution \(\mu\) over those profiles, with binary rational masses summing to \(1\).
Fix a query \(Q\), such as whether users prefer item \(a\) to item \(b\). For each profile, let \(s_t(\lambda)=\sum_{(F,w)\in P_t} w\,\mathbf 1[\lambda\models F]\), where \(\lambda\) is a possible ranking of \(H\). The problem is to compute the expected fraction of the society whose ranking satisfies \(Q\):
\[ \operatorname{Prev}_{\mu}(Q) =\sum_t \mu_t \frac{\sum_{\lambda\models Q}\exp(s_t(\lambda))} {\sum_{\lambda\in W}\exp(s_t(\lambda))}. \]
The answer is this exact scalar, under the same exact-probability convention as the paper. There is no control action or optimization objective: the question is how much population mass is expected to satisfy the preference query. The type-level answer can be fractional even though each person’s ranking either satisfies \(Q\) or does not.
The anchor is Theorem 1, proved in this paper. It states that, given a PPLN \(P\) and a preference statement \(S\), computing \(\Pr(S)\) is \(\#\mathrm{P}\)-hard. The proof reduces from \(\#3\mathrm{SAT}\): for a formula on \(n\) variables, it builds a PPLN over \(2n\) atoms with the single weighted statement \((S,1)\), where \(S\) encodes the clauses using pairwise preferences between each variable atom and its negation. The worlds satisfying \(S\) correspond to satisfying assignments; their number determines \(\Pr(S)\). This is a computational inference result about the probability of a query, not a hardness claim about the MRF encoding.
The continuous version has an exact high-multiplicity dictionary. A discrete cohort with \(N\) users and \(n_t\) users of profile \(t\) has \(\mu_t=n_t/N\), and its expected query-satisfying fraction is exactly \(\operatorname{Prev}_{\mu}(Q)\). Conversely, any binary-rational mass vector can be represented by counts after taking a common denominator. The number of distinct supported profiles is \(\tau\), which may be much smaller than \(N\).
I expect hardness transfers. Setting \(\tau=1\), \(\mu_t=1\), and \(Q=S\) gives precisely Theorem 1’s problem. The reduction’s combinatorics live in the object set and the preference statement, not in population multiplicity, so this continuum does not wash away the hardness. This mirror covers Theorem 1’s query-probability result; it does not claim that the paper’s probability distribution over rankings is itself a continuous society, or that the paper’s other results have automatically been continuized.
The weakest point is that the paper computes uncertainty for an entity’s ranking, while this mirror adds a population layer and aggregates many such inferences. The authors do explicitly motivate preferences for “a group of people whose choices are of interest,” which makes the cohort question a plausible extension of their problem. Still, the hardness result survives here because the continuous population can consist of a single profile type. Further questions include whether the paper’s approximation methods can estimate this aggregate efficiently as \(\tau\) grows, and how to exploit repeated or equivalent profiles without solving each one separately.
The strongest objection is that the population lift is almost entirely an outer averaging step. For profile types \(P_t\), the proposed quantity is
\[
\operatorname{Prev}_{\mu}(Q)=\sum_t\mu_t\,p(P_t,Q),
\]
where each \(p(P_t,Q)\) is precisely the query probability computed by the paper. The masses create no interaction between profiles, no population constraint, and no new inference problem: evaluate the existing query once per supported type, then take a weighted sum. The discrete counterpart is the same calculation over a finite cohort. Its cost is \(\tau\) calls to the original inference task, and its hardness follows immediately from \(\tau=1\). That gives a valid population statistic, but little new complexity landscape for ChoCo to chart.
The more collective version has the same limitation. Suppose users’ rankings are sampled from their type’s PPLN and we ask what fraction satisfy \(Q\). In the continuum, that fraction is the displayed weighted average. If we ask whether a majority satisfies \(Q\), the answer is just whether that average crosses \(1/2\). A nontrivial probability of a majority requires finite-population fluctuations, which brings population size back into the question. Pooling all users’ evidence into one PPLN instead asks about a single aggregate ranking; it changes the object being modeled and still leaves the paper’s query inference as the computational core.
These points do not make the proposed statistic incoherent. The paper explicitly mentions groups whose choices are of interest, and a platform could plausibly have many users with recurring evidence profiles. That is the weak point in the negative case: the group setting is credible, and the query is computational. The case against is about value to this programme. The anchor appears to add a batch expectation around an existing inference problem, with no population-dependent structure for continuous optimization to exploit. If ChoCo counts that kind of wrapper as a worthwhile mirror, Theorem 1 survives; I cannot honestly rule it out in every scenario.
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.