| paper | d4-conf-aaai-2017-0587 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The named results have computational character: Corollary 1 gives a compilability completeness result, and Proposition 1 supplies the query-equivalent encodings used for computation. But the proposed Hamming–\(\Sigma\) population objective is exactly the paper's weighted-profile objective after normalizing integer multiplicities, with rational masses converted back by clearing denominators. The paper already covers this model, so the candidate fails as a continuous mirror under b-already.
fails bit b-already — the paper is already native to the continuum
Normalizing the paper's integer weighted profiles yields the proposed rational-mass inference problem exactly.
fatal: True
The candidate covers weighted-Hamming, \(\Sigma\) inference from Corollary 1, with Proposition 1's encoding result; the paper also covers other distances and aggregators that this candidate leaves aside.
The strongest positive mirror is continuous Hamming–sum belief-merging inference. My lead anchor is Corollary 1, stated and derived in this paper from Proposition 1 using the compilability framework cited from Liberatore (1998). It says that, for every weighted drastic or weighted Hamming distance \(d^w\), and every aggregator \(f\in\{\Sigma,\mathrm{GMax},\mathrm{GMin}\}\), inference for \(\Delta^{d^w,f}\) is \(\mathrm{compcoNP}\)-complete: after polynomial-size preprocessing independent of the query, inference reduces to a coNP problem. The supporting Proposition 1 gives the route to that result: for each such distance and aggregator, there is a polynomial-size CNF formula query-equivalent to the merged base. This does not promise that the preprocessing itself runs in polynomial time.
Here is the continuous problem I would hand to a prover. An instance has a finite issue set \(P\), a consistent integrity constraint \(\kappa\), a query \(q\) over \(P\), and a distribution \(\rho\) over \(\tau\) belief types. Each type \(t\) is a consistent CNF belief base \(\varphi_t\), and its positive rational mass \(\rho_t\) is given in binary, with \(\sum_t\rho_t=1\). The instance also gives the variable weights \(w\) used by the weighted Hamming distance. For each world \(\omega\models\kappa\), define its population-average distance from the reported beliefs by
\[
F_\rho(\omega)=\sum_{t=1}^{\tau}\rho_t
\min_{\nu\models\varphi_t}
\sum_{x\in P}w(x)\mathbf{1}[\omega(x)\ne\nu(x)].
\]
The task is to decide whether \(q\) holds in every world minimizing \(F_\rho\) subject to \(\kappa\). A no-instance has an optimal feasible world falsifying \(q\) as a witness. This asks about the underlying group decision—what follows from the best feasible merged beliefs—not about constructing a SAT encoding.
The regime is natural in the paper’s own timetabling application. Treat each curriculum’s soft-constraint base as a type; students following that curriculum share the same preferences and distance weights; and their share of enrolments is the type’s mass. A large university system could have thousands of students but only tens of distinct curriculum types. The paper already weights curriculum bases by median student counts, so this is a setting its authors should recognize as their problem, expressed in population proportions.
For \(\Sigma\), the bridge is exact: if \(k_t\) individuals have type \(t\) in a finite society of size \(N\), set \(\rho_t=k_t/N\). Then \(F_\rho\) is the discrete sum-distance objective divided by \(N\), which leaves its minimizers unchanged. Conversely, binary rational masses can be multiplied by a common denominator to obtain integer multiplicities with polynomial encoding length. I therefore expect the continuous inference problem to retain the paper’s \(\mathrm{compcoNP}\)-completeness under binary rational input. In the programme’s terms, this is on the hardness-transfer side: the relevant combinatorics lie in the issue space and belief formulas, not in the granularity of individual population units.
This mirror covers the weighted-Hamming, \(\Sigma\) inference case of Corollary 1 and its query-preprocessing result. I would leave GMax and GMin outside this proposal: defining their lexicographic comparison over a continuum of distances needs additional care. The mirror also raises parameterized questions, such as whether preprocessing becomes efficient for small \(\tau\) or for formulas with bounded structural width.
The weak point is that integer-weighted profiles already compress repeated belief bases, so the continuous formulation may inherit the answer without changing the complexity landscape. That limits the novelty of this particular mirror, but strengthens the case that the population regime is a sensible one: the paper’s own application already describes agents through a small set of shared types and their multiplicities.
The strongest objection is a narrow collision: the proposed Hamming–sum mirror is already inside the paper’s weighted-profile model. A weighted base \(\varphi_t(k_t)\) means \(k_t\) copies of that base. Given rational masses \(\rho_t\), choose a common denominator \(D\) and set \(k_t=D\rho_t\). Then, for every feasible world \(\omega\),
\[ F_\rho(\omega)=\frac{1}{D}\sum_t k_t\,d_H^w(\omega,\varphi_t). \]
The factor \(1/D\) changes neither the minimizing worlds nor whether every minimizer entails the query. The conversion has polynomial binary encoding length, and it works in reverse by normalizing the integer weights. So the proposed inference problem is not merely expected to inherit the paper’s result: it is the same problem under a change of scale. Proposition 1 and Corollary 1 already cover it. The same normalization applies to weighted GMax and GMin profiles if their continuous versions are defined by rational mass at each distance level.
That makes the timetabling story especially poor grounds for a new mirror: curriculum weights already stand for student multiplicities. More generally, this inference problem has no fractional population decisions for continuization to relax. The population is fixed, and its masses only scale contributions to an objective over Boolean worlds. A mirror that adds fractional interventions or changes how beliefs are formed could pose a different computational question, but it would no longer be a mirror of the result the proponent anchored on.
This is a strong objection to the proposed anchor because the paper itself already covers its exact model. It does not establish the universal claim that no worthwhile continuous question can be built around belief merging. Under the programme’s rules, existing high-multiplicity work alone would support a mirror; the negative case rests specifically on the exact equivalence here, and is weaker for any genuinely different population-level problem.
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.