Answer: Exact minimization is polynomial-time solvable; an exact rational optimizer and optimum value can be computed in polynomial bit complexity.
Proposition 1 — class: algorithmic
Given a pool size \(B\) and the error moments \(v,a,b,d\), choose recruited mass \(q\in[0,1]\) to minimize \(F_x(Bq)=\frac{Bqa+v+Bq(Bq-1)b+2Bqd}{(Bq+1)^2}\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Here there is one human type, with mass \(1\), so \(\tau=1\); there is no candidate parameter \(m\).
The input consists of a binary integer pool size \(B\ge2\) and binary rational moments \(v,a,b,d\). Here \(v\ge0\) is the machine's expected squared error, \(a\ge0\) is the average human error variance, \(b\) is the average covariance between distinct humans' errors, and \(d\) is the average machine–human error covariance; covariances may be negative. Human errors have mean zero, the machine error has mean zero and variance \(v\), and the moments are promised realizable by a pool of \(B\) humans.
Recruit a divisible fraction \(q\in[0,1]\), corresponding to human mass \(Bq\). The machine remains included with weight \(1\); the supplied moments remain fixed as recruitment changes. The objective is the stipulated interpolation \(F_x(Bq)=\frac{Bqa+v+Bq(Bq-1)b+2Bqd}{(Bq+1)^2}\), including at fractional masses; \(x\) is fixed and represented only through \(v\).
Is exact minimization of \(F_x(Bq)\) over \(q\in[0,1]\) solvable in polynomial time, or is it NP-hard, with running time measured in \(\tau\), the total input bit length \(L\), and the binary encoding length of \(B\)?
Known results: integer recruitment has an analytic optimization rule when \(d<(3b-a)/2\). Real-valued recruitment is also explicitly analyzed, including the remaining regimes, and a finite pool bound is considered in the [original source](https://www.ijcai.org/proceedings/2018/0064.pdf); an explicit bit-complexity classification is not stated.
The stipulated problem admits an exact deterministic polynomial-time algorithm. It returns both a rational minimizing fraction \(q^\star\) and the rational minimum value. The algorithm examines at most three candidate points, regardless of the numerical size of \(B\).
Set \(n=Bq\). Since \(B>0\), this substitution is a bijection between \(q\in[0,1]\) and \(n\in[0,B]\). Define
\(c=a-b+2d\). The objective becomes
\(G(n)=F_x(n)=\dfrac{bn^2+cn+v}{(n+1)^2}.\)
The denominator is positive throughout \([0,B]\). Thus \(G\) is continuous on this compact interval and differentiable on its interior. In particular, a global minimum exists.
This is the objective in Equation (1) of the [original source](https://www.ijcai.org/proceedings/2018/0064.pdf), whose Propositions 1 and 2 analyze real-valued recruitment. The following argument establishes the bounded-interval optimization and its bit complexity directly.
Define
\(\alpha=2b-c=3b-a-2d\) and
\(\beta=c-2v=a-b+2d-2v\).
Differentiating and simplifying gives
\(G'(n)=\dfrac{(2bn+c)(n+1)-2(bn^2+cn+v)}{(n+1)^3} =\dfrac{\alpha n+\beta}{(n+1)^3}.\)
Consider the following cases.
\(r=-\beta/\alpha\). Every global minimizer in \((0,B)\) must have derivative zero, by Fermat’s theorem. Consequently, some global minimizer belongs to the set consisting of \(0\), \(B\), and \(r\) if \(r\in[0,B]\).
\(G(n)=b(n+1)^2/(n+1)^2=b\).
Every feasible point minimizes \(G\), including \(0\).
Thus the following algorithm is correct in every case:
The set contains at most three points. Including a stationary point that happens to be a maximum is harmless: the algorithm compares its value with both endpoints.
Represent each input rational as an integer numerator divided by a positive integer denominator. Let \(T\) be the product of the four moment denominators, and write
\(v=V/T,\qquad a=A/T,\qquad b=K/T,\qquad d=D/T,\)
where \(V,A,K,D\) are integers, possibly signed where permitted.
Define the integers
\(P=3K-A-2D,\qquad Q=A-K+2D-2V.\)
Then \(\alpha=P/T\), \(\beta=Q/T\), and, when \(P\ne0\), the stationary candidate is \(r=-Q/P\). Represent it with a positive denominator by setting
\(u=-Q\,\operatorname{sgn}(P),\qquad w=|P|.\)
The feasibility test is exactly \(0\le u\le Bw\), using integer comparisons.
For any feasible candidate \(n=u/w\), with \(w>0\), substitution yields the exact evaluation formula
\(G(u/w)= \dfrac{Ku^2+(A-K+2D)uw+Vw^2}{T(u+w)^2}.\)
Its denominator is positive. Thus two candidate values \(N_1/H_1\) and \(N_2/H_2\), with \(H_1,H_2>0\), can be compared exactly by comparing the signed integers \(N_1H_2\) and \(N_2H_1\). The returned recruitment fraction is \(q^\star=u/(Bw)\).
Let \(L\) denote the total input bit length, including the binary encoding of \(B\). Every integer constructed above has \(O(L)\) bits:
There are only constantly many integer arithmetic operations and comparisons. With ordinary schoolbook arithmetic, the algorithm uses \(O(L^2)\) bit operations and returns fractions with \(O(L)\)-bit numerators and denominators, allowing unreduced fractions. If reduced fractions are required, greatest-common-divisor computations also take polynomial time.
In particular, the algorithm never enumerates the \(B\) humans. Its dependence on \(B\) is through the encoding length \(\ell_B=\lfloor\log_2 B\rfloor+1\), which is already included in \(L\).
Exact minimization is therefore polynomial-time solvable, with \(\tau=1\), including all signs of the covariances and all degenerate derivative cases. A rational-threshold decision version is also in \(\mathrm P\), since the exact minimum can be compared with the threshold in polynomial time.
The realizability promise requires no additional algorithmic work: the proof applies to every rational coefficient tuple for the stipulated interpolation, and therefore applies to every promised input. No additional parameter or discrete selection problem is introduced.
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned problem correctly. It establishes an exact deterministic polynomial-time algorithm for the stipulated continuous objective, returning a rational optimizer and a rational minimum. No major or minor mathematical issues were found.
The proof addresses exactly the supplied model: one human type, fixed moments, divisible recruitment, and a machine that remains included.
The substitution \(n=Bq\) is a bijection from \(q\in[0,1]\) to \(n\in[0,B]\), since \(B\ge2\). Expanding the stipulated numerator gives
\(Bqa+v+Bq(Bq-1)b+2Bqd=bn^2+(a-b+2d)n+v\).
Thus the stated definition \(c=a-b+2d\) and the expression
\(G(n)=(bn^2+cn+v)/(n+1)^2\)
are correct.
For every feasible \(n\), \(n+1\ge1\). There are no poles on the feasible interval. Continuity on the nonempty compact interval \([0,B]\) ensures existence of a global minimum; differentiability holds throughout its interior.
The source attribution is accurate: Equation (1) contains the corresponding objective, and Propositions 1 and 2 discuss real-valued recruitment. The proof does not rely on those propositions for its correctness. [Original source](https://www.ijcai.org/proceedings/2018/0064.pdf)
The quotient-rule calculation is correct. Its simplified numerator is
\((2bn+c)(n+1)-2(bn^2+cn+v)=(2b-c)n+c-2v\).
Consequently,
\(G'(n)=(\alpha n+\beta)/(n+1)^3\),
with \(\alpha=3b-a-2d\) and \(\beta=a-b+2d-2v\), exactly as stated. The denominator is strictly positive throughout the feasible interval.
All derivative cases are covered.
The algorithm therefore examines a complete candidate set of at most three points. A stationary maximum cannot cause an incorrect result because both endpoints are also evaluated. Stationary points at endpoints, duplicate candidates, and ties create no difficulty: the task requires returning a minimizer, not establishing uniqueness.
The common denominator \(T\) is positive and divisible by each input denominator. Hence the integer numerators \(V,A,K,D\) exist as stated.
The formulas \(P=3K-A-2D\) and \(Q=A-K+2D-2V\) correctly give \(\alpha=P/T\) and \(\beta=Q/T\).
When \(P\ne0\), the proposed representation satisfies
\(u/w=-Q/P\), with \(w=|P|>0\).
Multiplying the interval conditions by this positive denominator shows that the feasibility test \(0\le u\le Bw\) is exact.
The evaluation formula
\(G(u/w)=[Ku^2+(A-K+2D)uw+Vw^2]/[T(u+w)^2]\)
is correct. For feasible candidates, \(u\ge0\) and \(w>0\), so its denominator is strictly positive. Signed cross multiplication therefore compares values correctly, including negative values.
The returned fraction \(q^\star=u/(Bw)\) equals \(n^\star/B\) and belongs to \([0,1]\). Endpoints also admit the stated representation with positive denominator.
The bit-length argument is valid.
The product \(T\) has bit length bounded by the sum of the four denominator lengths, up to a constant. Common-denominator numerators, linear combinations, candidate coordinates, feasibility products, evaluation expressions, and comparison products all contain only a fixed number of input-sized factors. Every intermediate integer therefore has \(O(L)\) bits.
There are constantly many arithmetic operations. Schoolbook multiplication and integer division on these sizes take \(O(L^2)\) bit operations, while additions and comparisons take linear time. Thus the claimed \(O(L^2)\) bound for unreduced output fractions is justified. Optional fraction reduction remains polynomial-time.
The algorithm depends on \(B\) through its binary encoding length and never enumerates humans. Since the assigned support size is fixed at \(\tau=1\), this answers the requested complexity question.
The proof applies to arbitrary rational coefficients because it requires only positivity of the denominator on the feasible interval. Consequently, it applies to every promised realizable input without needing to verify realizability.
The rational-threshold decision claim also follows from the exact minimum and polynomial-time rational comparison, including the threshold’s encoding length.
No additional clarification or repair 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.