Answer: Feasibility and exact minimization are polynomial-time solvable in \(m,\tau,L\), with a rational optimal plan. Additive approximation is polynomial-time solvable in \(m,\tau,L,\log(1/\varepsilon)\) by returning that exact plan.
Proposition 4.1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThe optimization problem in (12) can be posed as the constrained LS problem minimize α · ∥Ax −t∥2 2 + β · ∥v∥2 2 + γ · ∥u∥2 2, subject to Dx ≥d, Tx ≤τ, Bx −b ≤u, Bx −b ≥v, u ≥0, v ≤0, (13) where u, v ∈R|P | are additional auxiliary variables.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given projects \(P\), work packages \(W\), months \(M\), and a finite support \(T\) of complete researcher profiles with rational masses \(\mu_t\) summing to \(1\), each profile specifies cost \(e_t\), capacity \(\tau_{t,m}\), package eligibility, and target dedication \(q_{t,p,m}\). The instance also gives per-capita package requirements \(d_w\), project budgets \(b_p\), and nonnegative rational weights \(\alpha,\beta,\gamma\). Choose average dedication \(y_{t,w,m}\ge 0\), zero for ineligible packages, with \(\sum_w y_{t,w,m}\le\tau_{t,m}\), so that \(\sum_t\mu_t\sum_{m\in[w_s,w_e]}y_{t,w,m}\ge d_w\) for each package. Let \(z_{t,p,m}=\sum_{w\in p}y_{t,w,m}\) and \(c_p=\sum_t\mu_t e_t\sum_{w\in p,m}y_{t,w,m}\). Find a feasible plan minimizing \(\alpha\sum_t\mu_t\sum_{p,m}(z_{t,p,m}-q_{t,p,m})^2+\beta\sum_p\min(0,c_p-b_p)^2+\gamma\sum_p\max(0,c_p-b_p)^2\), or report infeasibility; for approximate computation, return an \(\varepsilon\)-optimal plan. Measure input size in the support and planning dimensions and binary input length.
Let \(M\) be an explicitly listed sequence of months, \(W\) a finite set of work packages with inclusive intervals \([w_s,w_e]\subseteq M\), and \(P\) a partition of \(W\) into nonempty projects. Put \(m=|P|+|W|+|M|\).
A society is given by its support: the list \(T\) of \(\tau\) complete researcher types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types. Type \(t\) specifies a positive rational hourly cost \(e_t\), nonnegative integer monthly capacities \(k_{t,m'}\), and package eligibility. Each hour contributes the same work regardless of type.
Inputs also include nonnegative rational per-capita requirements \(d_w\), per-capita budgets \(b_p\), and finite nonnegative rational weights \(\alpha,\beta,\gamma\). Nonnegative rational targets \(q_{t,p,m'}\) are specified when some eligible package in \(p\) is active in \(m'\), and are zero otherwise. Let \(L\) be the total binary input length.
A plan consists of real average dedications \(y_{t,w,m'}\geq0\), zero unless \(t\) is eligible for \(w\) and \(m'\in[w_s,w_e]\), satisfying \(\sum_w y_{t,w,m'}\leq k_{t,m'}\) and \(\sum_t\mu_t\sum_{m'\in[w_s,w_e]}y_{t,w,m'}\geq d_w\). Define \(z_{t,p,m'}=\sum_{w\in p}y_{t,w,m'}\) and \(c_p=\sum_t\mu_t e_t\sum_{w\in p,m'\in M}y_{t,w,m'}\); budgets impose no hard constraints.
Minimize \(F(y)=\alpha\sum_{t,p,m'}\mu_t(z_{t,p,m'}-q_{t,p,m'})^2+\beta\sum_p\min(0,c_p-b_p)^2+\gamma\sum_p\max(0,c_p-b_p)^2\), or report infeasibility. For rational \(0<\varepsilon<1\), the approximate problem asks for a feasible rational plan with \(F(y)\leq\min F+\varepsilon\).
Is this mass planning problem, including feasibility and exact minimization, solvable in polynomial time in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard? What is the corresponding classification for additive approximation, with running time measured in \(m,\tau,L,\log(1/\varepsilon)\)?
For a finite list of researchers, dedications are already real-valued; the asymmetric soft-budget objective admits a constrained least-squares formulation ([Lera-Leri and Bistaffa](https://iiia.csic.es/media/filer_public/ad/14/ad14495d-7346-49d7-98d4-166ac5f63ec1/lera-leri_2024_a_robust_and_scalable_approach_to_meet_user_preferences_in_research_project_planning.pdf)). No result addressing exactly this support-given mass formulation was located.
Feasibility and exact minimization are solvable in deterministic polynomial time in \(m,\tau,L\). A feasible instance has a rational optimal plan of polynomial encoding length, and such a plan can be computed exactly.
Consequently, additive approximation is also solvable in polynomial time in \(m,\tau,L,\log(1/\varepsilon)\): the exact algorithm already returns a plan meeting every positive additive tolerance.
The proof uses an explicit reduction to rational convex quadratic programming. All dedications retain the real-valued meaning specified in the question.
Let
\(I=\{(t,w,j):t\text{ is eligible for }w,\ j\in[w_s,w_e]\}\).
Introduce one variable \(y_{t,w,j}\) for each element of \(I\), and interpret all other dedication coordinates as zero.
Write \(K\) for the polyhedron defined by
\(y_{t,w,j}\geq0\quad((t,w,j)\in I),\)
\(\displaystyle \sum_{w:(t,w,j)\in I}y_{t,w,j}\leq k_{t,j}\quad(t\in T,\ j\in M),\)
and
\(\displaystyle \sum_{t,j:(t,w,j)\in I}\mu_t y_{t,w,j}\geq d_w\quad(w\in W).\)
These are exactly the plan constraints. In particular, neither budgets nor targets affect feasibility.
There are at most \(\tau|W||M|\leq\tau m^2\) variables. All constraints have rational coefficients, and their explicit encoding length is polynomial in \(m,\tau,L\). Thus rational linear programming decides feasibility in polynomial time.
Furthermore, nonnegativity and each monthly capacity constraint imply
\(0\leq y_{t,w,j}\leq k_{t,j}\).
Hence \(K\) is bounded. It is closed because it is defined by finitely many non-strict linear inequalities. If \(K\) is nonempty, it is compact, so the continuous objective \(F\) attains its minimum.
For a scalar \(r\), define
\(r_+=\max\{0,r\}\).
Then
\(\min(0,r)^2=(-r)_+^2\).
For every project \(p\), introduce two nonnegative variables \(u_p,v_p\), with linear constraints
\(u_p\geq b_p-c_p(y),\qquad v_p\geq c_p(y)-b_p.\)
Consider the quadratic objective
\(\displaystyle G(y,u,v)= \alpha\sum_{t,p,j}\mu_t\bigl(z_{t,p,j}(y)-q_{t,p,j}\bigr)^2 +\beta\sum_p u_p^2+\gamma\sum_p v_p^2.\)
For every feasible triple, the auxiliary constraints imply
\(u_p\geq(b_p-c_p(y))_+,\qquad v_p\geq(c_p(y)-b_p)_+.\)
Since squaring is nondecreasing on nonnegative arguments and \(\beta,\gamma\) are nonnegative, it follows that
\(G(y,u,v)\geq F(y).\)
Conversely, every \(y\in K\) has the feasible lift
\(u_p=(b_p-c_p(y))_+,\qquad v_p=(c_p(y)-b_p)_+,\)
for which \(G(y,u,v)=F(y)\). Therefore the original problem and this quadratic program have the same optimal value.
This argument also covers zero weights. It does not require auxiliary variables of an arbitrary optimizer to equal the positive parts.
For completeness, we can make the auxiliary feasible region bounded without changing this equivalence. Define
\(\displaystyle C=\sum_{t\in T}\mu_t e_t\sum_{j\in M}k_{t,j}.\)
For any \(y\in K\), positivity of costs and nonnegativity of dedications give
\(\displaystyle 0\leq c_p(y) \leq\sum_t\mu_t e_t\sum_j\sum_w y_{t,w,j} \leq C.\)
Thus both canonical auxiliary coordinates are at most
\(U_p=C+|b_p|\).
Add the bounds
\(u_p\leq U_p,\ v_p\leq U_p\).
Every original feasible plan still has its canonical lift, and the resulting quadratic program has a compact feasible region.
Finally, if \((y^*,u^*,v^*)\) minimizes this program, then
\(\displaystyle \min_{y\in K}F(y) \leq F(y^*) \leq G(y^*,u^*,v^*) =\min_{y\in K}F(y).\)
Consequently, its projected plan \(y^*\) is an exact optimizer of the original problem.
Each target discrepancy is an affine function of \(y\), squared and multiplied by the nonnegative rational coefficient \(\alpha\mu_t\). Each auxiliary penalty is also a square with a nonnegative rational coefficient.
More explicitly, collect all variables into \(x=(y,u,v)\). For rational vectors \(a_\ell\), rational scalars \(h_\ell\), and nonnegative rational coefficients \(\lambda_\ell\), the objective has the form
\(\displaystyle G(x)=\sum_\ell\lambda_\ell(a_\ell^{\mathsf T}x-h_\ell)^2.\)
Its Hessian is
\(\displaystyle H=2\sum_\ell\lambda_\ell a_\ell a_\ell^{\mathsf T}.\)
For every real vector \(r\),
\(\displaystyle r^{\mathsf T}Hr =2\sum_\ell\lambda_\ell(a_\ell^{\mathsf T}r)^2\geq0.\)
Hence \(H\) is positive semidefinite, including when some or all weights vanish. The program is a convex quadratic program with rational linear constraints. No square roots of masses or weights are needed.
Its size is polynomial:
All coefficients, including \(C\), arise from polynomially many rational additions and multiplications. Their binary encoding lengths are polynomially bounded: multiplication adds numerator and denominator lengths, and a sum can use the product of its denominators, whose length is at most their total length. Expanding the objective into its rational quadratic matrix therefore also takes polynomial time and space.
The explicit month list and explicit support are essential here. The construction neither enumerates unlisted types nor expands masses into individual researchers.
We use the following classical theorem in the binary Turing model:
Rational convex quadratic programming theorem. Given a rational symmetric positive semidefinite matrix \(H\), rational vectors \(h,a\), and a rational constraint matrix \(A\), a quadratic program minimizing
\(\frac12x^{\mathsf T}Hx+h^{\mathsf T}x\)
subject to \(Ax\leq a\) can be solved exactly in time polynomial in its binary encoding length. In particular, for a nonempty bounded feasible region, the algorithm returns a rational optimal point and the exact rational optimal value.
This is the exact polynomial-time result of [Kozlov, Tarasov, and Khachiyan, *The polynomial solvability of convex quadratic programming*](https://www.mathnet.ru/eng/zvmmf5189).
Every hypothesis has been verified: the constructed program has rational data, a positive semidefinite Hessian, and, when the planning instance is feasible, a nonempty compact feasible region. A rational constant term in its objective can be omitted during optimization and restored when reporting the value.
Applying the theorem and projecting onto the dedication coordinates yields an exact rational optimal plan in time polynomial in \(m,\tau,L\). Its output length is polynomially bounded as well. Evaluating the original formula at that plan gives the exact rational minimum.
For any promised rational tolerance \(0<\varepsilon<1\), run the exact algorithm. On a feasible instance its output satisfies
\(F(y^*)=\min F\leq\min F+\varepsilon.\)
The optimization routine is independent of \(\varepsilon\), so it satisfies the requested polynomial running-time bound in \(m,\tau,L,\log(1/\varepsilon)\).
Thus both exact optimization and additive approximation admit polynomial-time algorithms. Under the usual polynomial-time reductions, an \(\mathrm{NP}\)-hardness result for these tasks would imply \(\mathrm{P}=\mathrm{NP}\). This establishes binary polynomial-time solvability; it does not assert a strongly polynomial algorithm.
⟨structured verdict parsed — rendered above⟩
The output proves the requested polynomial-time classifications. The reduction is exact, its size and coefficient lengths are polynomially bounded, and the cited convex quadratic programming theorem supplies exact optimization in the binary Turing model. No major or minor mathematical issues were found.
The index set \(I\) includes exactly the permitted dedication coordinates: eligible type–package pairs during the package’s inclusive active interval. Interpreting omitted coordinates as zero matches the task.
The three families of inequalities defining \(K\) correctly encode:
The placement of \(\mu_t\) is correct. Neither targets nor budgets impose feasibility constraints in the task, so excluding them from \(K\) is justified.
There are at most \(\tau|W||M|\leq\tau m^2\) dedication variables. The constraint coefficients and right-hand sides are rational, and explicitly constructing these constraints requires only polynomial size. Rational linear programming therefore supplies the claimed polynomial-time feasibility decision.
For each retained variable, its monthly capacity inequality and nonnegativity imply \(0\leq y_{t,w,j}\leq k_{t,j}\). Thus \(K\) is bounded and closed. When nonempty, it is compact. The objective is continuous, so its minimum is attained.
Assessment: Correct.
The scalar identity \(\min(0,r)^2=(-r)_+^2\) is correct.
Together with nonnegativity, the auxiliary constraints imply
\[
u_p\geq(b_p-c_p(y))_+,\qquad
v_p\geq(c_p(y)-b_p)_+.
\]
Squaring preserves these inequalities because all quantities are nonnegative. Multiplication by the nonnegative weights \(\beta,\gamma\) consequently gives \(G(y,u,v)\geq F(y)\).
Conversely, the stated canonical lift satisfies every auxiliary lower bound and achieves equality \(G(y,u,v)=F(y)\). These two directions establish equality of optimal values.
The argument handles zero weights correctly: it never requires every optimal auxiliary coordinate to equal its canonical value.
Assessment: Correct.
The bound
\[
0\leq c_p(y)\leq C
\]
follows from nonnegative dedications, positive costs and masses, and the monthly capacity constraints. Summing over all packages gives a valid upper bound for spending on any one project.
For any allowed budget, the canonical coordinates satisfy
\[
(b_p-c_p(y))_+\leq |b_p|,\qquad
(c_p(y)-b_p)_+\leq C+|b_p|.
\]
Hence the proposed common bound \(U_p=C+|b_p|\) is valid. Adding these upper bounds preserves every canonical lift and makes the auxiliary feasible region compact.
The concluding inequality chain is also valid. Its first inequality uses \(y^*\in K\), its second uses the established pointwise comparison, and its final equality uses equality of optimal values. It proves that projecting any quadratic-program optimizer gives an original-problem optimizer.
Assessment: Correct.
All squared affine terms have nonnegative rational coefficients. Differentiating their sum gives exactly
\[
H=2\sum_\ell\lambda_\ell a_\ell a_\ell^{\mathsf T}.
\]
The displayed quadratic-form calculation proves positive semidefiniteness for every real vector, including when the Hessian is singular or zero.
Consequently, the constructed optimization problem is a rational convex quadratic program. The observation that no square roots are needed correctly avoids unnecessary irrational coefficients.
Assessment: Correct.
The stated counts of variables, constraints, and squared affine terms are valid polynomial bounds. The omitted dedication coordinates do not require additional variables.
The rational-arithmetic argument correctly bounds coefficient lengths. Each constructed coefficient uses polynomially many input quantities and arithmetic operations of the stated form; products and common-denominator sums therefore retain polynomial binary length. Expanding the squared terms creates a matrix of polynomial dimension with polynomial-length rational entries.
The explicit support and month list ensure that the construction requires neither enumeration of unlisted types nor expansion of rational masses into individual researchers.
Assessment: Correct.
The theorem invoked is the relevant exact polynomial-time result, rather than merely an approximation theorem. The cited paper expressly addresses exact determination of the optimum and an attaining point in polynomial binary-input time; its rational-data formulation is consistent with the standard denominator-clearing extension of its integer-data presentation. [Kozlov, Tarasov, and Khachiyan](https://www.mathnet.ru/eng/zvmmf5189).
Every hypothesis needed for this application is checked in the output:
There is no need for strict convexity, a unique optimizer, or an interior feasible point. Omitting and subsequently restoring the rational constant term is legitimate.
The theorem therefore establishes an exact rational optimizer with polynomial output length. Projection preserves rationality, and evaluating the original objective at that plan yields its exact rational optimal value.
Assessment: Correct.
Returning the exact optimal plan satisfies every promised positive additive tolerance. Since the optimization algorithm does not depend on \(\varepsilon\), its running time satisfies the requested polynomial bound in \(m,\tau,L,\log(1/\varepsilon)\). It need not inspect the tolerance to produce a valid answer.
The qualification concerning NP-hardness is appropriate: polynomial-time solvability would make NP-hardness under the usual polynomial-time reductions imply \(\mathrm{P}=\mathrm{NP}\). The output correctly distinguishes binary polynomial time from strongly polynomial time.
Assessment: Correct.
Zero objective weights, zero capacities, zero requirements, absent eligible coordinates, and lower-dimensional feasible regions do not invalidate the argument. Empty variable or project sets introduce only empty sums and trivial optimization cases.
No repair is required. The output settles feasibility, exact minimization, and additive approximation for the support-given formulation.
⟨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.