| paper | d4-conf-ecai-2010-0014 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: polynomial-time solvable · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 5
statement extracted from the paper’s text layer
Given typed real variables with axis-aligned domains and Manhattan metrics, \(\tau\) source types represented by \(I\)-consistent cube bases \(K_t\) with rational bounds, a nonempty cube integrity constraint \(IC^*\), and positive rational masses \(\mu_t\) summing to \(1\), compute the exact set \(\operatorname*{arg\,min}_{\omega\in\overline{\operatorname{Mod}_I(IC^*)}} \sum_{t=1}^{\tau}\mu_t\inf_{\eta\models_I K_t} d(\omega,\eta)\), represented as a formula or as a product of coordinate intervals.
A source type is a complete cube belief or goal base, together with its metric and other relevant parameters; its mass \(\mu_t\) is its share of the consultation. A feasible assignment is a plan, and the objective is the mass-weighted sum of each type’s Manhattan distance to its acceptable region, minimized subject to the integrity constraint.
The weighted problem appears to admit a straightforward coordinatewise endpoint sweep, which may limit the mirror’s research upside.
fatal: False
The mirror covers Proposition 5 for \(HS\) interpretations with cube source bases and a cube integrity constraint. It leaves the general \(H\) setting, full formulas and their DNF expansion, and the paper’s other propositions and perspectives aside.
My strongest case is a narrow one: the paper’s cuboid majority merging problem has a natural high-multiplicity mirror. The plan variables already range over continuous spaces, but the paper’s society—the sources whose views are merged—is still a finite multiset. Replacing that multiset with a distribution over recurring source types continuizes the population.
A plausible regime is a large public consultation on a feasible plan, such as housing locations and budgets. Residents submit views expressible as conjunctions of axis-aligned constraints. Many residents use the same template, so the number \(N\) of residents can be much larger than the number \(\tau\) of distinct templates. A type is one complete template, together with the same metric and other parameters used to measure its dissatisfaction. Its mass is the fraction of residents with that template.
The paper’s anchor is Proposition 5, stated as a result of this paper; its proof is omitted for space. Under interpretations in \(HS\), for a cube integrity constraint \(IC^*\), a profile \(K^*\) of cube bases, and a variable \(x_i\) of type \(t_j\), it says that Algorithm 2 computes \(\Delta^i_{IC^*}(K^*)\) in \(O(n_j|V|)\) time, and that there is a formula \(\phi\in L\) whose projection onto \(x_i\), \(S^i(\phi)\), equals that computed set. This is an algorithmic result about the underlying merging problem, which the algorithm computes—not about an encoding.
The precise mirror I would ask a prover to study is Continuous Cuboid Majority Merging. An instance gives typed real variables with axis-aligned box domains and Manhattan metrics; a cube \(K_t\) for each of \(\tau\) source types, with rational half-space bounds; a nonempty cube integrity constraint \(IC^*\); and positive binary-rational masses \(\mu_t\) summing to \(1\). The question is to compute the exact set
\[ \left\{\omega\in\overline{\operatorname{Mod}(IC^*)}: F_\mu(\omega)=\min_{\eta\in\overline{\operatorname{Mod}(IC^*)}}F_\mu(\eta)\right\}, \qquad F_\mu(\omega)=\sum_t\mu_t\,\inf_{\eta\models K_t}d_1(\omega,\eta). \]
A solution is the whole minimizer set, represented as a formula or as its product of coordinate intervals. This keeps the paper’s source dissatisfaction, sum aggregation, integrity constraint, and compromise assignment intact; only the finite source profile becomes a distribution.
I expect this mirror to be Class A. For a discrete profile with \(n_t\) sources of type \(t\), setting \(\mu_t=n_t/N\) scales the paper’s sum objective by \(1/N\) and leaves its minimizers unchanged. Conversely, rational masses can be cleared to denominators to produce a finite discrete profile, possibly with very large multiplicities. The continuous input stores those multiplicities compactly. In the stated cuboid setting, the objective separates by coordinate. Each coordinate minimizes a rationally weighted sum of distances to intervals, restricted to the integrity interval. Sorting the interval endpoints and sweeping the resulting piecewise-linear objective should compute the full minimizer interval in time polynomial in \(\tau\), the dimensions, and the input bit length. This is a weighted extension of the paper’s finite-profile result, not a claim that Proposition 5 already proves the weighted case.
The scope is deliberately limited to Proposition 5’s \(HS\), cube-input setting. Follow-up questions include whether the result extends to nonrectilinear polyhedra and other norms, and what happens for full formulas whose DNF expansion can be large. The paper’s Proposition 5 runtime, as printed, does not account for binary rational weights or their bit lengths, so those bounds would need to be established for the mirror.
The weakest point is the scenario: many real sources may have distinct constraints, leaving \(\tau\) close to \(N\). Repeated templates are plausible in standardized consultations, but not universal. That limits the regime rather than undermining the model: when templates are shared, grouping sources by identical views is precisely what makes this a high-multiplicity problem.
Proposition 5 is the one serious anchor: it gives an algorithm and a running-time bound, so this is not a case where the paper lacks a computational result to mirror.
The strongest skeptical reading is that the proposed mirror changes only the coefficients in a problem the paper already solves. For each coordinate, a source type contributes its distance to an interval; the population objective is the sum of those distances weighted by the type masses. Sweeping the \(2\tau\) interval endpoints finds the minimizing interval, which is then clipped to the integrity interval. Doing this independently for every coordinate returns the full minimizer set. For rational input, this is a small weighted-geometric calculation, not a new use of the continuous-optimization machinery that motivates ChoCo. Proposition 5’s printed bound also omits the number of source bases, although its algorithm loops over them; the practical bound must depend on \(\tau\).
That makes the research payoff look modest: the paper’s finite-profile computation already aggregates source dissatisfaction, and the proposed population version compresses repeated sources into rational weights. But that criticism does not defeat the mirror. The compression is exactly the high-multiplicity change the programme seeks, and standardized public-consultation templates are a plausible regime. Clearing denominators gives an exact finite-profile correspondence, while the weighted version asks a well-posed computational question.
So I can make a case that this is a routine, low-upside mirror, but not that it is unworthy in every scenario. The anchor survives; the universal negative case is weak.
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.