d4-conf-aaai-2006-0015

The strongest mirror is for the paper’s inference problem for merging: treat knowledge sources as the population. A source’s type is its complete stratified knowledge base together with its ordering strategy. Two sources share a type only when the problem treats them identically. The mass \(\lambda_t\) of type \(t\) is the fraction of sources using it. This fits, for example, a large federation of policy or diagnostic units using a small library of ranked knowledge templates: millions of units, perhaps dozens of distinct types.

The anchor is Proposition 8, proved by the authors, with its proof deferred to their accompanying technical report. It states that deciding whether \(\Delta_{\mathrm{PLMIN},\mu}^{X}(E)\models\psi\) is in \(\Theta_2^p\); when the ordering strategies are best-out, maxsat, or leximin, the decision problem is \(\Theta_2^p\)-complete. The paper assumes the world rankings induced by each knowledge base have been computed in an offline preprocessing stage. The decision is whether every model selected by merging the profile \(E\) subject to integrity constraint \(\mu\) satisfies query \(\psi\).

Here is a continuous version that keeps that decision intact. Call it Continuous PLMIN Entailment. An instance consists of a finite propositional language, a finite support \(T\) of types \(t=(K_t,X_t)\), positive rational masses \(\lambda_t\) summing to \(1\), a satisfiable integrity constraint \(\kappa\), and a query \(\psi\). For each world \(w\), let \(\ell_t(w)\) be its priority level under type \(t\)’s ordering strategy. Let \(R\) be the largest level, and define
\[ F_w(j)=\sum_{t\in T:\,\ell_t(w)\le j}\lambda_t,\qquad j=1,\ldots,R-1. \]
Among worlds satisfying \(\kappa\), select those that lexicographically maximize \((F_w(1),\ldots,F_w(R-1))\): at the first priority level where two worlds differ, prefer the one with more mass at that level or better. The question is whether every selected world satisfies \(\psi\); a solution is yes or no.

This is the population form of PLMIN’s lexicographic comparison of sources’ priority levels. It preserves the paper’s substantive question: which admissible interpretations best reconcile the ranked knowledge of a group of sources? It is not a continuous outcome space or a probability model over discrete profiles. When \(\lambda_t\) is the fraction of sources of each type in a finite profile, the rank histogram gives the same comparison as the profile’s multiset of priority levels. Thus the continuous question has a direct bridge back to the paper’s problem.

I expect hardness to transfer. Given a finite profile of \(n\) sources, assign each distinct type mass equal to its count divided by \(n\). The resulting continuous instance reproduces the original merging decision, so Proposition 8’s \(\Theta_2^p\)-hardness carries over. Under the same offline-stratification assumption, I would expect the continuous problem to remain \(\Theta_2^p\)-complete: it compares polynomial-length rational rank histograms while optimizing over worlds. This is a Class B mirror, not a claim that continuization makes this result tractable. It also raises follow-up questions about parameterized complexity in support size \(\tau\) and number of atoms \(m\), and about algorithms that exploit a small number of source types.

The mirror covers Proposition 8’s inference result, not the paper’s logical postulates or every computational question about merging. Its weakest point is the regime: many knowledge sources may be less naturally understood as a population than voters are, and the paper itself studies profiles of sources without assigning them population masses. But the masses here encode cohort proportions of otherwise identical sources, and the discrete problem already counts repeated bases in a multiset. That makes the continuous profile a plausible high-multiplicity version of the authors’ own model, rather than a simplified substitute for it.