Answer: —
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximate\fi For SC profiles, \app-\Monroe-\summw and \app-\Monroe-\maxmw can be solved in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), committee size \(k\), and ordered types \(i\in\{1,\ldots,\tau\}\) with approval sets \(A_i\subseteq C\) and positive rational masses \(\mu_i\) summing to \(1\), where each candidate’s approving types form an interval, choose a committee \(W\subseteq C\) of size \(k\) and mass assignments \(x_{i,c}\geq 0\) with \(\sum_{c\in W}x_{i,c}=\mu_i\) and \(\sum_i x_{i,c}=1/k\) for every \(c\in W\), minimizing \(\sum_i\sum_{c\in W}x_{i,c}\mathbf{1}[c\notin A_i]\).
Let \(C\) be a set of \(m\geq 1\) candidates and \(1\leq k\leq m\) an integer committee size. A society is given by its support: the list of its \(\tau\geq 1\) types with positive masses, each encoded as a binary rational. Here \(\tau\) is the support size, not the number of possible approval sets.
The support is supplied in an order \(1,\ldots,\tau\); type \(i\) has approval set \(A_i\subseteq C\) and mass \(\mu_i>0\), with \(\sum_i\mu_i=1\). For every candidate \(c\), the set \(\{i:c\in A_i\}\) is an interval in this order, possibly empty. Empty approval sets are allowed.
A feasible outcome consists of a committee \(W\subseteq C\), \(|W|=k\), and divisible assignments \(x_{i,c}\in\mathbb{R}_{\geq0}\) satisfying \(\sum_{c\in W}x_{i,c}=\mu_i\) for each type and \(\sum_i x_{i,c}=1/k\) for each committee member. Its cost is \(\sum_i\sum_{c\in W}x_{i,c}\mathbf{1}[c\notin A_i]\).
Given also a binary rational threshold \(b\in[0,1]\), decide whether a feasible outcome has cost at most \(b\). Let \(L\) be the total binary input length; state running times in \(m,\tau,k,L\).
Is this continuous approval Monroe decision problem solvable in polynomial time in \(m,\tau,k,L\), or is it NP-hard?
For explicitly listed discrete voters with the same interval condition, approval Monroe winner determination is polynomial-time solvable for both total and maximum misrepresentation, with each selected candidate representing between \(\lfloor n/k\rfloor\) and \(\lceil n/k\rceil\) voters ([Chen, Hatschka, and Simola](https://arxiv.org/pdf/2307.16864)). No result settling the exact divisible-mass problem above was located in the literature search.
I do not settle the general polynomial-time versus $\mathrm{NP}$-hardness question. I establish two additional polynomial-time cases for arbitrary binary rational thresholds:
The first case permits crossing intervals. The second permits arbitrary nesting and crossing around the common type. The arguments below are self-contained, except for a precisely stated scheduling theorem used in the second case.
Write
$$
q=\frac1k,\qquad
I_c=\{i:c\in A_i\}.
$$
Each $I_c$ is an interval or is empty. For $J\subseteq\{1,\ldots,\tau\}$, define
$$
\mu(J)=\sum_{i\in J}\mu_i.
$$
Write $\mu_i=p_i/d_i$ and $b=u/v$, with integer numerators and positive integer denominators. Define
$$
D=v\prod_{i=1}^{\tau}d_i,
\qquad
N=kD,
\qquad
T_i=N\sum_{j=1}^{i}\mu_j,
\qquad
T_0=0.
$$
Then $T_\tau=N$, every $T_i$ is an integer, and
$$
Nq=D,\qquad Nb\in\mathbb Z.
$$
Let
$$
B=L+\lceil\log_2(m+1)\rceil+\lceil\log_2(k+1)\rceil+1.
$$
All these integers have $O(B)$ bits: the sum of the binary lengths of the encoded denominators is at most $L$.
For a nonempty interval $I_c=[l_c,r_c]$, associate the integer time window
$$
[\alpha_c,\omega_c)
=
[T_{l_c-1},T_{r_c}).
$$
Type $i$ corresponds to the block $[T_{i-1},T_i)$.
For $Q\subseteq C$, with $|Q|\leq k$, let $F(Q)$ be the maximum approved mass in a partial assignment satisfying
$$
z_{i,c}\geq0,\qquad
z_{i,c}=0\text{ if }i\notin I_c,
$$
$$
\sum_{c\in Q}z_{i,c}\leq\mu_i,
\qquad
\sum_i z_{i,c}\leq q.
$$
This is a maximum-flow problem: use source-to-candidate capacities $q$, candidate-to-approved-type capacities $2$, and type-to-sink capacities $\mu_i$.
For every committee $W$ of size $k$,
$$
\operatorname{cost}(W)=1-F(W).
$$
Proof. The approved part of any complete assignment is feasible for the partial-flow problem. Hence every complete assignment has cost at least $1-F(W)$.
Conversely, take a maximum approved partial assignment. Its residual type supplies and residual candidate quotas both total $1-F(W)$. Because assignments between every type and every selected candidate are permitted, these residual quantities can be matched. The resulting complete assignment has cost at most $1-F(W)$. Together with the lower bound, this proves equality. $\square$
After scaling by $N$, all capacities are integers. Integral maximum flow therefore gives an optimal approved assignment on the $1/N$ grid. Residual supplies and quotas are also integral after scaling, so completion can likewise be performed on that grid.
Consequently, a committee is a polynomial-size certificate. Its optimum can be verified by maximum flow, establishing membership in $\mathrm{NP}$. For example, Edmonds–Karp gives the conservative bit-time bound
$$
O\!\left(
L B^2+
(\tau+k+2)(k\tau+k+\tau)^2B^2
\right).
$$
Define
$$
\delta(Q)=q|Q|-F(Q).
$$
Then
$$
\delta(Q)=
\max_{S\subseteq Q}
\left(
q|S|-\mu\!\left(\bigcup_{c\in S}I_c\right)
\right).
$$
Proof. The source-only cut has capacity $q|Q|\leq1$, so a minimum cut cannot cross an arc of capacity $2$.
If $S$ is the set of source-side candidates, every type in their approval union must also lie on the source side. Including any further type increases the cut capacity, since its mass is positive. Thus
$$
F(Q)=
\min_{S\subseteq Q}
\left(
q(|Q|-|S|)
+
\mu\!\left(\bigcup_{c\in S}I_c\right)
\right).
$$
Subtracting from $q|Q|$ proves the formula. The choice $S=\varnothing$ also shows $\delta(Q)\geq0$. $\square$
If a committee contains $e$ empty-interval candidates and its nonempty candidates form $Q$, then
$$
\operatorname{cost}(W)=eq+\delta(Q).
$$
A scaled integral approved assignment for $Q$ can be represented by assigning integer time units to its candidates. Each candidate receives at most $D$ units, all inside its window, and no time unit is assigned twice.
Indeed, within each type block, partition time units according to the integral approved-flow amounts; unused units remain unassigned. Conversely, such a schedule determines approved-flow amounts by counting candidate time units in each type block.
Thus $NF(Q)$ is the maximum total number of executed units when candidates in $Q$ may each execute between zero and $D$ units inside their windows.
Assume the nonempty candidates can be ordered as $c_1,\ldots,c_s$ so that
$$
\alpha_1\leq\alpha_2\leq\cdots\leq\alpha_s,
\qquad
\omega_1\leq\omega_2\leq\cdots\leq\omega_s.
$$
This condition is checkable by sorting on left endpoints, breaking ties by increasing right endpoint, and checking that the right endpoints are nondecreasing. In particular, it holds if no nonempty candidate interval properly contains another.
Fix any subsequence of this candidate ordering. Starting with cursor $t=0$, process its selected candidates in order.
For a selected candidate with window $[\alpha,\omega)$:
$$
a=\max(t,\alpha),\qquad
p=\min(D,\omega-a),
$$
execute the candidate throughout $[a,a+p)$, and set $t=a+p$.
This greedy schedule maximizes the total approved units for that fixed selection.
Proof. Start with an optimal integral partial schedule. We transform it successively to agree with the greedy schedule.
Suppose previously processed candidates already agree with the greedy schedule, whose current cursor is $t$. All remaining execution is at times at least $t$.
Consider the next candidate, with window $[\alpha,\omega)$. Every later candidate has release time at least $\alpha$ and deadline at least $\omega$.
If $\omega\leq\max(t,\alpha)$, then $\omega\leq t$, because $\alpha<\omega$. The current candidate has no execution in the remaining schedule. The required greedy step already holds.
Otherwise, define
$$
a=\max(t,\alpha),\qquad
p=\min(D,\omega-a),\qquad
P=[a,a+p).
$$
Let:
Since the current candidate executes only inside $[a,\omega)$,
$$
z\leq p.
$$
Since time units are disjoint,
$$
h+y\leq p.
$$
Assign every unit of $P$ to the current candidate, and remove its old execution outside $P$. This displaces $y$ units of later candidates.
Reassign $\min(y,z-h)$ displaced units to distinct former current-candidate units outside $P$. Every such reassignment is valid: the destination is later than the displaced unit and earlier than $\omega$; the receiving candidate’s release is no later than its displaced execution time, and its deadline is at least $\omega$. Discard any remaining displaced units.
No later candidate’s executed amount increases. If $V$ and $V'$ denote total execution before and after this transformation, then
$$
V'-V
=
p-z-y+\min(y,z-h)
=
p-z-\max(0,y-z+h).
$$
Both
$$
p-z\geq0
\quad\text{and}\quad
y-z+h\leq p-z
$$
hold, so $V'\geq V$.
The current candidate now executes exactly the greedy prefix $P$, and all later execution occurs at times at least $a+p$. This proves the induction step.
After all selected candidates have been processed, the resulting schedule is the greedy schedule. It is feasible and has value at least the original optimum, so it is optimal. $\square$
Define
$$
\mathcal T=
\{T_i+hD:
0\leq i\leq\tau,\ 0\leq h\leq k,\ T_i+hD\leq N\}.
$$
Its cardinality $R$ satisfies
$$
R\leq(\tau+1)(k+1).
$$
Every greedy cursor belongs to $\mathcal T$. Initially the cursor is $T_0$. A positive-execution step ends either at a deadline $\omega$, which is some $T_i$, or at $\max(t,\alpha)+D$. The latter is either $\alpha+D$ or $t+D$, and belongs to $\mathcal T$ whenever it is at most $N$. An expired candidate leaves the cursor unchanged.
The numerical size of $N$ therefore does not determine the number of states.
For candidate $c_j$, let $g_j(t)$ be the number of units added by its greedy step and $f_j(t)$ its resulting cursor.
Let
$$
G_j(r,t)
$$
be the maximum greedy execution among selections of exactly $r$ candidates from $c_1,\ldots,c_j$ whose final cursor is $t$.
Initialize
$$
G_0(0,0)=0
$$
and all other entries to $-\infty$.
For each layer, initialize its entries to $-\infty$ and apply the following updates to every finite preceding entry:
$$
G_{j+1}(r,t)
\leftarrow
\max\{G_{j+1}(r,t),G_j(r,t)\},
$$
and, if $r<k$,
$$
G_{j+1}(r+1,f_{j+1}(t))
\leftarrow
\max\{
G_{j+1}(r+1,f_{j+1}(t)),
G_j(r,t)+g_{j+1}(t)
\}.
$$
These are respectively the choices to omit or select the next candidate. Future greedy steps depend on the preceding selection only through its cursor, so retaining the largest value at each state is valid. Induction on $j$ proves the table’s stated meaning.
Let $e$ be the number of empty-interval candidates. The optimum approved units for a committee of size $k$ are
$$
G^*=
\max_{\substack{0\leq r\leq k\\k-r\leq e}}
\ \max_{t\in\mathcal T}G_s(r,t).
$$
The other $k-r$ selections are empty candidates. Lemma 3 and Proposition 1 give
$$
\operatorname{OPT}=1-\frac{G^*}{N}.
$$
Thus the decision answer is affirmative exactly when
$$
G^*\geq N(1-b).
$$
Sort the coordinates and precompute all cursor transitions using binary search. This requires
$$
O(mR\log(R+1))
$$
arithmetic operations; the dynamic program requires $O(mkR)$.
All finite table entries and coordinates have $O(B)$ bits. A conservative total bit-time bound is
$$
O\!\left(
\left[
L+m\log(m+1)
+m\tau k\bigl(k+\log(\tau k+2)\bigr)
\right]B^2
\right).
$$
This is polynomial in $m,\tau,k,L$, independently of denominator magnitudes.
Assume there is a type $h$ satisfying
$$
h\in I_c
$$
for every nonempty candidate interval.
This additional hypothesis allows endpoints to occur in arbitrary orders.
Let $s$ be the number of nonempty candidates, and put
$$
t=\min(k,s),\qquad e=k-t.
$$
There is an optimal committee with exactly $t$ nonempty candidates. To see this, whenever a committee contains an empty candidate and omits a nonempty candidate, replace the former by the latter. Its existing approved partial assignment remains feasible, so approved mass cannot decrease. Repetition yields the asserted composition.
If $s=0$, every outcome has cost $1$, and the decision is immediate. Assume henceforth $t\geq1$.
Set
$$
\beta=b-\frac ek.
$$
If $\beta<0$, reject: the empty candidates alone cause cost at least $e/k$.
For $\beta\geq0$, define augmented supplies
$$
\mu'_h=\mu_h+\beta,\qquad
\mu'_i=\mu_i\quad(i\neq h).
$$
Keep each candidate’s capacity equal to $q$.
For every set $Q$ of nonempty candidates,
$$
\delta_\mu(Q)\leq\beta
$$
if and only if all candidates in $Q$ can receive their full quotas using approved augmented supply.
Proof. Every nonempty $S\subseteq Q$ has an approval union containing $h$. Therefore
$$
\mu'\!\left(\bigcup_{c\in S}I_c\right)
=
\mu\!\left(\bigcup_{c\in S}I_c\right)+\beta.
$$
The minimum-cut calculation from Proposition 2 remains valid with augmented supplies: source-only cut capacity is still at most $1$, so capacity-$2$ arcs cannot cross a minimum cut.
Full approved quotas are feasible exactly when
$$
q|S|\leq
\mu'\!\left(\bigcup_{c\in S}I_c\right)
$$
for every $S\subseteq Q$. For nonempty $S$, these inequalities are exactly
$$
q|S|-\mu\!\left(\bigcup_{c\in S}I_c\right)\leq\beta.
$$
The empty-subset inequality is automatic. Proposition 2 now proves the equivalence. $\square$
For a committee with nonempty part $Q$ of size $t$, its original cost is
$$
\frac ek+\delta_\mu(Q).
$$
Hence it meets threshold $b$ exactly when its nonempty candidates can all receive full approved quotas under the augmented supplies.
Define augmented integer cumulative coordinates
$$
U_i=
N\sum_{j=1}^{i}\mu'_j
=
T_i+N\beta\,\mathbf 1[i\geq h].
$$
These are integers because
$$
N\beta=Nb-eD\in\mathbb Z.
$$
For each nonempty candidate, create a job with:
There is a full approved assignment for some $t$ nonempty candidates exactly when at least $t$ jobs can be completed.
For the forward direction, scale an approved full-quota flow by $N$, take an integral flow, and partition augmented type blocks into job time units. Every selected job receives exactly $D$ units inside its window.
For the reverse direction, choose any $t$ completed jobs and count their execution in each augmented type block. These counts yield an approved assignment respecting augmented supplies and giving every chosen candidate $D/N=q$. Unused time units correspond to unused augmented supply.
Baptiste, Chrobak, Dürr, Jawor, and Vakhania prove that maximum weighted throughput for preemptive single-machine jobs with a common positive integer processing time, integer releases and deadlines, and nonnegative integer weights is computable in $O(s^4)$ arithmetic operations, where $s$ is the number of jobs. [Theorem 2.1](https://arxiv.org/pdf/cs/0209033)
Here processing time is the positive integer $D$, all releases and deadlines are integers, and every weight is $1$.
Discard jobs whose windows have length less than $D$. If fewer than $t$ jobs remain, reject immediately. This explicitly handles an empty retained job list. Otherwise, shift releases and deadlines by the minimum retained release time and apply the theorem. Accept exactly when maximum throughput is at least $t$.
The theorem’s tables are indexed by jobs and job counts. Their time calculations involve input coordinates and at most $O(m)$ multiples of $D$, so their integers have $O(B)$ bits. A conservative total bit-time bound is
$$
O\!\left((L+m\tau+m^4)B^2\right).
$$
This proves polynomial-time decision for arbitrary rational $b$ under the common-type hypothesis.
The endpoint-order hypothesis in Lemma 3 is essential to its exchange argument.
Take two candidates $a,b$, committee size $k=2$, and three types with
$$
A_1=\{a\},\qquad
A_2=\{a,b\},\qquad
A_3=\{a\},
$$
$$
\mu_1=\frac15,\qquad
\mu_2=\frac15,\qquad
\mu_3=\frac35.
$$
In unscaled cumulative coordinates, the windows are
$$
a:[0,1),\qquad
b:\left[\frac15,\frac25\right).
$$
Processing $a$ greedily first assigns it $[0,1/2)$ and leaves no approved mass for $b$. This obtains approved mass $1/2$.
The optimum approved mass is instead $7/10$: give $b$ the entire middle type and give $a$ mass $1/2$ from the first and third types. This is optimal because $a$ contributes at most $1/2$ and $b$ at most $1/5$.
The exchange proof fails here because the later candidate’s deadline is earlier. Displaced execution cannot necessarily be moved to the first candidate’s later execution times.
This example refutes the unrestricted greedy extension; it supplies no hardness proof. It satisfies the common-type hypothesis and is covered by Section 4.
The results above establish exact polynomial algorithms for two classes beyond the cases proved in the notes. They do not settle instances that combine unrestricted nesting and crossing without a common approved type.
No polynomial-time algorithm or $\mathrm{NP}$-hardness reduction for that general case is established here.
⟨structured verdict parsed — rendered above⟩
The output establishes genuine partial results: membership in $\mathrm{NP}$ and polynomial-time algorithms for the two stated special cases. Neither special-case argument has a substantive mathematical defect. The general classification requested in USER_TASK remains unresolved, as the prover explicitly acknowledges.
The scaling is correct. Since every denominator $d_i$ divides $D$,
$$
N\mu_i=kD\frac{p_i}{d_i}
$$
is an integer. Consequently, every $T_i$ is an integer, and normalization gives $T_\tau=N$. Also,
$$
Nq=D,\qquad Nb=kD\frac uv\in\mathbb Z.
$$
Because all masses are positive, the cumulative coordinates are strictly increasing. Thus a nonempty candidate interval produces a window with $\alpha_c<\omega_c$, including when its approval interval consists of a single type.
The bit-length claim is valid. The logarithm of the denominator product is bounded by the sum of the input denominator lengths. Multiplication by $k$ adds only $O(\log(k+1))$ bits. Coordinates lie between $0$ and $N$, so they also have $O(B)$ bits.
The construction does not require explicitly creating $N$ voters or time units. The later scheduling interpretations use these units to establish equivalences, while the algorithms operate on binary coordinates.
Finding: Correct.
The network correctly models approved partial assignments. Candidate capacity is $q$, type capacity is $\mu_i$, and an approval-edge capacity of $2$ exceeds the total mass that can flow.
Proposition 1 proves both inequalities required for
$$
\operatorname{cost}(W)=1-F(W),
$$
where $\operatorname{cost}(W)$ is understood as the minimum assignment cost for the fixed committee.
The residual completion argument is valid: residual supplies and residual quotas have the same total, and every type may assign mass to every committee member. Completion therefore exists. Its cost is at most the residual total; together with the lower bound, this establishes equality.
After scaling, integral maximum flow applies. Residual completion also has an integral realization after scaling. These observations justify the claimed rational grid without imposing a discretization assumption on the original continuous problem.
A committee is a polynomial-size certificate. Computing its optimum by maximum flow and comparing against $b$ is a polynomial-time verification procedure. The stated Edmonds–Karp bound is conservative: the graph has at most $\tau+k+2$ vertices and $k\tau+k+\tau$ forward edges, and capacities have $O(B)$ bits.
Finding: Correct; membership in $\mathrm{NP}$ is established for the general problem.
For $|Q|\leq k$, the source-only cut has capacity at most $1$. Therefore a minimum cut cannot cross an approval arc of capacity $2$.
For a fixed source-side candidate set $S$, its approved types must also be source-side. Additional source-side types strictly increase the cut capacity because their masses are positive. This proves the displayed minimum-cut formula and hence the deficiency formula.
The identity for committees containing empty candidates follows correctly:
$$
1-F(Q)
=
1-q|Q|+\delta(Q)
=
eq+\delta(Q).
$$
The partial-scheduling equivalence is also correct. Integral flow quantities can be partitioned within each type block into disjoint integer time units, and counting scheduled units in those blocks recovers a feasible approved partial flow. Candidate execution is bounded by $D$, exactly as required.
Finding: Correct.
The endpoint hypothesis supplies both properties needed by the exchange argument: every later candidate has release at least $\alpha$ and deadline at least $\omega$.
The induction invariant is valid. Initially, all execution occurs at nonnegative times. After a greedy prefix has been fixed, the transformation leaves all remaining execution after the new cursor.
The expired-window case is handled correctly. Since $\alpha<\omega$,
$$
\omega\leq\max(t,\alpha)
$$
implies $\omega\leq t$.
For the positive-execution case, the bounds
$$
z\leq p,\qquad h+y\leq p
$$
are justified respectively by the candidate quota and available window length, and by disjointness of execution.
Reassigning displaced later-candidate units is valid:
The execution-change calculation is correct:
$$
V'-V
=
p-z-y+\min(y,z-h)
=
p-z-\max(0,y-z+h).
$$
The inequality $h+y\leq p$ gives
$$
y-z+h\leq p-z,
$$
so the change is nonnegative.
Thus the transformation preserves feasibility and cannot reduce total execution. Repeating it proves greedy optimality for each fixed selection.
Finding: Correct, including ties in endpoints and candidates receiving zero execution.
The cursor coordinate set is polynomial in size. Each positive greedy step ends at a deadline, at $\alpha+D$, or at $t+D$; zero-execution steps preserve the cursor. Across at most $k$ selections, the claimed coordinate representation suffices.
The dynamic-programming state records all information relevant to future transitions: the number selected, the current cursor, and the greatest accumulated execution for that state. Future greedy behavior depends only on the cursor. Therefore discarding lower-valued histories at the same state is sound.
The final maximization correctly permits exactly those nonempty selection counts that can be supplemented to size $k$ by available empty candidates. Unreachable states retain value $-\infty$.
The decision comparison
$$
G^*\geq N(1-b)
$$
is exact because $N(1-b)$ is integral.
The operation counts and bit-time bound are polynomial in $m,\tau,k,L$. The cases $s=0$, $k=1$, and $k=m$ are covered by the stated initialization and final maximization.
Finding: Correct polynomial-time algorithm under the ordered-endpoint hypothesis.
Replacing a selected empty candidate by an omitted nonempty candidate preserves every existing approved-flow assignment. Hence an optimum exists with exactly $\min(k,s)$ nonempty candidates. The all-empty case and rejection when $\beta<0$ are correctly handled.
For the relevant sets $Q$ with $|Q|\leq k$, Lemma 4 is correct. Every nonempty subset $S$ has an approval union containing $h$, so augmentation adds exactly $\beta$ to every nonempty Hall-type supply expression. The empty-subset inequality remains automatic. This establishes the equivalence between the deficiency budget and full-quota feasibility.
Minor issue — scope of Lemma 4. The wording “For every set $Q$ of nonempty candidates” should explicitly retain $|Q|\leq k$. Section 2 defines $\delta(Q)$ only on that domain, and the cited source-only cut bound uses it. All subsequent applications satisfy this restriction, so this is an expositional issue.
Minimum clarification: State Lemma 4 for every set $Q$ of nonempty candidates with $|Q|\leq k$.
The augmented coordinates are integral because
$$
N\beta=Nb-eD.
$$
They remain strictly increasing, and their magnitudes are at most $2N$, since $0\leq\beta\leq1$. Their bit lengths are consequently $O(B)$.
The full-quota scheduling equivalence is valid in both directions. Selecting any $t$ completed jobs from a larger completed set preserves feasibility.
The cited theorem matches the application. The paper defines integer releases and deadlines, a common positive integer processing length, nonnegative integer weights, and schedules consisting of integer time units. Its Theorem 2.1 provides the claimed polynomial algorithm. [Baptiste, Chrobak, Dürr, Jawor, and Vakhania](https://arxiv.org/pdf/cs/0209033)
The prover checks the relevant hypotheses:
The asserted bit-time conversion is supported by the theorem’s job-indexed tables and coordinate arithmetic. Its calculations use releases, deadlines, and bounded multiples of processing length rather than enumerating the numerical time horizon. The displayed bound
$$
O\!\left((L+m\tau+m^4)B^2\right)
$$
is therefore a valid conservative polynomial bound.
Finding: Correct polynomial-time algorithm under the common-type hypothesis.
The counterexample is calculated correctly. Greedy processing of $a$ first obtains approved mass $1/2$. Candidate $b$ can obtain at most $1/5$, and candidate $a$ at most $1/2$, giving an upper bound of $7/10$ that the described assignment attains.
It correctly demonstrates failure of that unrestricted greedy extension. It does not refute another algorithm or establish hardness, and the prover makes neither claim.
The main remaining limitation is coverage: the two additional hypotheses are not assumptions of USER_TASK. The output supplies no algorithm or hardness reduction for arbitrary candidate intervals. Its opening and closing statements accurately acknowledge this.
Minimum additional work needed to settle the target: A verifiable polynomial-time algorithm covering all permitted interval instances, or a valid hardness reduction for those instances. Clarifying the existing special-case proofs alone cannot resolve the general question.
⟨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.