| paper | d4-conf-ijcai-2016-0442 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard: a polynomial-time constructor exists if and only if \(\mathrm{P}=\mathrm{NP}\). For satisfiable inputs, a polynomial-time construction exists with \(\tau=1\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 10
statement extracted from the paper’s text layer
Given a target knowledge base \(K\) over a finite vocabulary \(U\), can one construct a finitely supported rational distribution \(\nu\) over \(2\mathrm{CNF}\) knowledge-base types, allowing fresh auxiliary atoms, and a \(2\mathrm{CNF}\) integrity constraint \(\mu\), such that the interpretations minimizing \(\sum_t \nu_t \min_{\omega'\models K_t} d_H(\omega,\omega')\) among models of \(\mu\) project onto \(U\) as exactly \(\operatorname{Mod}(K)\)?
Types are complete \(2\mathrm{CNF}\) knowledge bases held by agents, with rational population masses \(\nu_t\). The merge minimizes the mass-weighted sum of each type’s nearest-model Hamming distance, subject to a \(2\mathrm{CNF}\) integrity constraint; fresh auxiliary atoms are allowed, and the merged models must project onto the target vocabulary as \(\operatorname{Mod}(K)\).
Theorem 10’s witness uses only one knowledge-base type, so it does not establish a multiplicity-dependent result; requiring several positive-mass types would create an additional question.
fatal: False
The mirror covers Theorem 10’s universal \(2\mathrm{CNF}\) simpliability result. It leaves the paper’s \(1\mathrm{CNF}\) and Horn characterizations, drastic-distance results, partial distributability results, and profile-size questions unmirrored.
The paper has no named computational complexity result of the kind your anchor rule requires. Its numbered theorems and propositions establish representability and characterization results; the complexity discussion in the introduction cites earlier work. So I cannot honestly give a continuous prover question *per eligible anchor*.
The closest positive seed is Theorem 10, proved here: for every knowledge base \(K\), there is a single \(2\mathrm{CNF}\) knowledge base \(K'\) and a \(2\mathrm{CNF}\) integrity constraint \(\mu\) such that Hamming-distance merging yields \(\Delta^H_\mu(K')\equiv K\). The construction may add new atoms. This is a strong result about simplifying the representation of knowledge, but it does not classify the complexity of a problem.
One could imagine a related continuous question about reconstructing a target knowledge base from a distribution of simple knowledge bases held by many data-storage agents. That gives a possible population story, but it changes the paper’s single-base simplifiability result into a weighted-profile problem. Theorem 10 does not establish an algorithmic or hardness anchor for that problem, and a one-base construction would not itself make multiplicity matter.
That is the soft spot, and here it defeats the positive case: the paper studies whether reconstruction is possible, not computational questions about a continuous population.
The strongest case against a mirror is a mismatch with the programme’s computational aim. The paper’s theorems and propositions establish representability: whether a base can be reconstructed by merging bases from a fragment. They do not classify the complexity of a computational problem. The complexity discussion in the introduction cites earlier work; it is not a result of this paper. So there is no named computational theorem here to mirror.
The best seed is Theorem 10: every knowledge base \(K\) can be reconstructed from a single \(2\mathrm{CNF}\) base using Hamming-distance revision. But its central object is not a population. The construction uses new propositional atoms to distinguish models of \(K\); the number of those atoms tracks the number of models, not the number of agents. Treating those models or auxiliary atoms as a continuum would change the wrong part of the problem.
A stronger population version is possible. Imagine many storage devices, each holding a simple knowledge base, and let type \(t\) have population mass \(\nu_t\). Define the aggregate Hamming cost of an interpretation \(\omega\) as \(F_\nu(\omega)=\sum_t \nu_t H(\omega,K_t)\), and ask whether the resulting merge recovers \(K\). That is a coherent weighted-profile question, and the storage scenario is plausible. But for Theorem 10, the paper’s single-base construction already answers the unrestricted existence question: put all mass on that one \(2\mathrm{CNF}\) type. Requiring multiple types, a fixed catalogue, or a support bound could make the problem nontrivial, but those restrictions create a new computational problem rather than continuize the theorem’s result. The paper itself identifies profile size and construction complexity as future questions; a mass-weighted version would extend that agenda, not supply a continuous mirror of an established complexity result.
The same issue applies to the paper’s other results: they characterize which knowledge bases are expressible or distributable, rather than giving computational classifications. Their statements could motivate new algorithmic questions about weighted profiles, but those questions would need to be formulated and justified as new work.
So I would argue against prioritizing this paper as a ChoCo mirror. The case is strongest on scope, not on the claim that no sensible population can be imagined. If the programme welcomes computational questions about collective epistemic aggregation, weighted populations of knowledge holders could be worth studying; that is the clearest weakness in the negative case.
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.