| paper | d4-conf-ijcai-2015-0055 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions, hence \(\mathrm{NP}\)-hard under polynomial-time Turing reductions, for every fixed allowed operation \(\oplus\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite HCLP structure, a query \(\alpha\le\beta\), a rational threshold \(q\), a support bound \(\tau\), and strata \(j\) with rational masses \(w_j\) summing to one and input statements \(\Gamma_j\), consider allocations \(x_{j,H}\ge0\) of each stratum’s mass to HCLP types \(H\in\mathcal C(2)\) satisfying \(\Gamma_j\), with at most \(\tau\) distinct types used overall. Is the minimum, over all such compatible allocations, of \(\sum_{j,H:\,H\models^\oplus\alpha\le\beta}x_{j,H}\) at least \(q\)?
A type is an HCLP hierarchy \(H\in\mathcal C(2)\), and \(x_{j,H}\) is the mass of stratum \(j\) assigned to it. Minimize the total mass on types satisfying \(\alpha\le\beta\), subject to each stratum’s mass and elicited statements and the overall support bound \(\tau\).
The coNP-hardness witness fixes half the mass on an indifferent type, so it demonstrates inherited hardness without showing what richer cohort constraints add to the classification.
fatal: False
Covers Theorem 1’s coNP-complete deduction case for \(t=2\) through a population share-threshold question; leaves its polynomial cases for \(t=1\) and fixed equivalence classes, and the paper’s consistency algorithm, outside the mirror.
Lead mirror: Robust Population HCLP Inference. A type is an HCLP model \(H\): an ordered partition of the evaluations, with each level containing at most two evaluations. It determines a user’s complete preference relation over the alternatives. A recommender platform with a very large user base can have many users but relatively few such preference types; the mass of a type is the fraction of users with that hierarchy. The alternatives and evaluations remain exactly those in the paper.
The instance describes a family of societies consistent with incomplete preference data. Each society is a distribution over HCLP types, represented by its support and rational masses, with support bounded by \(\tau\). The data specify population strata and, for each stratum, the pairwise statements its members must satisfy; more general versions could give observed bounds on the fraction satisfying each statement. Given a query \(\alpha\le\beta\) and rational threshold \(q\), ask whether every society consistent with the data has at least \(q\) of its total mass on types \(H\) for which \(H\models^\oplus\alpha\le\beta\). A no answer has a concrete witness: a compatible support list and masses with query share below \(q\).
This is a population-level version of the paper’s inference task: use incomplete pairwise preference information to infer whether a comparison holds, now asking what share of a society must hold it. In a large user base, preference hierarchies can repeat across many users, and aggregate survey reports can constrain their proportions. The underlying preference model stays intact; population mass makes the inferred claim useful at society scale.
The anchor is Theorem 1, proved in this paper. In full, it states that HCLP-DEDUCTION for \(\models^\oplus_{\mathcal C(t)}\) is polynomial when \(t=1\), and coNP-complete for any \(t>1\), even when restricted to non-strict preference statements; HCLP-DEDUCTION for \(\models^\oplus_{\mathcal C(\equiv)}\) is polynomial for any equivalence relation \(\equiv\). I rely on its coNP-completeness result for \(t=2\), with non-strict inputs.
The population problem inherits that hardness even with support at most two. Give half the population a known empty HCLP model \(H_0\), and let the other half come from models satisfying the input statements \(\Gamma\). Since the anchor uses non-strict statements, \(H_0\) satisfies both \(\Gamma\) and the non-strict query \(\alpha\le\beta\). Set \(q=3/4\). If \(\Gamma\models^\oplus_{\mathcal C(2)}\alpha\le\beta\), every compatible society meets the threshold. If not, a model \(H^\star\) satisfies \(\Gamma\) but violates the query; assigning the other half of the population to \(H^\star\) gives query share \(1/2\), below threshold. Thus the mirror is hard for reasons already present in the model-inference problem: hardness transfers (Class B). The population size can be arbitrarily large while the witness society has only two types.
The paper’s scope covered here is its inference problem for bounded-size equal-importance levels. I would expect tractable cases when the permitted hierarchies have the paper’s total-order or fixed-equivalence structure, but aggregate share constraints may change that; the broader population problem needs its own classification. Further questions include how complexity changes with \(q\), \(\tau\), and fractional survey bounds, and whether optimization over compatible type distributions admits efficient algorithms.
The weak point is that Wilson, George, and O’Sullivan study one user’s unknown hierarchy, not a distribution of users’ hierarchies. The mirror adds aggregate population inference, and the hardness reduction uses a particularly clean two-type construction. A referee could reasonably ask for evidence that fractional survey data lead to useful new algorithms or classifications. Still, the proposed question keeps their HCLP models, elicited comparisons, and deduction target; it makes the population the continuous object and asks what can be inferred about the society’s preference mass.
The strongest case against this anchor is that it changes the inferential object. Theorem 1 concerns one user: given that user’s elicited comparisons \(\Gamma\), does every compatible HCLP model entail \(\alpha\le\beta\)? The proposed mirror asks what fraction of a cohort must prefer \(\alpha\) to \(\beta\). A lower bound on that fraction cannot answer what a particular user prefers, which is the paper’s stated recommender use case.
The half-and-half construction makes the gap especially visible. The known indifferent group supplies a fixed \(1/2\) share, while the other group repeats the original one-user deduction question. The threshold \(q=3/4\) turns a single countermodel into a population-level no-answer. That proves hardness for the constructed population problem, but the population composition itself contributes no inference beyond the original entailment test. It is a warning that this particular reduction may be a wrapper around the theorem, not evidence of a distinctive population problem.
That objection does not defeat the better mirror, though. A platform could have many users with the same elicitation record, or cohorts with different records and observed bounds on their proportions. Treat each user’s complete HCLP preference relation as a type, give the types rational masses, and ask for the smallest compatible share that prefers one alternative to another. That is a coherent high-multiplicity question, and it makes mass the quantity of interest. The paper’s individual-user framing does not establish that its authors would reject this extension, especially given its recommender-system motivation.
Nor can I dismiss the anchor as already done or as lacking a named computational result: Theorem 1 explicitly classifies HCLP deduction, including coNP-completeness for levels of size two. The population question is not already continuous in the paper. Its exact reduction may be thin, but richer cohort constraints could make the population composition central and open a real classification problem.
So the negative case is weak at its decisive point. The theorem survives the proposed mirror, and I cannot honestly rule out a worthwhile continuous version 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.