| paper | d4-conf-ijcai-2017-0319 |
| 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: \(\Delta_2^{\mathrm P}\)-complete for every fixed positive \(k\); in particular, \(\mathrm{NP}\)-hard. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given a shared ontology \(O\), a conjunctive query \(q(x)\), fixed \(k\), a proposed answer tuple \(A\), and a distribution \(\mu\) over a finite support \(\mathcal{T}\) of complete user preference rankings \(P_t\), decide whether \(\sum_{t \in \mathcal{T}: A\text{ is a top-}k\text{ answer under }(P_t,O)} \mu_t \ge \eta\), for a rational target share \(\eta\). Use the paper's top-\(k\) definition, including its treatment of ties; each ranking is given in a permitted polynomial-time-computable representation.
Users with the same complete ranking over the ontology's contexts form a type \(t\), with population mass \(\mu_t\) and \(\sum_t \mu_t=1\). For each type, set \(z_t=1\) exactly when \(A\) is a top-\(k\) answer under \((P_t,O)\); ask whether the served mass \(\sum_t \mu_t z_t\) reaches \(\eta\).
The population calculation decomposes into τ separate validation calls plus rational arithmetic, so it adds a cohort coverage measure without creating shared computational structure across users.
fatal: False
The mirror covers Theorem 5's top-\(k\) validation and, analogously, Theorem 3's \(p\)-entailment threshold. It leaves the paper's conditional-answer and most-preferred-world tasks, as well as its semantic characterization results, unmirrored.
The strongest mirror is for the paper’s query-answering tasks in a service with many users and a small set of recurring preference profiles. Think of a travel site answering the same query over one shared ontology for millions of users. One user type is their complete preference ranking over the ontology’s contexts, represented in the paper’s permitted way—for example, by a possibilistic network. Users of a type are identical for this task; if there are \(N\) users and \(n_t\) have type \(t\), the society is \(\mu_t=n_t/N\). A plausible regime is millions of users but tens or hundreds of distinct preference profiles.
This scenario fits the paper’s own account of different users supplying different rankings over the same contexts. The population is continuous; the contexts and each user’s preference ranking are not. In particular, \(\mu_t\) measures people, not uncertainty about worlds.
My lead is population top-\(k\) validation mass, mirroring Theorem 5, proved in this paper. Its relevant result is: given a candidate tuple \(A=(\theta_1,\ldots,\theta_k)\) of answers to a CQ \(q(x)\) under a ranked ontology \(K\), deciding whether \(A\) is a top-\(k\) answer is in \(C_d\), \(C_k\), and \((\Delta_2^P)^{C_c}\) in data, KB, and combined complexity, respectively, when \(C_d\) contains P; it is \(\Delta_2^P\)-complete in ranking complexity. If \(C_c\subseteq NP\), it is also \(\Delta_2^P\)-complete in combined complexity. For EL, the problem is in P in data and KB complexity and \(\Delta_2^P\)-complete in ranking and combined complexity. The paper’s hardness route uses its Theorem 4, whose reduction draws on a result of Krentel.
Here is the population problem. The input is a shared \(V\)-ontology \(O\), a CQ \(q(x)\), fixed \(k\), a proposed answer tuple \(A\), and a finite support of preference types \(t\), each with a polynomial-time-computable ranking \(P_t\) and rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). Each type induces the ranked ontology \(K_t=(P_t,O)\). For a rational target share \(\eta\), decide whether
\[ \sum_{t:\,A\text{ is a top-}k\text{ answer to }q(x)\text{ under }K_t}\mu_t\ \ge\ \eta. \]
The solution is yes or no, optionally accompanied by the supporting types. For each type, “is a top-\(k\) answer” uses the paper’s definition, including its treatment of ties. This asks whether a proposed shared recommendation list is valid for at least an \(\eta\) fraction of the population. With \(\mu_t=1\) for one type and \(\eta=1\), it is exactly Theorem 5’s problem. I expect hardness to transfer in that one-type case; the ranking input, rather than population multiplicity, carries the known hardness. In the useful restricted regime of a fixed menu of rankings and EL data or KB complexity, the paper’s polynomial bounds apply per type, and the mass aggregation takes polynomial time in the support size and input bit length.
A second, narrower mirror is population \(p\)-entailment mass, anchored in Theorem 3, also proved in this paper. For an arbitrary fixed DL \(L\), that theorem puts \(p\)-entailment in \(C_d\), \(C_k\), and \(NP^{C_c}\) in data, KB, and combined complexity; it is NP-complete in ranking complexity, and also in combined complexity when \(C_c\subseteq NP\). In EL, it is in P in data and KB complexity and NP-complete in ranking and combined complexity.
For this mirror, the input is a shared \(V\)-ontology \(O\), BCQ \(q\), threshold \(p\in(0,1]\), the same kind of rational type distribution, and a target share \(\eta\). Decide whether
\[ \sum_{t:\,\operatorname{rank}_{(P_t,O)}(q)\ge p}\mu_t\ \ge\ \eta. \]
Again, the answer is yes or no, with the qualifying types as a certificate. A single type with \(\eta=1\) recovers the paper’s \(p\)-entailment problem, so I would expect hardness to carry over there too. With a fixed finite menu of rankings, EL’s data and KB tractability gives a polynomial-time population calculation.
The scope is these two ranked-ontology query tasks. This does not continuize the answer space or turn the paper’s possibility ranks into probabilities; it makes the user population the distributed object. The soft spot is that the paper studies answering for a user, while these mirrors ask a population-level coverage question. The authors’ explicit motivation of supporting different users makes batch evaluation of their rankings plausible, but the population threshold is an added service-level question. And although the mirrors are well-posed, their one-type cases show that continuization need not remove the paper’s ranking-complexity hardness.
Theorem 5 and Theorem 3 are genuine computational results, so the case against cannot rest on the paper lacking something to mirror. The weakness is that the proposed population questions add an outer count to tasks the paper defines for one preference ranking at a time.
For Theorem 5, let \(I_t(A)\) indicate whether \(A\) is a top-\(k\) answer under type \(t\). The proposed task computes \(\sum_t \mu_t I_t(A)\). For Theorem 3, it does the same with the indicator that \(\operatorname{rank}_{(P_t,O)}(q)\ge p\). In either case, solve the paper’s problem separately for each supported ranking, then add the masses. The running time is the sum of the per-type running times plus the cost of rational arithmetic. The number of people \(N\) vanishes; only the number of distinct rankings \(\tau\) matters.
That is not an objection that the continuous answer might be easy or hard. It is a concern about what is being continuized: the paper’s input is one ranked ontology, not a society of users whose outputs interact. A large cohort with the same ranking can be compressed to one weighted type, but the population computation gains no structure beyond that compression. With a fixed menu of rankings, the paper’s tractable cases remain tractable type by type; when ranking complexity is hard, the hard work also remains inside those individual calls. The population threshold organizes a batch of instances, rather than exposing a new continuous optimization problem.
The stronger version of the Theorem 5 mirror would choose a single answer list maximizing the mass of users it serves. That is a plausible product question, but it changes the task: the paper is designed to give each user answers under that user’s own ranking. A common list requires a new collective objective—such as exact agreement with each user’s top-\(k\), or acceptance of any answer from it—and a policy for resolving ties. Averaging the rank values would not supply a neutral objective: they are degrees within different preference rankings, not an established common utility scale. This could be a worthwhile collective recommendation problem, but its central question is how to aggregate users’ preferences, not the paper’s query-answering question over a continuous society.
Theorem 3’s population version has the same issue. It counts users whose individual preference degree for a query clears \(p\); it does not make the ontology’s worlds or contexts into population mass. Those remain part of each user’s ranked-ontology calculation. Nor does the threshold aggregate the degrees across users: it aggregates only the yes/no outcomes of the original decision problem.
The proposed user-profile scenario is credible, and measuring what fraction of users a recommendation serves could be useful. That makes this a weak negative case rather than a decisive one. But the strongest anchors still appear to be weighted batch evaluation; the more ambitious version that creates cross-user computational structure shifts to a new preference-aggregation problem. I would not call either a strong continuous mirror of the paper’s stated computational results.
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.