| paper | d4-conf-ijcai-2007-0035 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
parameterized→NP-hard discrete result → its continuous mirror
Answer: Exact computation of the bound and its certified removals is \(\mathrm{NP}\)-hard. Deciding \(B(D)>q\), or whether a specified pair is removed, is \(\mathrm{NP}\)-complete. · discrete side: parameterized · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given current finite domains \(D_1,\ldots,D_n\), a radius \(q\), and a binary-rational society \(\mu\) supported on types \(T\), each with one ideal \(v^t\), compute the subset-average lower bound \(B(D)=\max_{\emptyset\ne S\subseteq T}\left\lceil\frac{1}{|S|}\sum_{i=1}^{n}\min_{a\in D_i}\sum_{t\in S}\mathbb{1}[a\ne v_i^t]\right\rceil\), and prune each \(a\in D_i\) whose corresponding bound with \(X_i=a\) fixed exceeds \(q\). The requested output is this sound bound and the values it certifies can be removed; retained values need not have supporting completions.
A shared feasible configuration \(x=(x_1,\ldots,x_n)\) serves a continuum of users represented by supported types \(t\in T\), with mass \(\mu_t>0\) and ideal configuration \(v^t\). Each type has one ideal and the same Hamming distance; the worst-case radius is \(\max_{t:\mu_t>0}\sum_i\mathbb{1}[x_i\ne v_i^t]\), and the anchored task propagates the constraint that this radius is at most \(q\).
The mirror covers Theorem 2’s lower-bound filtering for a Hamming-distance conjunction over supported ideal types. It leaves exact GAC for unbounded support, optimization over arbitrary CSP constraints, and the paper’s empirical comparisons outside the anchor.
The most credible mirror is a shared configuration chosen for a large population—for example, a public service package or mass-market product with \(n\) configurable features. Each person belongs to a type whose members share the same ideal configuration and distance metric. The society is a rational distribution \(\mu\) over \(\tau\) supported types, with many more people than types. A single feasible configuration \(x\) serves everyone, and its worst-case mismatch is
\[
R_\mu(x)=\max_{t:\mu_t>0}\sum_{i=1}^{n}\mathbf{1}[x_i\ne v_i^t],
\]
where \(v^t\) is type \(t\)’s ideal. The design question is to minimize \(R_\mu(x)\), or, for a specified radius \(q\), determine which feature choices can still extend to a configuration within distance \(q\) of every represented type. This preserves the paper’s conjunction/max objective while making the population the continuous object.
My lead anchor is Theorem 2, proved in this paper. It states that Algorithm 3 finds a valid lower bound on the maximum Hamming distance to a set of ideals, filters variable domains using that bound, and runs in \(O(nd2^k)\), where \(n\) is the number of variables, \(d\) the largest domain size, and \(k\) the number of ideals. For the population mirror, \(k=\tau\). The bound considers every nonempty type subset \(S\):
\[
B(D)=\max_{\varnothing\ne S\subseteq T}
\left\lceil
\frac{1}{|S|}\sum_{i=1}^{n}
\min_{a\in D_i}
\sum_{t\in S}\mathbf{1}[a\ne v_i^t]
\right\rceil.
\]
For radius \(q\), fixing \(X_i=a\) and finding the corresponding bound exceeds \(q\) certifies that \(a\) has no completion satisfying the population constraint, so it can be pruned. A solution to Population SIMILAR\(_{\max}\) Propagation is this valid lower bound together with the domain values it soundly removes; retained values need not all have support. The theorem makes this propagation task fixed-parameter tractable in the number of distinct ideal types.
I expect this precise propagation mirror to be Class A. Its scope is the paper’s Hamming-distance conjunction and Theorem 2’s sound but incomplete filtering. It does not show that the full minimax design problem is easy when arbitrary CSP constraints are added; those constraints can themselves make feasibility hard. The paper also reports that exact GAC for SIMILAR\(_{\max}\) with an unbounded number of ideals is NP-hard, citing Hebrard et al. (2005). That gives useful context, but it is not a numbered hardness result proved in this paper. Natural follow-up questions are whether exact GAC is FPT in \(\tau\), and which tractable CSP families let this propagation yield an efficient optimizer.
The weakest point is that the magnitude of \(\mu_t\) does not affect the worst-case objective: only whether \(\mu_t>0\) matters. A tiny group constrains the shared design as much as a large one. That is a real limitation if the intended social question is proportional welfare. Still, a worst-case mandate is plausible for a shared public or safety-critical configuration, and grouping users with identical ideals and metrics is exactly the high-multiplicity move. The authors’ max-over-ideals problem therefore has a recognizable population interpretation, though this mirror uses prevalence only to specify which types are present.
The strongest anchor really is Theorem 2, so the negative case cannot rest on the absence of a named computational result. The issue is what that theorem computes: a bound for a CSP assignment’s worst distance to a *set of reference solutions*. Its input is the ideals and variable domains. If a thousand users share an ideal, the theorem sees the same vector as if one user had it. More generally, the proposed population criterion
\[
R_\mu(x)=\max_{t:\mu_t>0}\delta(x,v^t)
\]
does not use the masses. It is unchanged as the society moves anywhere inside a region with the same support, then can jump when a type’s mass reaches zero. That is a support-robustness question, not an aggregate population question.
The proposed shared-configuration scenario is coherent, especially for a public or safety-critical design that must serve every represented group. But it makes a voter’s ideal into a worst-case constraint, and repeated voters with that ideal can be deduplicated in the discrete problem too. The continuous encoding adds rational proportions that the objective and Theorem 2 ignore. The theorem’s \(O(nd2^\tau)\) bound may be useful for robust design with \(\tau\) distinct ideals; its parameter is the number of reference points, though, not a multiplicity made computationally manageable by taking the population limit.
There is also a mismatch between the paper’s preference expressions and the proposed voter types. In the paper, one user can want to be close to both Volvo and Jaguar while distant from Lada. Those ideals form one user’s logical query. Treating each ideal as a separate voter changes that query into a population conjunction. A more faithful population model would make each type’s complete object its whole preference expression, then specify how satisfaction is aggregated across types. A worst-case aggregation over those expressions is no longer Theorem 2’s flat maximum over ideals; a mass-weighted average or coverage requirement would be a different optimization problem. Such questions may be worthwhile, but this result does not supply their computational anchor.
So the case against is strongest if ChoCo requires population mass to do computational work: Theorem 2 then offers no high-multiplicity gain, and the obvious mass-sensitive variants move beyond its result. But the universal negative is weak at the edge. If support-based robust design counts as a continuous mirror, the public-configuration interpretation survives, and it is not honest to dismiss it as implausible. The objection is that its continuity lies in the input encoding while the theorem’s substance remains set-based—not that no one could use the resulting robust optimization 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.