| paper | d4-conf-ijcai-2018-0616 |
| 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{EXPTIME}\)-complete, hence \(\mathrm{NP}\)-hard; no algorithm polynomial in \(m,\tau,L\) exists. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Corollary 8
statement extracted from the paper’s text layer
Given a finite ALC agenda \(\Phi\) of \(m\) axioms, a finite support of \(\tau\) complete rankings \(\pi\) with binary-rational masses \(\mu_\pi\geq 0\) summing to \(1\), and a rational threshold vector \(\theta\in\mathbb{Q}^m\), decide whether there is a consistent subset \(S\subseteq\Phi\) such that \(q_r(S)=\sum_\pi\mu_\pi\mathbf{1}\{\text{the axiom ranked }r\text{ by }\pi\text{ belongs to }S\}\) is lexicographically greater than \(\theta\); the optimization version finds a lexicographically maximal consistent subset.
A society is a distribution \(\mu\) over complete axiom-ranking types, represented by its \(\tau\) positive-mass rankings and rational masses. The decision variable is a consistent agenda subset \(S\); its objective vector is the rankwise support mass \((q_1(S),\ldots,q_m(S))\), compared lexicographically with the input threshold.
Covers the reference-ontology selection problem and its complexity results, Theorem 7 and Corollary 8; it leaves the voting and turn-based weakening procedures, their axiomatic properties, and the happiness experiments unmirrored.
The strongest mirror is the reference-ontology problem, not either full aggregation procedure. Its continuous version asks how to choose a consistent set of axioms when the agents’ priorities are given by a distribution over preference types.
Call it Continuous Collective Best Consistent Ontology (C-CBC). An instance has a finite ALC agenda \(\Phi\) of \(m\) axioms; a finite support of \(\tau\) complete rankings of those axioms, with rational masses \(\mu_\pi\geq 0\) summing to \(1\); and a rational threshold vector \(\theta\in\mathbb{Q}^m\). For a candidate subontology \(S\subseteq\Phi\), define its rankwise support by
\[
q_r(S)=\sum_{\pi}\mu_\pi\,\mathbf{1}\{\text{the axiom ranked }r\text{ by }\pi\text{ belongs to }S\},
\qquad r=1,\ldots,m.
\]
The question is whether there is a consistent \(S\) whose vector \(q(S)\) is lexicographically greater than \(\theta\): at the first coordinate where they differ, \(q(S)\) must be larger. A yes-instance has a consistent \(S\) as its witness. The optimization version returns a lexicographically maximal consistent \(S\), allowing ties.
The lead anchor is Corollary 8, proved in this paper from its Theorem 7 and the relevant ontology-consistency complexity results. It states that the paper’s finite-profile optimal repair problem is EXPTIME-complete for ALC, and PSPACE-complete for ALC with acyclic TBoxes. In that problem, the input is an ontology \(T\), a profile \(\alpha\) of total rankings over its axioms, and a threshold \(m\)-tuple \(\theta\); it asks whether some consistent subontology \(S\subseteq T\) has \(S_\alpha<_{\mathrm{lex}}\theta\). In the paper’s convention, that comparison means that \(S_\alpha\) has a larger value at the first differing coordinate. Theorem 7, also proved here, gives the general upper bound: if ontology consistency is in a class \(\mathcal C\), optimal repair is in \(\mathrm{NP}^{\mathcal C}\).
This is a direct population mirror. Given any finite profile of \(k\) agents, put mass equal to the fraction of agents with each ranking, so that \(\mu_\pi\) is that ranking’s count divided by \(k\). Then \(q_r(S)\) is exactly the paper’s count \([r]^S_\alpha\), divided by \(k\). Dividing the threshold by \(k\) preserves the answer. Thus every finite-profile instance, including the hard ones, maps exactly to C-CBC. I expect hardness to transfer (Class B); the ALC and acyclic-TBox bounds should carry over. With binary rational masses, each \(q_r(S)\) can also be computed and compared exactly in polynomial time, so the paper’s certificate-based upper-bound reasoning has a natural continuous counterpart. A converse expansion of a rational distribution into an explicit voter list may be very large, so this is a high-multiplicity input representation, not necessarily a polynomial-size encoding in both directions.
A plausible regime is a large network of local health or data authorities jointly setting an ontology from a shared agenda. Many authorities may follow the same small set of standard governance templates, each template inducing a complete ranking of the agenda. For example, there could be thousands of authorities but only dozens of distinct ranking types. Here the “agents” are the authorities, and mass is the fraction of authorities using each ranking. The type records everything this problem uses from an agent: its priority ordering. The paper itself frames its agents broadly as voters, citizens, or experts, and its reference-ontology calculation uses those rankings directly. That makes this a recognizable version of the authors’ problem, rather than an easier surrogate.
The scope is deliberately narrow: C-CBC mirrors the computation of the reference ontology and Corollary 8. It does not claim to continuize the subsequent vote-repair or turn-based weakening mechanisms, or their happiness experiments. The outcome remains a finite set of axioms; the population is what becomes continuous. Nor is the mirror already present in the paper: its input is a finite profile, while C-CBC takes rational masses over types. The exact embedding makes the finite result a lower-bound anchor, not a reason to dismiss the continuous question.
The soft spot is that this mirror compresses the agents’ rankings but leaves the ontology-selection structure and ALC consistency difficulty intact. It is therefore a strong high-multiplicity analogue, but a modest illustration of new continuous-optimization machinery. The follow-on questions are whether the complexity changes when the support size \(\tau\) is bounded, how complexity depends jointly on agenda size, \(\tau\), and mass bit length, and whether the paper’s other results admit similarly direct mirrors.
The strongest negative case is that the proposed C-CBC is well-posed and has a plausible large-population setting, but the population contributes very little to the computation. A network of authorities using a small number of priority templates is credible, and treating each ranking as a type is faithful to the paper. I would not object that there is no multiplicity regime.
For any distribution over rankings, define \(P_{r,\varphi}\) as the mass of rankings that place axiom \(\varphi\) at rank \(r\). Then the score of a candidate ontology is just
\[
q_r(S)=\sum_{\varphi\in S}P_{r,\varphi}.
\]
The matrix \(P\) is doubly stochastic, and it contains everything C-CBC uses from the population. The distribution over ranking types can be replaced by this matrix. The task is therefore to choose a discrete, consistent subset of axioms using rational weights. It is weighted ontology repair, with a lexicographic objective.
That reduction identifies the limitation: no mass is being allocated or transferred, and there is no continuous decision variable. The hard choice remains which axioms to include; ALC consistency supplies the computational difficulty. The population affects the rational coefficients, but adding types or increasing their masses does not create a new optimization structure or bring the problem within reach of the continuous-optimization tools motivating ChoCo. C-CBC could be worth recording as a high-multiplicity weighted variant, but it is a thin case for the programme’s broader computational agenda.
A fuller mirror could put both each authority’s ranking and its submitted ontology into the type. That gives a sensible continuous version of the voting input, with mass determining each axiom’s support. It still leaves the paper’s repair procedures as ontology operations over a discrete agenda. The turn-based procedure raises a further modeling choice: a continuum of agents has no intrinsic turn order. Either way, the paper proves no separate complexity result for those procedures that would provide another computational anchor.
So Corollary 8 is the one serious anchor, and it survives the basic modeling objections. My case against it is about priority, not validity: its continuous population mostly compresses into a matrix of axiom weights, while the computation stays in discrete ontology consistency. That is a real but limited reason to decline it as a ChoCo target. The negative case is weak if the programme counts weighted high-multiplicity variants as worthwhile in their own right.
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.