Answer: Polynomial-time solvable: \(O(m+\tau)\) exact arithmetic operations and \(O((m+\tau)L^2)\) bit operations suffice, without restricting the number of local minima of \(q\).
Corollary 3.4 — class: algorithmic
Given rational location types \(z_1<\cdots<z_\tau\), rational masses \(\mu_t\ge 0\) with \(\sum_t\mu_t=1\), and a positive continuous piecewise-linear scaling function \(q:[0,1]\to\mathbb{R}_{>0}\) described by rational breakpoints and coefficients with \(O(1)\) local minima, output an exact \(y^\star\in[0,1]\) and \(v^\star\) satisfying \(v^\star=q(y^\star)\sum_{t=1}^{\tau}\mu_t|y^\star-z_t|=\min_{y\in[0,1]}q(y)\sum_{t=1}^{\tau}\mu_t|y-z_t|\).
A society is given by its support: \(\tau\geq1\) rational location types \(0\leq z_1<\cdots<z_\tau\leq1\), each with positive binary-rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
The input also specifies a continuous function \(q:[0,1]\to\mathbb{R}_{>0}\) by rational breakpoints \(0=b_0<\cdots<b_m=1\) and rational coefficients \(q(y)=a_jy+c_j\) on each \([b_{j-1},b_j]\). Its local-minimum set has at most \(C\) connected components, for a fixed constant \(C\); local minima are weak and relative to \([0,1]\), so a flat minimum counts once.
Define \(F(y)=q(y)\sum_{t=1}^{\tau}\mu_t|y-z_t|\). The computational problem is to output an exact minimizing location \(y^\star\in[0,1]\) and value \(v^\star=F(y^\star)=\min_{y\in[0,1]}F(y)\), encoded as binary rationals; any minimizing location is allowed. Let \(L\) be the total input bit length, and state running times in \(m,\tau,L\).
Is this exact optimization problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For a finite list of equally weighted agents, a linear-time algorithm is claimed when the continuous piecewise-linear scaling function has constantly many local minima; this claim is retained in the [revised version](https://arxiv.org/html/2402.18908v3). No result settling this exact binary-rational mass formulation was located.
The problem admits an exact algorithm using \(O(m+\tau)\) arithmetic operations and \(O((m+\tau)L^2)\) bit operations with schoolbook integer arithmetic. The restriction on the number of local-minimum components of \(q\) is unnecessary.
I use the standard binary encoding of a rational as an integer numerator and a positive integer denominator, both written in binary.
Define \(D(y)=\sum_{t=1}^{\tau}\mu_t|y-z_t|\), so that \(F(y)=q(y)D(y)\). Let \(S=\{b_0,\ldots,b_m\}\cup\{z_1,\ldots,z_\tau\}\). Its distinct elements partition \([0,1]\) into at most \(m+\tau\) intervals.
Lemma. On every interval \([u,v]\) between consecutive elements of \(S\), the minimum of \(F\) is attained at an endpoint.
Proof. There is no breakpoint of \(q\) or support location in \((u,v)\). Consequently, there are rational coefficients \(a,c,s,d\) such that \(q(y)=ay+c\) and \(D(y)=sy+d\) throughout \([u,v]\). The formulas hold at the endpoints by continuity. Thus \(F(y)=as\,y^2+(ad+cs)y+cd\).
There are three cases.
\(F((1-\lambda)u+\lambda v)-((1-\lambda)F(u)+\lambda F(v))=-as\,\lambda(1-\lambda)(v-u)^2\geq 0\).
The convex combination of the endpoint values is at least their minimum, so \(F(y)\geq\min\{F(u),F(v)\}\) throughout the interval.
\(F'(y)=aD(y)+s q(y)>0\),
because \(D(y)\geq 0\) and \(q(y)>0\). Hence \(F\) is strictly increasing and its minimum is at \(u\).
These exhaust the possibilities when \(as>0\), proving the lemma. \(\square\)
Every point of \([0,1]\) therefore has objective value at least that of some point of \(S\). Since \(S\) is finite and nonempty, we obtain the exact identity \(\min_{y\in[0,1]}F(y)=\min_{x\in S}F(x)\).
In particular, some minimizing location is an input support location or an input breakpoint. Both the location and its objective value are rational.
Define the total first moment \(T=\sum_{t=1}^{\tau}\mu_t z_t\). For a candidate \(x\in S\), define the prefix quantities \(M(x)=\sum_{z_t\leq x}\mu_t\) and \(H(x)=\sum_{z_t\leq x}\mu_t z_t\).
Splitting the distance sum at \(x\) gives
\(D(x)=\sum_{z_t\leq x}\mu_t(x-z_t)+\sum_{z_t>x}\mu_t(z_t-x)\).
Using \(\sum_t\mu_t=1\), this becomes
\(D(x)=xM(x)-H(x)+T-H(x)-x(1-M(x))=(2M(x)-1)x+T-2H(x)\).
The algorithm is therefore:
Each support location and breakpoint is processed only constantly many times. Thus the algorithm uses \(O(m+\tau)\) exact arithmetic operations and comparisons. The lemma proves that the retained candidate is a global minimizer.
No expansion of a rational mass into equally weighted agents is needed.
To bound intermediate sizes and make exact comparison explicit, let \(Q\) be the product of the positive denominators of all input rationals. Since their encodings are included in the total input length, \(\log_2 Q=O(L)\).
Scale every input rational by \(Q\). In particular, write the resulting integers as \(U_t=Q\mu_t\), \(Z_t=Qz_t\), \(A_j=Qa_j\), and \(E_j=Qc_j\). Every candidate has an integer coordinate \(X=Qx\).
Precompute \(R=\sum_t U_tZ_t\). During the sweep maintain \(W=\sum_{z_t\leq x}U_t\) and \(V=\sum_{z_t\leq x}U_tZ_t\). The preceding distance formula yields
\(D(x)=\dfrac{(2W-Q)X+R-2V}{Q^2}\).
On the active piece of \(q\), we also have
\(q(x)=\dfrac{A_jX+E_jQ}{Q^2}\).
Consequently,
\(F(x)=\dfrac{N(x)}{Q^4}\), where \(N(x)=(A_jX+E_jQ)((2W-Q)X+R-2V)\).
All candidates share the denominator \(Q^4\), so comparing their values requires only comparing the integer numerators \(N(x)\).
Every integer used here has \(O(L)\) bits:
There are \(O(m+\tau)\) input rationals. Constructing \(Q\), scaling the inputs, computing the moments, and performing the sweep therefore require \(O(m+\tau)\) integer operations on \(O(L)\)-bit operands. Schoolbook multiplication and division take \(O(L^2)\) bit operations, giving the stated bound \(O((m+\tau)L^2)\).
The output can be \(y^\star=X^\star/Q\) and \(v^\star=N(x^\star)/Q^4\), with both fractions encoded in binary. These are exact rational encodings of \(O(L)\) bits; reduction to lowest terms is unnecessary for the stated representation.
The revised paper states the local-minimum candidate characterization in Theorem 4.1 and the constant-local-minima linear-time claim in Corollary 1. [Revised paper, Section 4.1](https://arxiv.org/html/2402.18908v3#S4.SS1)
The proof above independently settles the binary-rational mass formulation. By evaluating every breakpoint, it avoids needing a characterization involving local minima or flat components. Its arithmetic-operation count is linear in \(m+\tau\), while its exact bit complexity is polynomial in \(m,\tau,L\), even without the local-minimum restriction.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned exact optimization problem. The argument is correct, including its arithmetic-operation count and polynomial bit-complexity bound. No major or minor mathematical issues were found.
The set \(S\) contains both domain endpoints, all scaling-function breakpoints, and all support locations. After removing duplicates, it partitions the domain into at most \(m+\tau\) nondegenerate intervals.
On each such interval, the claimed affine representations of \(q\) and \(D\) are valid: no scaling breakpoint or absolute-value kink occurs in its interior. Continuity extends these representations to both endpoints. The product expansion
\(F(y)=as\,y^2+(ad+cs)y+cd\)
is correct.
The three cases exhaust all possibilities:
Thus each interval has an endpoint minimizer. Taking the minimum over the finite, nonempty set \(S\) proves the claimed global identity. This establishes existence of a rational minimizing location without relying on the cited paper.
The distance decomposition assigns every support location to exactly one of the two sums. Including locations equal to \(x\) in the prefix causes no error because their distance contribution is zero.
The algebra yielding
\(D(x)=(2M(x)-1)x+T-2H(x)\)
is correct and uses the stated normalization \(\sum_t\mu_t=1\).
The sweep is well specified:
Consequently, the initialization and sweep require \(O(m+\tau)\) exact arithmetic operations and comparisons. The candidate lemma proves that the retained location is globally optimal.
The denominator construction is valid under the stated numerator–denominator binary encoding. Every input denominator divides \(Q\), and the sum of their binary lengths is bounded by the total input length. Therefore \(\log_2 Q=O(L)\), and all scaled inputs are integers with \(O(L)\) bits, including signed scaling coefficients.
Both scaled evaluation formulas are correct:
\(D(x)=((2W-Q)X+R-2V)/Q^2\)
and
\(q(x)=(A_jX+E_jQ)/Q^2\).
Their product therefore has precisely the common denominator \(Q^4\) and the stated numerator \(N(x)\). Comparing these numerators is equivalent to comparing objective values because the denominator is common and positive.
The intermediate-size bounds also hold:
There are \(O(m+\tau)\) input rationals. Constructing \(Q\), scaling each input by exact integer division and multiplication, computing moments, and evaluating candidates all fit the claimed number of integer operations. Schoolbook arithmetic on these operands yields the stated bound \(O((m+\tau)L^2)\).
The output fractions \(X^\star/Q\) and \(N(x^\star)/Q^4\) have \(O(L)\)-bit encodings. The task does not require reduced fractions, so omitting fraction reduction is valid.
The written argument covers support size \(\tau=1\), support locations at domain endpoints, coincident support locations and breakpoints, constant scaling pieces, zero distance slopes, flat objective intervals, and tied minimizing candidates.
Strict positivity of \(q\) is used correctly in the derivative cases. Positive masses ensure nonnegative distance values. No assumption about the number or structure of local minima enters the argument, so the stronger claim that the restriction is unnecessary is justified.
The paper does contain the described candidate characterization in Theorem 4.1 and the constant-local-minima linear-time claim in Corollary 1. [Revised paper, Section 4.1](https://arxiv.org/html/2402.18908v3#S4.SS1)
These statements are contextual citations, not premises of the submitted proof. The proof independently addresses the specified support representation, exact rational output, and running times in \(m,\tau,L\). It establishes polynomial-time solvability; no repair or additional clarification is needed.
⟨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.