| paper | d4-conf-ijcai-2005-0222 |
| 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: \(\Delta_2^p\)-complete; in particular, \(\mathrm{NP}\)-hard even when \(\tau=1\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 17
statement extracted from the paper’s text layer
Given propositional variables \(P\), a finite support \(T\) of consistent bases \(K_t\) with positive binary-rational masses \(\mu_t\) summing to \(1\), a consistent integrity formula \(\psi\), and a query \(\alpha\), define \(h_w(j)=\sum_{t:\,d_H(w,K_t)=j}\mu_t\) for each world \(w\models\psi\) and \(j=0,\ldots,|P|\), where \(d_H(w,K_t)\) is the minimum Hamming distance from \(w\) to a model of \(K_t\). Select the worlds whose vectors \((h_w(0),\ldots,h_w(|P|))\) are lexicographically maximal; decide whether every selected world satisfies \(\alpha\).
Types are consistent propositional bases, each carrying rational population mass; feasible outcomes are discrete worlds satisfying \(\psi\). A world’s objective is its mass histogram of distances to the types’ bases, maximized lexicographically from distance \(0\) upward, and the computational task is entailment of \(\alpha\) by the selected worlds.
The mirror covers Hamming-\(G_{\min}\) inference from Proposition 17; the relative-quota mirror also covers the inference hardness in Proposition 4. It does not continuize the paper’s logical postulates, strategy-proofness results, or other comparisons among merging operators.
The strongest mirror is a population version of the paper’s Hamming-\(G_{\min}\) merging problem. It fits the paper directly: the authors merge agents’ beliefs, and a large consultation on a fixed set of policy issues supplies a plausible high-multiplicity regime. Many participants submit the same standardized package of logical commitments, so the number of people \(n\) can be much larger than the number \(\tau\) of distinct packages. The package is the type; its mass \(\mu_t\) is its fraction of the population. Feasible policy choices remain discrete worlds, constrained by an integrity formula. Only the society becomes continuous.
Call the resulting question Continuous Hamming-\(G_{\min}\) Inference. An instance consists of issue variables \(P\), a finite support \(T\) of consistent bases \(K_t\), positive rational masses \(\mu_t\) summing to \(1\), a consistent integrity formula \(\psi\), and a query formula \(\alpha\). For a world \(w\), let \(d_H(w,K_t)\) be its minimum Hamming distance to any model of \(K_t\), and define
\[
h_w(j)=\sum_{t:\,d_H(w,K_t)=j}\mu_t \qquad (j=0,\ldots,|P|).
\]
The merged worlds are those satisfying \(\psi\) whose vector \((h_w(0),\ldots,h_w(|P|))\) is lexicographically maximum. This is the population form of minimizing the paper’s sorted, increasing list of distances: it first favors more mass at distance \(0\), then—among ties—more mass at distance \(1\), and so on. The question is whether every merged world satisfies \(\alpha\); the answer is yes or no.
The lead anchor is Proposition 17, proved in this paper: \(\mathrm{MERGE}(\triangle^{d_H,\mathrm{GMIN}})\) is \(\Delta^p_2\)-complete. In the paper’s problem, the input is a finite profile \(E\), integrity constraint \(\mu\), and query \(\alpha\), and the question is whether the Hamming-\(G_{\min}\) merged base entails \(\alpha\). The continuous question preserves that same inference task and distance objective while representing repeated bases by rational mass. Every finite profile embeds exactly: set \(\mu_K=\#\{i:K_i=K\}/n\). Its distance histogram is the discrete profile’s histogram divided by \(n\), so the selected worlds and the answer to the query are unchanged. I therefore expect hardness to transfer. A further question is whether support size \(\tau\) permits useful fixed-parameter or approximation algorithms despite that hardness.
A second, simpler mirror is Continuous Relative-Quota Inference. It has the same kinds of inputs, adds a rational threshold \(q\in[0,1]\), and selects worlds satisfying \(\psi\). If some such world satisfies every positive-mass base, the selected worlds are those satisfying all of them. Otherwise, select worlds \(w\) for which
\[
\sum_{t:\,w\models K_t}\mu_t\ge q.
\]
The decision question is again whether every selected world satisfies \(\alpha\). Here the collective criterion is the share of society whose bases a world satisfies.
Its anchor is Proposition 4, also proved in this paper: the paper’s \(k\)-quota inference problem is \(\mathrm{BH}(2)\)-complete, even when the query is a propositional symbol and there are no integrity constraints. The underlying problem asks whether \(\triangle^k_\mu(E)\models\alpha\) for a finite profile \(E\), quota \(k\), integrity constraint \(\mu\), and query \(\alpha\). The continuous threshold version contains that case: give each of the \(n\) agents mass \(1/n\) and set \(q=k/n\). Thus I expect hardness to transfer here too. The next question is whether binary-encoded rational masses and small support yield algorithms that improve on the explicit-profile bound. The paper’s relative-quota discussion is useful prior art: a percentage threshold is already studied, but the profile still lists individual agents. Weighted support makes the population itself the input object.
Both questions have the kind of high-multiplicity interpretation this programme calls for. Agents sharing a base are indistinguishable for these inference problems; the formulas, distance rule, and integrity constraint apply equally to them. A repeated, standardized policy questionnaire can have millions of respondents but far fewer distinct response packages. The authors should recognize these as their merging problems with the finite profile replaced by its type distribution—not as a change to outcome continuity, nor as an axiomatic question.
The weak point is that this is a regime-specific case. Unstandardized belief bases may be mostly unique, so \(\tau\) can approach \(n\), and the formulas may retain hard reasoning problems even when \(\tau\) is small. The mirrors establish well-posed continuous-population questions and preserve the paper’s hardness; they do not by themselves promise that continuization makes either problem easier.
The strongest objection to Proposition 17 is that the proposed Hamming-\(G_{\min}\) mirror creates no new limiting behavior. Distances take only finitely many integer values, so a rational mass distribution is summarized by a finite histogram. Any such distribution can also be expanded into a finite profile by taking a common denominator. The continuous problem is therefore an exact, potentially succinct encoding of the paper’s inference problem, with the hard propositional reasoning still present. That makes the mirror less revealing about what a continuum changes.
But this does not dispose of the computational question. The expansion can be exponentially larger than the binary-encoded masses, and studying algorithms in support size and bit length is exactly the kind of high-multiplicity question the programme targets. The survey scenario is also credible: for a fixed questionnaire, many respondents can submit the same complete package, and the paper’s inference task treats identical bases identically. I cannot make the encoding objection rule out a worthwhile mirror.
Proposition 4 offers a closer case against. The paper already studies relative quotas, so a continuous share threshold is not a new aggregation idea. The best version of the mirror would use nonuniform rational masses and ask about inference with a weighted support. Again, every rational instance can be expanded into an ordinary profile, but that expansion may be enormous; the paper’s equal-weight relative quota result does not settle the complexity of the compressed weighted input. The observation narrows the novelty claim, but it does not defeat the anchor.
So the negative case is weak. Both mirrors are well-posed population versions of named computational results, and the proposed types have a plausible high-multiplicity interpretation. Their exact reducibility to expanded profiles is a reason to describe them carefully as high-multiplicity or succinct-input questions; under ChoCo’s stated aims, it is not a reason to dismiss them. I cannot honestly support the universal claim that no worthwhile continuous mirror exists.
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.