| paper | d4-journals-jair-2010-0019 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: the continuous valid-value decision problem belongs to \(\mathrm{P}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 7
statement extracted from the paper’s text layer
Given a rational distribution \(\mu\) over complete configuration-request types, each with an MDD of feasible whole-configuration paths and additive costs \(c_{j,t}\), current type-level settings, and cohort-average limits \(K_j\), determine for a target type \(t_0\), variable \(x_i\), and value \(a\) whether there are path flows for each type such that all mass of \(t_0\) uses paths with \(x_i=a\) and \(\sum_t \mu_t \mathbb{E}[c_{j,t}] \le K_j\) for every cost \(j\). The values passing this feasibility test form the valid domain.
Use a flow variable for each edge of each type’s MDD; flow conservation represents distributions over whole configurations, and cohort-average cost limits are linear constraints. For each candidate value, constrain all flow for the target type to paths using that value and test linear feasibility.
Average-cost coupling replaces the paper’s single-configuration feasibility question with portfolio feasibility; the authors may view that as a new problem, a concern the proponent acknowledges but cannot resolve.
fatal: False
The mirror covers the multi-cost domain-computation results anchored by Proposition 3 and Theorem 7; it leaves the single-cost algorithm, MDD compilation, and experimental results aside.
There is a real, though qualified, population mirror for the paper’s multi-cost results. The lead is Fleet-2-wCVD, a continuous version of two-cost configuration. It keeps the paper’s central task—finding which values remain valid under partial assignments and cost limits—but applies it to a large procurement cohort rather than one customer configuring one product.
A type is a complete configuration request: its variables, domains, constraints, feasible MDD, prices, cost coefficients, and current shared settings. The society is a distribution \(\mu\) over such request types. In the clearest regime, a data-center operator is procuring thousands or millions of servers from a small number of repeated request profiles, so the number of units is much larger than the support size \(\tau\). Units of a type share the same request and costs, while each unit still receives one whole, valid configuration. A fleet-wide choice, such as a common platform setting, applies to every unit of that type; other attributes may vary across units. The cost limits are per-unit averages across the cohort, such as average purchase price and average energy use.
The decision variable is mass \(f^t_e\) sent along each edge of each type’s MDD. Flow conservation makes this a distribution over complete, feasible configuration paths; the MDD represents the individual constraints, so no unit receives a fractional configuration. For cost \(j\), the cohort must satisfy \(\sum_{t,e} c_{j,t}(e)f^t_e\le K_j\). As in the paper’s CVD query, there is no separate optimization objective: for a type \(t\), variable \(x_i\), and candidate value \(a\), the question is whether a feasible allocation exists when all mass of type \(t\) is required to have \(x_i=a\). The values for which it does are the valid domain. This is a population-level domain query: it asks which setting the operator can make common across a request cohort while still meeting the fleet’s average cost limits.
The lead anchor is Proposition 3, proved in this paper. It states that 2-wCVD-SAT is NP-hard even for Boolean variables and linear cost functions with positive coefficients. The reduction is from Two-Partition: each number \(s_i\) gets a pair of Boolean variables constrained to differ; one cost sums the odd-indexed variables weighted by \(s_i\), the other sums the even-indexed variables, and each cost is bounded by half the total. Both bounds can be met exactly when the numbers can be partitioned into two equal-sum sets.
For that anchor, Fleet-2-wCVD takes a rational type distribution, an MDD for each type’s feasible configurations, two additive per-unit costs, two average-cost limits, and current type-level settings. It asks for the valid values of a specified unassigned variable under those limits. A candidate is valid if the corresponding flow-feasibility system has a solution. This is a polynomial-size LP: it has one flow variable per MDD edge, flow-conservation constraints, two cost constraints, and a constraint fixing the candidate value for the target type. A flow on a DAG decomposes into whole configuration paths, so this LP is exactly a population allocation, not an approximation that gives individuals fractional products. The expected outcome is tractable, Class A. The discrete hardness concerns whether one path satisfies both limits; the population question permits different units to take different paths while meeting the limits in aggregate.
A second mirror, Fleet-k-wCVD, uses the same definition with \(k\) cost limits, where \(k\) is part of the input. Its anchor is Theorem 7, also proved here: k-wCVD-SAT is strongly NP-hard when \(k\) varies. The proof reduces from bin packing. It uses \(n\) variables, each with \(k\) values representing bins, no hard constraints, and \(k\) additive costs; assigning item \(i\) to a bin charges its size to that bin’s cost. Each cost has capacity \(K\), so a feasible assignment exists exactly when the items can be packed into \(k\) bins of capacity \(K\).
Fleet-k-wCVD asks the corresponding domain question for a population under \(k\) average-cost bounds. Its LP adds one cost constraint per objective, so it remains polynomial in \(k\), the total MDD size, and the rational input length. It too is expected to be tractable, Class A. Theorem 7’s strong hardness does not transfer to this mass-allocation question: a feasible population may mix whole configurations even when no single configuration meets every bound. The two mirrors are worth anchoring separately because Proposition 3 establishes hardness for two criteria even in the simple Boolean case, while Theorem 7 establishes hardness when the number of criteria is itself variable.
The strongest support for author recognition is how little of the paper’s actual task disappears. The mirror still uses feasible configurations encoded by MDDs, additive costs, partial assignments, cost bounds, and interactive valid-domain computation. It changes the unit of decision from one product to a cohort of repeated requests, and changes cost limits from per-product limits to cohort averages. Those are consequential co-modifications, but they are natural in large-scale procurement. The population itself is the distribution over complete request types; the flow over configurations describes the action taken for that population.
The weakest point is that average-cost limits permit cross-subsidy: some units may exceed a limit if others bring the cohort average down. The paper’s original query asks whether a *single* complete configuration meets every bound, and its authors could reasonably say that the fleet query is a new portfolio problem rather than their direct analogue. The mirror is most credible when the application genuinely has fleet-wide average targets; if every individual product must satisfy every bound, the LP convexification is not valid. The scope here is therefore just Proposition 3 and Theorem 7’s multi-cost domain-computation results, not the paper’s single-cost algorithm or its compilation and empirical results.
This mirror also suggests useful follow-up questions: how closely can finite cohorts approximate the continuous domains, what bounds ensure that a feasible mass allocation can be rounded with small cost violations, and how do the domains change when the operator imposes per-unit limits alongside cohort averages?
The strongest negative is that Fleet-2-wCVD and Fleet-\(k\)-wCVD change what the paper’s query means. The paper asks whether one partial assignment can be extended to one feasible product whose costs meet every bound. Proposition 3 and Theorem 7 establish hardness for that single-configuration question.
The fleet LP instead asks whether there is a distribution over feasible configurations whose *average* costs meet the bounds. For paths \(p\) through an MDD, it tests whether the cost vector lies in the convex hull of \(\{(c_1(p),\ldots,c_k(p))\}\). Its flows can be decomposed into whole configurations, so the units receive integral products. But the portfolio can use different products for different units and cross-subsidize their costs. That is a coherent batch-procurement question; it is not the paper’s interactive valid-domain query for one customer.
This distinction defeats both anchors on the same ground. For Proposition 3, the fleet query replaces “does one configuration satisfy both limits?” with “can a mixture satisfy both average limits?” For Theorem 7, it does the same with \(k\) limits. The results motivate those questions, but their reductions do not make the fleet problem a continuous version of the results’ original problem.
The strongest alternative mirror still has this issue. A large cohort buying repeated server configurations, with fleet-wide settings and average price or energy limits, is plausible. If each product instead has its own hard cost limits, identical units just repeat the same query; the population adds no new computation. If the operator imposes shared average limits, the problem becomes coordinated portfolio configuration. Fixing a setting for every unit of a type makes that setting a meaningful policy choice, but the remaining choices are still allocated across the cohort under shared budgets. That is a substantive extension, not a continuization of the paper’s interaction model.
The author-recognition gate is therefore the real weakness in the negative case. The paper is about cost-bounded configuration, MDDs, and valid domains, so its authors might well recognize fleet configuration as a worthwhile extension. The fleet scenario also genuinely has high multiplicity. I cannot honestly rule out a continuous mirror in every scenario. My narrower case is that these two anchors do not establish one: their best population reformulation changes the query’s semantics, and whether that neighboring portfolio problem merits this programme’s time remains uncertain.
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.