d4-conf-ecai-2024-0121 (d4-conf-ecai-2024-0121)

Given an explicitly listed support \(A\) of family types with rational masses \(\mu_a\ge 0\), \(\sum_{a\in A}\mu_a=1\), integral service requirements \(r_a\), three places with rational per-capita supplies \(q_{p,s}\), and a target \(\theta\), is there an allocation \(x_{a,p}\ge 0\) such that \(\sum_p x_{a,p}\le\mu_a\), \(\sum_a r_a[s]x_{a,p}\le q_{p,s}\), and \(\sum_{a,p}x_{a,p}\ge\theta\)?

A society is given by its support: an explicit list \(A\) of \(\tau\) family types with positive binary-rational masses \(\mu_a\), where \(\sum_{a\in A}\mu_a=1\). Here \(\tau=|A|\) is the support size, not the number of possible types.
There are \(m=3\) places \(P\) and \(t\ge1\) services \(S\). Each type has a nonnegative integral requirement vector \(r_a\in\mathbb Z_{\ge0}^{t}\), encoded in unary; zero coordinates and zero vectors are allowed. Each place has nonnegative binary-rational supplies \(q_{p,s}\), measured per unit of total society mass, and no lower quotas.
Every type may be assigned to every place, with unit utility per unit of assigned family mass. Mass may be split among places or left unassigned. The input threshold is a binary rational \(\theta\in[0,1]\).
An allocation consists of real numbers \(x_{a,p}\ge0\) satisfying \(\sum_{p\in P}x_{a,p}\le\mu_a\) for every \(a\in A\), and \(\sum_{a\in A}r_a[s]x_{a,p}\le q_{p,s}\) for every \(p\in P\) and \(s\in S\). The decision problem asks whether such an allocation satisfies \(\sum_{a\in A,p\in P}x_{a,p}\ge\theta\).
Let \(L\) be the total input encoding length; state running times in \(m\), \(\tau\), \(t\), and \(L\).

Is this continuous assigned-mass decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?

