Answer: Polynomial-time solvable, with bit running time \(\operatorname{poly}(m,\tau,L)\).
Proposition 7 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet MIN-SUM take as input ex- plicit descriptions of n functions fi(·), and output min⃗x,xi≥0∀i, i xi≤B{ i fi(xi)}. Then, MIN-SUM is (weakly) NP-hard, even when each fi(·) takes the form of min{1, gi(·)}, where gi(·) is convex. Observe that without the minimum with 1, this is just con- vex minimization, which can be solved in polynomial time. It is certainly possible that for certain functional forms of Fi (e.g., exponentially distributed), that the min-sum objective can be optimized exactly in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many complete response-curve types \(t\in T\), rational masses \(\mu_t\) summing to \(1\), a per-capita budget \(b\), and nonincreasing penalties \(f_t(x)=\min\{1,g_t(x)\}\) on \([0,H]\), where each \(g_t\) is convex and given by rational piecewise-linear data, choose finite measures \(\lambda_t\) with \(\lambda_t([0,H])=\mu_t\) and \(∑_t\int x\,d\lambda_t(x)\le b\) to minimize \(∑_t\int f_t(x)\,d\lambda_t(x)\); determine the exact and approximation complexity in τ and the encoding size.
A society is given by its support: a list \(T\) of \(\tau\geq 1\) complete response-curve types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type specifies a continuous, convex, nonnegative function \(g_t:[0,H]\to\mathbb R_{\geq 0}\) by rational piecewise-linear data, and its penalty \(f_t(x)=\min\{1,g_t(x)\}\) must be nonincreasing. The subsidy bound \(H>0\) and per-capita budget \(b\geq 0\) are binary rationals.
An allocation consists of finite nonnegative Borel measures \(\lambda_t\) on \([0,H]\), with \(\lambda_t([0,H])=\mu_t\); mass within a type may receive different subsidies. It is feasible when \(\sum_{t\in T}\int x\,d\lambda_t(x)\leq b\), and its cost is \(\sum_{t\in T}\int f_t(x)\,d\lambda_t(x)\).
Given a binary-rational threshold \(q\in[0,1]\), decide whether a feasible allocation has cost at most \(q\). Let \(m\) be the total number of supplied linear pieces and \(L\) the total binary input length, including \(q\); state running times in \(m,\tau,L\).
Is this continuous subsidy-allocation decision problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
The discrete problem, assigning one nonnegative subsidy to each individual under a total budget, is weakly NP-hard even for penalties \(\min\{1,g_i\}\) with convex \(g_i\) ([Abebe, Kleinberg, and Weinberg](https://ojs.aaai.org/index.php/AAAI/article/view/6188)).
No result settling this precise measure-allocation problem was verified.
The measure-allocation decision problem is solvable in polynomial time in \(m,\tau,L\). It is exactly equivalent to rational linear-program feasibility with at most \(2m+\tau\) variables.
The proof uses the permitted splitting of mass within each type. It does not require convexity of \(g_t\) or monotonicity of \(f_t\), beyond the stated input assumptions.
Let \(m_t\) be the number of supplied linear pieces of \(g_t\), so that \(\sum_{t\in T}m_t=m\).
On a supplied interval where \(g_t(x)=ux+v\), the penalty \(f_t(x)=\min\{1,g_t(x)\}\) is affine except possibly where \(ux+v=1\). If \(u\ne0\), insert the point \(x=(1-v)/u\) whenever it lies strictly inside the interval. If \(u=0\), no additional breakpoint is necessary, including when \(g_t\) is identically \(1\) there.
Thus each supplied piece produces at most two affine pieces of \(f_t\). Write the resulting ordered breakpoints as
\(0=a_{t,0}<a_{t,1}<\cdots<a_{t,r_t}=H\),
where \(r_t\le2m_t\), and set \(c_{t,j}=f_t(a_{t,j})\). Continuity ensures that \(f_t\) agrees with affine interpolation between its endpoint values on every closed interval \([a_{t,j},a_{t,j+1}]\).
All these coordinates and values are rational. The total number of breakpoint variables will be
\(N=\sum_{t\in T}(r_t+1)\le2m+\tau\).
Fix a type \(t\). For every breakpoint index \(j\), define the continuous function \(\phi_{t,j}\) that is affine between consecutive breakpoints and satisfies
\(\phi_{t,j}(a_{t,i})=1\) if \(i=j\), and \(\phi_{t,j}(a_{t,i})=0\) otherwise.
Explicitly, for \(x\in[a_{t,k},a_{t,k+1}]\), the only potentially nonzero functions are
\(\phi_{t,k}(x)=\dfrac{a_{t,k+1}-x}{a_{t,k+1}-a_{t,k}}\),
\(\phi_{t,k+1}(x)=\dfrac{x-a_{t,k}}{a_{t,k+1}-a_{t,k}}\).
These definitions agree at shared endpoints. Consequently, for every \(x\in[0,H]\),
\(\phi_{t,j}(x)\ge0,\qquad \sum_{j=0}^{r_t}\phi_{t,j}(x)=1,\)
\(\sum_{j=0}^{r_t}a_{t,j}\phi_{t,j}(x)=x,\)
\(\sum_{j=0}^{r_t}c_{t,j}\phi_{t,j}(x)=f_t(x).\)
The last identity follows from the affine interpolation established in Section 1.
Now let \(\lambda_t\) be any admissible measure for this type. Define
\(y_{t,j}=\int_{[0,H]}\phi_{t,j}(x)\,d\lambda_t(x).\)
These integrals exist because the functions are bounded and Borel measurable and the measure is finite. Integrating the preceding identities, using linearity for finite sums, gives
\(\sum_{j=0}^{r_t}y_{t,j}=\mu_t,\)
\(\sum_{j=0}^{r_t}a_{t,j}y_{t,j}=\int_{[0,H]}x\,d\lambda_t(x),\)
\(\sum_{j=0}^{r_t}c_{t,j}y_{t,j}=\int_{[0,H]}f_t(x)\,d\lambda_t(x).\)
Let \(\delta_a\) denote the unit point mass at \(a\). The measure
\(\widehat{\lambda}_t=\sum_{j=0}^{r_t}y_{t,j}\delta_{a_{t,j}}\)
therefore has exactly the same total mass, spending, and cost as \(\lambda_t\).
Every allocation can thus be replaced by one supported on the constructed breakpoints, preserving spending and cost exactly.
Consider the following rational feasibility problem in the \(N\) variables \(y_{t,j}\):
\(y_{t,j}\ge0\qquad(t\in T,\ 0\le j\le r_t),\)
\(\sum_{j=0}^{r_t}y_{t,j}=\mu_t\qquad(t\in T),\)
\(\sum_{t\in T}\sum_{j=0}^{r_t}a_{t,j}y_{t,j}\le b,\)
\(\sum_{t\in T}\sum_{j=0}^{r_t}c_{t,j}y_{t,j}\le q.\)
If the original measure problem has a feasible allocation of cost at most \(q\), Section 2 supplies variables satisfying this system.
Conversely, any solution of this system defines the finite nonnegative Borel measures
\(\lambda_t=\sum_{j=0}^{r_t}y_{t,j}\delta_{a_{t,j}}.\)
Their masses equal \(\mu_t\); their total spending is at most \(b\); and their cost is at most \(q\), directly by the constraints.
Hence the linear system is feasible if and only if the answer to the original decision problem is yes. This equivalence includes the exact boundary case where the minimum cost equals \(q\).
Every input rational has numerator and denominator of bit length at most \(L\). Each generated breakpoint or penalty value is obtained using a bounded number of rational arithmetic operations on supplied data. Therefore each has numerator and denominator of bit length \(O(L)\). If pieces are supplied by endpoint values, computing their affine coefficients also requires only a bounded number of such operations per piece.
Constructing and ordering the breakpoints takes
\(O(m\log(m+1)+\tau)\)
rational arithmetic operations and comparisons on numbers of bit length \(O(L)\). Using elementary integer arithmetic, this gives a preprocessing bound of
\(O((m\log(m+1)+\tau)L^2)\)
bit operations.
After replacing each equality by two inequalities, the linear system has \(N\le2m+\tau\) variables and \(N+2\tau+2\) inequalities. Its dense binary encoding length \(S\) satisfies
\(S=O((m+\tau)^2L).\)
The standard polynomial-time linear-programming theorem states that feasibility of an explicitly given rational linear system can be decided exactly in time polynomial in its binary encoding length. It applies to systems with equalities and to feasible sets of lower dimension; no strict-feasibility assumption is needed. See the [MIT lecture notes on the ellipsoid method](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf), particularly Section 3.12.
All hypotheses are verified here: the system is finite, explicit, rational, and has polynomial encoding length. Thus, for some fixed polynomial \(p\), the complete decision algorithm runs in
\(O((m\log(m+1)+\tau)L^2+(m+\tau)^2L)+p(S),\qquad S=O((m+\tau)^2L).\)
In particular, its bit running time is \(\operatorname{poly}(m,\tau,L)\).
The endpoint replacement relies on dividing a type’s mass among different subsidies. For an indivisible individual, replacing one subsidy by a mixture of endpoint subsidies is generally inadmissible.
For example, take one type of mass \(1\), with \(H=1\), \(b=1/4\), and \(g(x)=2-2x\). This function is continuous, convex, and nonnegative, and its capped penalty is nonincreasing. Every single subsidy satisfying the budget has penalty \(1\). However, the allowed measure
\(\lambda=\tfrac34\delta_0+\tfrac14\delta_1\)
has spending \(1/4\) and cost \(3/4\). Thus splitting changes the feasible outcomes.
The polynomial-time conclusion therefore concerns precisely the measure-allocation problem posed here. It would be NP-hard under polynomial-time reductions only if \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly. The reduction preserves both budget and cost exactly, and its binary encoding has polynomial size. No major or minor mathematical issues were found.
On each supplied affine piece, the equation \(ux+v=1\) has at most one solution unless \(u=0\). Inserting its solution only when it lies strictly inside the interval correctly handles all cases: crossings, endpoint crossings, constant pieces, and pieces identically equal to \(1\).
After this subdivision, each penalty is affine on every resulting interval. Continuity ensures that the affine formulas extend to the interval endpoints. Each original piece contributes at most two intervals, so \(r_t\leq 2m_t\), and therefore
\[
N=\sum_{t\in T}(r_t+1)\leq 2m+\tau.
\]
The count includes both domain endpoints for every type. Since \(H>0\), the ordered distinct breakpoints give intervals of positive length, as required by the interpolation formulas.
The functions \(\phi_{t,j}\) are well-defined continuous, nonnegative functions. Their definitions agree at shared endpoints, including \(0\) and \(H\).
On each interval, the two displayed weights sum to \(1\). Their weighted breakpoint coordinates equal \(x\), and their weighted penalty values equal \(f_t(x)\) because the penalty is affine there. Thus all three pointwise identities are correct throughout the domain.
Each integral defining \(y_{t,j}\) exists: the integrand is bounded and Borel measurable, and \(\lambda_t\) is finite. Nonnegativity gives \(y_{t,j}\geq 0\). Integrating the finite sums is legitimate and yields exactly the three claimed preservation identities.
Consequently, \(\widehat{\lambda}_t\) is a finite nonnegative Borel measure with the same mass, spending, and cost as \(\lambda_t\). This argument applies to arbitrary admissible measures, including nonatomic measures; it makes no assumption that the original allocation has finite support.
Both implications are established.
An allocation satisfying the budget and threshold constraints produces nonnegative endpoint weights satisfying every LP constraint. Conversely, any real solution of the LP defines admissible atomic measures, whose mass, spending, and cost are exactly those specified by the constraints.
There is no approximation, limiting argument, or rounding step. The use of non-strict inequalities therefore preserves the case of cost exactly \(q\). No separate theorem about attainment of a minimum is needed for this feasibility equivalence.
The claim that convexity and monotonicity are unnecessary for the reduction is also correct: the argument uses continuity and the finite piecewise-affine description.
The rational-size argument is valid. Each new crossing coordinate and endpoint penalty value requires a bounded number of rational operations on input quantities. Their numerator and denominator lengths are therefore \(O(L)\). Computing affine coefficients from endpoint data has the same property because consecutive endpoints are distinct.
The stated construction and ordering bound,
\[
O(m\log(m+1)+\tau),
\]
is a valid upper bound on the number of rational operations and comparisons. Elementary arithmetic on quantities of bit length \(O(L)\) supports the stated preprocessing bound
\[
O((m\log(m+1)+\tau)L^2).
\]
The inequality count is correct: \(N\) nonnegativity constraints, \(2\tau\) inequalities representing the type-mass equalities, and two global inequalities. The dense system consequently has encoding length
\[
S=O((m+\tau)^2L).
\]
The invoked theorem—exact feasibility of explicitly represented rational linear systems is decidable in polynomial binary time—is stated sufficiently precisely, and its hypotheses hold here. In particular, the theorem permits feasible sets of lower dimension. The cited notes’ Section 3.12 explicitly covers arbitrary polyhedra and polynomial-time feasibility for integer data; the rational-data formulation is the standard equivalent formulation. The citation supports the application. [MIT ellipsoid-method lecture notes](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf)
The final bound using a fixed polynomial \(p(S)\) establishes polynomial time in \(m,\tau,L\). The task does not require a particular polynomial exponent.
The example is correct. For every affordable single subsidy \(x\leq 1/4\), \(g(x)=2-2x\geq 3/2\), so the capped penalty is \(1\). The displayed split allocation instead has spending \(1/4\) and cost \(3/4\). Its function satisfies all stated assumptions.
The construction also covers \(\tau=1\), \(b=0\), thresholds \(q=0\) and \(q=1\), constant penalties, and budgets exceeding \(H\). None requires division by a mass, positive budget, or strict feasibility.
The final qualification about NP-hardness is correct under the usual polynomial-time reductions: a problem in \(\mathrm{P}\) can be NP-hard only if \(\mathrm{P}=\mathrm{NP}\).
Required repair feedback: None. The proof establishes the claimed polynomial-time classification for the precise measure-allocation problem.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.