For indivisible families, deciding whether an assignment reaches a given total utility is NP-hard even with three places, no lower quotas, unit upper quotas, and equal positive utilities. With equal utilities, the discrete problem is also FPT in the number of services plus the maximum requirement coordinate. [Source](https://arxiv.org/abs/2408.08392v1)
These discrete results do not classify the continuous problem defined above.

Classification

The continuous assigned-mass decision problem is in \(\mathrm{P}\). This holds even when the number of places \(\mathrm{m}\) is part of the input.

Exact linear-programming formulation

Let \(n=m\tau\), and introduce one real variable \(x_{a,p}\) for each pair \((a,p)\in A\times P\). Consider the following rational linear feasibility problem:

• \(x_{a,p}\ge 0\) for every \(a\in A\) and \(p\in P\).
• \(\sum_{p\in P}x_{a,p}\le\mu_a\) for every \(a\in A\).
• \(\sum_{a\in A}r_a[s]x_{a,p}\le q_{p,s}\) for every \(p\in P\) and \(s\in S\).
• \(-\sum_{a\in A,p\in P}x_{a,p}\le-\theta\).

These constraints have exactly the intended meaning. The first three are precisely the allocation constraints in the question. The fourth is equivalent to assigning total mass at least \(\theta\). Thus an instance has answer yes if and only if this linear system is feasible over the reals.

There are \(n=m\tau\) variables and \(k=m\tau+\tau+mt+1\) inequalities, including nonnegativity. No variables for types outside the explicitly listed support are needed.

Encoding size and running time

Let \(B\) denote the total binary encoding length of the constructed linear system.

Its coefficients belong to \(\{0,1,-1\}\), the requirement coordinates \(r_a[s]\), and the given rational right-hand sides. Each requirement coordinate can be converted from unary to binary in polynomial time, and its binary length is at most \(L+1\). Each supplied rational also has encoding length at most \(L\).

Consequently, even a dense encoding of the system satisfies

\(B=O\bigl((m\tau+1)(m\tau+\tau+mt+1)(L+1)\bigr).\)

The system can therefore be constructed in time polynomial in \(m,\tau,t,L\).

We apply the standard rational linear-programming theorem: feasibility of an explicitly given rational linear system can be decided exactly, in deterministic time polynomial in its binary encoding length. This is the polynomial-time linear-programming result established by [Khachiyan](https://www.mathnet.ru/eng/dan42319).

All hypotheses hold: the system is explicit, has finitely many variables and inequalities, and all coefficients and right-hand sides are rational with polynomial total encoding length. The theorem applies even if the feasible region has empty interior, so zero supplies and zero requirement coordinates cause no difficulty. Exact feasibility also handles equality at the threshold.

The resulting bit running time can be stated as

\((m\tau+\tau+mt+L)^{O(1)}.\)

For \(m=3\), this becomes \((\tau+t+L)^{O(1)}=L^{O(1)}\), since the explicit input encoding bounds both \(\tau\) and \(t\) by \(O(L)\).

Why discrete hardness does not transfer

Indivisibility imposes restrictions absent from this system. Here a type’s mass may be divided among places and partially left unassigned; every feasible real solution is itself a valid allocation. Hence there is no integrality condition to enforce after solving the linear program.

The classification is therefore polynomial-time solvability. Under polynomial-time many-one reductions, an additional claim of \(\mathrm{NP}\)-hardness would imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The prover resolves the assigned task correctly. The LP formulation is exact, its encoding has polynomial size, and the stated rational LP feasibility theorem applies. No major or minor issues were found.

• Variables and domains. There is one real variable \(x_{a,p}\) for each explicitly listed type and place, giving \(n=m\tau\) variables. Nonnegativity matches the allocation definition. Using only the support is correct: the task introduces no families outside \(A\).

• Allocation constraints. For each type, the inequality \(\sum_p x_{a,p}\le\mu_a\) allows both splitting and leaving mass unassigned. For each place and service, \(\sum_a r_a[s]x_{a,p}\le q_{p,s}\) is exactly the stated supply restriction. No eligibility restrictions, lower quotas, or integrality conditions are required.

• Threshold and equivalence. The inequality \(-\sum_{a,p}x_{a,p}\le-\theta\) is equivalent to the required assigned-mass threshold. Both directions of the claimed equivalence follow directly: an admissible allocation reaching the threshold satisfies every LP inequality, and every feasible LP solution is such an allocation. No rounding or conversion step is missing.

• Constraint count. Including nonnegativity, the count is correctly

\(k=m\tau+\tau+mt+1\): respectively, the variable bounds, type mass bounds, supply bounds, and threshold inequality.

• Encoding bound. All matrix entries and right-hand sides are rational. Converting unary requirement coordinates to binary takes polynomial time and does not increase their encoding lengths beyond the stated bound. Negating the threshold changes its encoding length by at most a constant. A dense representation has \(k(n+1)\) entries when right-hand sides are included, so the claimed bound

\(B=O((m\tau+1)(m\tau+\tau+mt+1)(L+1))\)
is valid. It is a loose upper bound, but sufficient.

• LP theorem and running time. The prover states the needed theorem precisely enough: explicit rational linear feasibility is decidable exactly in deterministic time polynomial in its binary encoding length. This is the standard polynomial-time LP result attributed to [Khachiyan](https://www.mathnet.ru/eng/dan42319). Every hypothesis is checked: finitely many variables and inequalities, rational data, and an explicit polynomial-size encoding. Neither strict feasibility nor a full-dimensional feasible region is required.

Substituting the encoding bound gives the valid bit-time estimate \((m\tau+\tau+mt+L)^{O(1)}\). With \(m=3\), explicit listing of the types and service data ensures \(\tau,t=O(L)\), yielding \(L^{O(1)}\). The extension to variable \(m\) is also justified for the same explicit input representation.

• Boundary cases and complexity conclusion. Zero supplies, zero requirement coordinates, and zero requirement vectors remain valid rational LP data. The non-strict threshold inequality includes equality exactly. For \(\theta=0\), the zero allocation is feasible; for \(\theta=1\), the formulation still expresses the requested decision without alteration. Positive masses summing to one exclude an empty support.

The discussion of discrete hardness is correct: indivisibility is absent from this problem, so discrete hardness does not establish continuous hardness. The final statement that polynomial-time many-one NP-hardness would imply \(\mathrm{P}=\mathrm{NP}\) is also correct.

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