Answer: —
Theorem 1 — class: hardness
Given peer-type masses \(\mu_t\), assignment-class masses \(\nu_s\), a feasible grading schedule with \(a_{st}\) reviewers of type \(t\) per assignment of class \(s\), diligent reliabilities \(p_t^1\), costs \(c_{ts}\), rewards \(r_{ts}\), and normalized checking budget \(\kappa\), determine the complexity of maximizing the paper’s average lower-bound accuracy over finite measures \(\rho_s\) on \([0,1]\). Each \(\rho_s\) has total mass \(\nu_s\), and \(x\) units of assignment mass receive checking probability \(x\); type \(t\) works diligently on class \(s\) exactly when \(xr_{ts}\ge c_{ts}\). The objective is \(\sum_s\int_0^1\left[1-(1-x)\exp\left(-\frac12\sum_t a_{st}(2p_t^{e_{ts}(x)}-1)^2\right)\right]d\rho_s(x)\), subject to \(\sum_s\int_0^1 x\,d\rho_s(x)\le\kappa\), where \(e_{ts}(x)=1\) when \(xr_{ts}\ge c_{ts}\) and \(0\) otherwise. In particular, determine exact and \(\epsilon\)-approximation complexity in the number of types and classes, input bit length, and precision.
A society is given by its support: the list of the \(\tau\) peer types with positive binary-rational masses \(\mu_t\); \(\tau\) is the support size, not the number of possible types. There are \(m\) assignment classes with positive binary-rational masses \(\nu_s\), with \(\sum_t\mu_t=\sum_s\nu_s=1\).
A fixed feasible grading schedule specifies integer reviewer counts \(a_{st}\ge0\), with \(\sum_t a_{st}=\ell\ge1\) and \(\sum_s\nu_s a_{st}=\ell\mu_t\); feasibility promises distinct reviewers, no self-review, and load \(\ell\) per peer.
Inputs also include binary rationals \(p_t^1\in(1/2,1]\), \(c_{ts},r_{ts}\in[0,1]\), and normalized checking budget \(\kappa\in[0,1]\). Set \(p_t^0=1/2\). Effort is \(e_{ts}(x)=1\) exactly when \(xr_{ts}\ge c_{ts}\), including indifference; otherwise it is \(0\).
Choose nonnegative finite Borel measures \(\rho_s\) on \([0,1]\), with \(\rho_s([0,1])=\nu_s\). Here \(\rho_s(B)\) is the assignment mass receiving checking probabilities in \(B\).
Maximize \(F(\rho)=\sum_{s=1}^m\int_0^1[1-(1-x)\exp(-\tfrac12\sum_{t=1}^{\tau}a_{st}(2p_t^{e_{ts}(x)}-1)^2)]\,d\rho_s(x)\), subject to \(\sum_s\int_0^1x\,d\rho_s(x)\le\kappa\). Write \(\mathrm{OPT}=\sup_\rho F(\rho)\).
Exact computation means deciding \(\mathrm{OPT}\ge q\) for a binary-rational input \(q\in[0,1]\), using ordinary Turing bit complexity and the mathematical exponential. Additive approximation means computing a feasible rational atomic policy with value at least \(\mathrm{OPT}-\epsilon\), for binary-rational \(0<\epsilon<1\). Let \(L\) be the total input bit length.
Is this continuous exact decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
What is the complexity of additive \(\epsilon\)-approximation, with running times stated in \(m,\tau,\ell,L\), and \(\log(1/\epsilon)\) or \(1/\epsilon\)?
Finite-agent optimal spot-checking with this lower-bound objective is reported \(\mathrm{NP}\)-hard by [Wang, An, and Jiang (2018)](https://ojs.aaai.org/index.php/AAAI/article/view/11336); their [2020 extended version](https://www3.ntu.edu.sg/home/boan/papers/IEEETCSS20.pdf) retains this result.
No result settling exactly the measure-valued problem above was located in the literature search.
The additive approximation problem is solvable in
$$
\operatorname{poly}\!\left(m,\tau,L,\log(\ell+1),\log(1/\epsilon)\right)
$$
Turing time, with an exactly feasible rational atomic output supported on at most $m+1$ class-labelled atoms. In particular, no polynomial dependence on $1/\epsilon$ is necessary.
The exact classification is not settled here: I prove decidability, but neither membership in $\mathrm{P}$ nor $\mathrm{NP}$-hardness.
Additional structural results identify the arithmetic issue more precisely:
All reductions below use binary encodings of rationals. If “binary-rational” is interpreted more narrowly as dyadic, the arithmetic comparison problems should likewise be restricted to dyadic inputs; the constructions preserve that restriction.
Define
$$
d_t=(2p_t^1-1)^2,\qquad
A_s(x)=\frac12\sum_{t=1}^{\tau}a_{st}d_t e_{ts}(x),
\qquad
f_s(x)=1-(1-x)e^{-A_s(x)}.
$$
Because $p_t^0=1/2$, these definitions reproduce the given objective. Moreover,
$$
0<d_t\le1,\qquad 0\le A_s(x)\le\frac{\ell}{2}.
$$
For each class, let
$$
B_s=\{0,1\}\cup
\left\{\frac{c_{ts}}{r_{ts}}:
a_{st}>0,\ r_{ts}>0,\ 0<c_{ts}\le r_{ts}
\right\}.
$$
List the distinct elements as
$$
0=b_{s,0}<b_{s,1}<\cdots<b_{s,k_s}=1.
$$
The effort rule includes the following boundary cases:
Consequently, $A_s$ is constant on every interval $[b_{s,i},b_{s,i+1})$ and can only increase at its right endpoint.
For $x$ in such an interval, set
$$
\lambda(x)=\frac{b_{s,i+1}-x}{b_{s,i+1}-b_{s,i}}.
$$
Then
$$
x=\lambda(x)b_{s,i}+(1-\lambda(x))b_{s,i+1}
$$
and
$$
f_s(x)\le
\lambda(x)f_s(b_{s,i})+
(1-\lambda(x))f_s(b_{s,i+1}).
$$
Indeed, $f_s$ is affine on the interval. Its affine continuation to the right endpoint has value at most the actual endpoint value, because the exponent can only increase there.
Thus mass at $x$ may be replaced by these two endpoint masses, preserving checking cost and weakly increasing value. The replacement weights are bounded Borel functions on a finite partition, so integrating them against $\rho_s$ defines a finite atomic measure. Mass already at $1$ is left there.
It follows that the original problem has exactly the same optimum as
$$
\max_{w\in P}\sum_{s,i}w_{s,i}v_{s,i},
\qquad
v_{s,i}=1-(1-b_{s,i})e^{-A_s(b_{s,i})},
$$
where
$$
P=
\left\{
w\ge0:
\sum_iw_{s,i}=\nu_s\ \text{for every }s,\quad
\sum_{s,i}b_{s,i}w_{s,i}\le\kappa
\right\}.
$$
Conversely, each $w\in P$ defines the feasible policy
$$
\rho_s=\sum_iw_{s,i}\delta_{b_{s,i}}.
$$
Let
$$
N=\sum_s|B_s|.
$$
Since every positive integer $a_{st}$ consumes at least one of the $\ell$ reviewer positions,
$$
N\le m\bigl(\min\{\tau,\ell\}+2\bigr).
$$
This bound uses the supplied support only.
Thresholds, exponents, and constraint coefficients are computable using rational arithmetic in polynomial time. Their binary lengths are polynomial in $L$: sums and products involve only polynomially many supplied rationals, and reviewer counts are used in binary.
The polytope $P$ is nonempty, since assigning every class probability $0$ is feasible. It is compact, because
$$
0\le w_{s,i}\le\nu_s.
$$
Its real linear objective therefore attains a maximum at a vertex.
Every vertex is rational. To see this, select a full-rank collection of its active rational constraints; their unique solution is the vertex. Clearing denominators and applying Cramer’s rule also shows that every vertex has polynomial binary length in $L$.
Every vertex has at most $m+1$ positive coordinates. Otherwise, the columns corresponding to its positive coordinates would be linearly dependent in the matrix consisting of the $m$ class-mass rows and the budget row. A nonzero dependence gives a perturbation preserving all those quantities. Sufficiently small perturbations in both directions preserve nonnegativity, contradicting extremality.
Hence an optimal policy exists with at most $m+1$ class-labelled atoms. Since every $\nu_s$ is positive, every class uses at least one atom; at most one class uses two.
The obstacle to exact computation is therefore not the size of an optimal policy’s rational description.
Set
$$
b=\left\lceil\log_2(1/\epsilon)\right\rceil,\qquad
\delta=2^{-b}\le\epsilon,\qquad B=b+1.
$$
For every nonnegative rational $A$, we construct a rational $u(A)$ satisfying
$$
e^{-A}\le u(A)\le e^{-A}+\delta,
\qquad 0<u(A)\le1.
$$
If $A\ge B$, use $u(A)=\delta$. Since $e>2$,
$$
e^{-A}\le e^{-B}<2^{-B}<\delta,
$$
which establishes both required inequalities.
If $A<B$, use
$$
n=8(B+b+1),\qquad
S=\sum_{j=0}^{n-1}\frac{A^j}{j!},
\qquad u(A)=\frac1S.
$$
Taylor’s theorem gives
$$
0\le e^A-S\le e^B\frac{A^n}{n!}.
$$
The inequality
$$
\log(n!)\ge\int_1^n\log t\,dt
=n\log n-n+1
$$
implies $n!\ge(n/e)^n$. Therefore, using $e<4$ and $n\ge8B$,
$$
e^B\frac{A^n}{n!}
\le e^B\left(\frac{eB}{n}\right)^n
\le2^{2B-n}
\le2^{-b}.
$$
Since $1\le S\le e^A$,
$$
0\le\frac1S-e^{-A}
=\frac{e^A-S}{Se^A}
\le\delta.
$$
This construction uses $O(b)$ terms. If $A=a/d$, a common denominator for $S$ is
$$
d^{\,n-1}(n-1)!.
$$
Its bit length, and those of the intermediate numerators, are polynomial in the bit length of $A$ and in $b$. Thus the construction has polynomial bit complexity. The preliminary test $A\ge B$ avoids dependence polynomial in the numerical value of $\ell$.
Replace the objective coefficients by
$$
\widetilde v_{s,i}
=1-(1-b_{s,i})u(A_s(b_{s,i})).
$$
They satisfy
$$
0\le v_{s,i}-\widetilde v_{s,i}\le\delta.
$$
Every feasible vector has total mass $1$, so
$$
0\le
\sum_{s,i}w_{s,i}(v_{s,i}-\widetilde v_{s,i})
\le\delta.
$$
The algorithmic theorem used here is the polynomial-time solvability of rational linear programming: a linear program with rational coefficients can be checked for feasibility and unboundedness, and, when its optimum is finite, an exact rational optimal solution and value can be computed in time polynomial in its binary encoding length. This is the classical Khachiyan theorem; its bit-complexity formulation is also stated in [Adler and Beling’s research paper](https://adler.ieor.berkeley.edu/ilans_pubs/lp_algebraic_stoc_1992.pdf).
Here all constraints and the approximated objective are rational, their total encoding length is polynomial in $L+b$, and feasibility and boundedness were proved above.
For completeness, obtaining an optimal vertex also requires only polynomial work. First compute the rational optimum and restrict to its optimal face. Successively minimize each coordinate over the current face, adding the resulting coordinate equality. Each step retains a nonempty face of $P$. After all coordinates have been fixed, the face is a singleton and hence a vertex of $P$. Coordinate minima are attained at vertices of $P$, so their bit lengths satisfy the polynomial bounds already proved. There are only $N$ additional rational LP calls.
Let $\widetilde w$ be the resulting vertex and $\widetilde{\mathrm{OPT}}$ its approximated objective value. Then
$$
\widetilde{\mathrm{OPT}}
\le\mathrm{OPT}
\le\widetilde{\mathrm{OPT}}+\delta,
$$
and its actual value satisfies
$$
F(\widetilde\rho)
\ge\widetilde{\mathrm{OPT}}
\ge\mathrm{OPT}-\epsilon.
$$
The policy is exactly feasible because the constraints were never approximated.
The running time is
$$
\operatorname{poly}\!\left(
m,\tau,L,\log(\ell+1),
\left\lceil\log_2(1/\epsilon)\right\rceil
\right),
$$
with at most $m(\min\{\tau,\ell\}+2)$ LP variables. Since $L$ accounts for the supplied arrays and binary reviewer counts, this is also
$$
\operatorname{poly}\!\left(L+\log(1/\epsilon)\right).
$$
If the accuracy input’s encoding is excluded from $L$, its encoding length must additionally be included.
The output uses at most $m+1$ atoms. Their positions and masses have polynomial bit length in the original constraint encoding, independently of the precision used for the objective.
Let $V(k)$ denote the optimum when the budget is $k\in[0,1]$, with all other data fixed.
First, $f_s$ is strictly increasing. If $x<y$, then $A_s(y)\ge A_s(x)$, and
$$
\begin{aligned}
f_s(y)-f_s(x)
&=(y-x)e^{-A_s(x)}
+(1-y)\bigl(e^{-A_s(x)}-e^{-A_s(y)}\bigr)\\
&\ge(y-x)e^{-\ell/2}>0.
\end{aligned}
$$
For each class, form the upper boundary $H_s$ of the convex hull of
$$
\{(b_{s,i},v_{s,i})\}_i.
$$
For a normalized class mean checking probability $y$, this boundary is exactly the maximum class value obtainable by mixing the endpoint policies. Indeed, all attainable mean-value pairs form that convex hull.
Write the upper-hull vertices as
$$
(x_{s,0},h_{s,0}),\ldots,(x_{s,J_s},h_{s,J_s}),
\qquad x_{s,0}=0,\quad x_{s,J_s}=1.
$$
The segment slopes
$$
\alpha_{s,j}
=\frac{h_{s,j}-h_{s,j-1}}{x_{s,j}-x_{s,j-1}}
$$
are nonincreasing by concavity and satisfy
$$
\alpha_{s,j}\ge e^{-\ell/2}>0.
$$
Their budget capacities are the rational numbers
$$
C_{s,j}=\nu_s(x_{s,j}-x_{s,j-1}).
$$
Their total is $1$.
Increasing a class mean traverses its hull segments in order. Its value increase is slope times budget allocated to each segment. Temporarily dropping the within-class ordering constraints gives a fractional-knapsack problem.
Sort all segments by nonincreasing slope, placing earlier segments of a class first when slopes tie. Filling this order automatically respects every within-class ordering constraint, since that class’s slopes are nonincreasing. It therefore yields a feasible solution to the original problem.
To verify optimality, suppose the greedy allocation has one partially filled segment of slope $\lambda$. Earlier segments are full and later segments are empty. For any competing allocation $t$ with the same total budget, subtracting objectives gives
$$
\sum_j(\alpha_j-\lambda)(t_j^{\mathrm{greedy}}-t_j)\ge0.
$$
Each summand is nonnegative: earlier segments have both factors nonnegative, later segments have both factors nonpositive, and the partially filled segment has first factor zero. At a boundary, the same argument applies using an adjacent marginal slope. Positive slopes also imply that an optimum uses the full budget.
There are
$$
K=\sum_sJ_s\le N-m\le m(\min\{\tau,\ell\}+1)
$$
segments. In the sorted order, let their slopes and capacities be $\alpha_j,C_j$, and put
$$
T_0=0,\qquad T_j=\sum_{i=1}^jC_i.
$$
Then for $T_{r-1}\le k\le T_r$,
$$
V(k)=V(0)+\sum_{j<r}\alpha_jC_j
+\alpha_r(k-T_{r-1}).
$$
Thus $V$ is concave and piecewise affine with at most $K$ segments. Every $T_j$ is rational and has polynomial bit length, being a sum of polynomially many products of input masses and rational threshold differences.
This also gives a direct explanation of the atom bound: only the class containing the partially filled segment needs to mix two hull vertices.
Limitation. Computing this description exactly still requires ordering its exponential expressions. The polynomial number of segments does not resolve those comparisons.
I use the following form of Lindemann–Weierstrass: if $\beta_1,\ldots,\beta_n$ are distinct algebraic numbers, then $e^{\beta_1},\ldots,e^{\beta_n}$ are linearly independent over the algebraic numbers. A self-contained proof is available in [Popescu’s paper](https://arxiv.org/abs/2306.14352).
For any rational atomic policy, group atoms having the same exponent:
$$
F(\rho)=1-\sum_{r\in R}\gamma_r e^{-r},
\qquad
\gamma_r=\sum_{\substack{\text{atoms }(s,x)\\A_s(x)=r}}
w_{s,x}(1-x).
$$
Here $r,\gamma_r$ are nonnegative rationals. The hypotheses of the theorem hold because the grouped arguments $-r$ are distinct rational, hence algebraic, numbers.
Consequently, two rational atomic policies have equal values if and only if all their grouped coefficients $\gamma_r$ agree, interpreting missing coefficients as zero. Computing effort, grouping rational exponents, and checking these coefficients takes polynomial time in the encoded instances and policies.
Furthermore, if any $r>0$ has $\gamma_r>0$, the policy value is transcendental. Otherwise an algebraic value of $F(\rho)$ would give a nonzero algebraic linear relation among $e^0$ and the $e^{-r}$.
If all positive-exponent coefficients vanish, then
$$
F(\rho)=1-\gamma_0
=\sum_{s,x}w_{s,x}x,
$$
because the total atom mass is $1$.
If $\kappa=1$, checking everything gives $\mathrm{OPT}=1$.
If $\kappa=0$, nonnegative checking cost forces every class measure to be supported at $0$. Therefore
$$
\mathrm{OPT}=\sum_s\nu_s(1-e^{-A_s(0)}).
$$
It equals $0$ if every $A_s(0)=0$, and is transcendental otherwise.
Now suppose $0<\kappa<1$. Say an effective reviewer is inducible below $1$ if some pair satisfies
$$
a_{st}>0,\qquad c_{ts}=0\ \text{or}\ c_{ts}<r_{ts}.
$$
If no such pair exists, $A_s(x)=0$ for every $x<1$, while $f_s(1)=1$. Thus $f_s(x)=x$ everywhere and
$$
\mathrm{OPT}=\kappa.
$$
If such a pair exists, then $\mathrm{OPT}>\kappa$. Start with
$$
\rho_s=\nu_s\bigl((1-\kappa)\delta_0+\kappa\delta_1\bigr).
$$
Its cost is $\kappa$ and its value is
$$
\kappa+(1-\kappa)\sum_s\nu_sf_s(0).
$$
This exceeds $\kappa$ if any scheduled effort is free.
Otherwise, some class has a threshold $z\in(0,1)$ with $A_s(z)>0$. Choose $h>0$ sufficiently small that
$$
h(1-z)\le\nu_s(1-\kappa),\qquad
hz\le\nu_s\kappa.
$$
Replace masses $h(1-z)$ at $0$ and $hz$ at $1$ by mass $h$ at $z$. This preserves cost and increases value by
$$
h(f_s(z)-z)
=h(1-z)(1-e^{-A_s(z)})>0.
$$
At a rational optimal vertex, a value exceeding $\kappa$ requires a positive-exponent coefficient, since otherwise the value would equal its checking cost. Hence this optimum is transcendental.
Finally, every feasible policy of checking cost $C$ satisfies
$$
F(\rho)
\le1-e^{-\ell/2}(1-C)
\le1-(1-\kappa)e^{-\ell/2}.
$$
This is strictly below $1$ when $\kappa<1$.
The classification is therefore:
| Case | Optimum |
|---|---|
| $\kappa=1$ | $1$ |
| $\kappa=0$, all $A_s(0)=0$ | $0$ |
| $\kappa=0$, some $A_s(0)>0$ | Transcendental |
| $0<\kappa<1$, no effective reviewer inducible below $1$ | $\kappa$ |
| $0<\kappa<1$, some effective reviewer inducible below $1$ | Transcendental, strictly between $\kappa$ and $1$ |
All the rational cases are recognizable by rational input comparisons.
Handle those rational cases directly. In every other case, the rational query $q$ differs from $\mathrm{OPT}$.
Run the approximation algorithm at successively finer precisions, obtaining
$$
\widetilde{\mathrm{OPT}}
\le\mathrm{OPT}
\le\widetilde{\mathrm{OPT}}+2^{-b}.
$$
Return yes when $q\le\widetilde{\mathrm{OPT}}$ and no when
$q>\widetilde{\mathrm{OPT}}+2^{-b}$.
Since
$$
\Delta=|\mathrm{OPT}-q|>0,
$$
one of these conditions holds once $2^{-b}<\Delta$. Doubling $b$ gives total running time polynomial in
$$
m,\tau,L,\log(\ell+1),1+\log(1/\Delta).
$$
This proves exact decidability, and polynomial time under an explicit inverse-exponential gap promise. It does not give an unconditional input-length polynomial bound.
Indeed, take two equally weighted classes, two types of masses $1/2$, and $\ell=2^n$. Schedule only perfect, free-effort reviewers in the first class and only never-effort reviewers in the second. With $\kappa=0$,
$$
\mathrm{OPT}=\frac12(1-e^{-2^{n-1}}).
$$
For $q=1/2$,
$$
\Delta=\frac12e^{-2^{n-1}},
$$
although the instance has length $O(n)$. The schedule is feasible by the realization argument below. Thus a uniform bound $\Delta\ge2^{-\operatorname{poly}(L)}$ is false. This particular comparison is nevertheless easy by positivity.
Define positive exponential-sum comparison as follows: given positive rational $\lambda_s$ with total $1$, nonnegative rational $z_s$, and rational $h\in[0,1]$, decide
$$
\sum_s\lambda_s e^{-z_s}\le h.
$$
The zero-budget restriction reduces to this problem immediately:
$$
\mathrm{OPT}=1-\sum_s\nu_s e^{-A_s(0)},
$$
so use $\lambda_s=\nu_s$, $z_s=A_s(0)$, and $h=1-q$.
I now prove the converse reduction, including all input entries and the feasibility promise.
For each source exponent, write
$$
z_s=\frac{k_s}{2}+f_s,\qquad
k_s=\lfloor2z_s\rfloor,\qquad
0\le f_s<\frac12.
$$
If $k_s>0$, create an effective type dedicated to class $s$, with perfect reliability and reviewer count $k_s$.
If $f_s>0$, write $f_s=u_s/v_s$. Then
$$
2f_s=\frac{2u_sv_s}{v_s^2},
\qquad 2u_sv_s<v_s^2.
$$
Expand the integer $2u_sv_s$ in binary. A set bit at position $2j$ contributes
$$
\left(\frac{2^j}{v_s}\right)^2;
$$
a set bit at position $2j+1$ contributes twice this square.
For each contribution, create a dedicated type with reliability
$$
p_t^1=\frac{1+2^j/v_s}{2}
$$
and reviewer count $1$ or $2$, respectively. A contributing bit satisfies
$$
2^{2j}\le2u_sv_s<v_s^2,
$$
so $0<2^j/v_s<1$ and the reliability is admissible.
For every effective type, put $c_{ts}=r_{ts}=0$ in its dedicated class. It therefore exerts effort at $0$. The resulting exponent contribution is exactly
$$
\frac{k_s}{2}+f_s=z_s.
$$
Let $D_s$ be the total effective reviewer count. Its integer part is $k_s$; its remaining part is polynomial in the source encoding length. Thus $D_s$ has polynomial binary length.
Choose a power of two $\ell>\max_sD_s$. Create one filler type with reliability $1$, with count $\ell-D_s$ in class $s$, and which never exerts effort.
Complete the input arrays explicitly as follows:
Thus filler and unscheduled pairs have valid parameters. Identical peer types, if any arise, may be merged by adding their reviewer counts and masses.
Set
$$
\nu_s=\lambda_s,\qquad
\mu_t=\frac1\ell\sum_s\nu_s a_{st}.
$$
Every retained type has positive mass. Moreover,
$$
\sum_t\mu_t
=\frac1\ell\sum_s\nu_s\sum_ta_{st}
=1,
$$
and the balance equations hold by definition.
The construction has polynomial support size and total binary encoding length. For source exponents in $[0,1/2]$, even the numerical value of $\ell$ is polynomially bounded. For unrestricted exponents, its binary length remains polynomial. If the source rationals are dyadic, all constructed input parameters are dyadic.
In fact, any rational schedule satisfying the balance equations admits a finite realization after sufficiently enlarging the population.
Choose a population size making all type and class counts integral. Give every peer $\ell$ outgoing reviewer stubs. Give each assignment in class $s$ exactly $a_{st}$ incoming stubs labelled by type $t$. For each type, balance makes the total incoming and outgoing stub counts equal, so they can be matched. This creates an $\ell$-regular bipartite multigraph.
An $\ell$-regular bipartite multigraph decomposes into $\ell$ perfect matchings. Indeed, for any subset $U$ on one side,
$$
\ell|U|\le\ell|N(U)|,
$$
so Hall’s condition holds. Remove a perfect matching and repeat on the remaining regular multigraph.
Colour these matchings by $1,\ldots,\ell$. Replace every peer and its owned assignment by $\ell+1$ clones indexed modulo $\ell+1$. Lift an edge of colour $j$ from peer clone $k$ to assignment clone $k+j$.
Each clone has incoming and outgoing degree $\ell$. Every assignment clone retains its prescribed reviewer-type counts. Parallel base edges have different colours, hence different shifts, so no reviewer clone reviews the same assignment clone twice. A base self-edge has a nonzero shift and therefore never becomes self-review. A base edge between different owners cannot become self-review.
This verifies the feasibility promise without requiring the potentially large realizing population to be output.
Set $\kappa=0$ and $q=1-h$. Then
$$
\mathrm{OPT}
=1-\sum_s\lambda_s e^{-z_s},
$$
and hence
$$
\mathrm{OPT}\ge q
\quad\Longleftrightarrow\quad
\sum_s\lambda_s e^{-z_s}\le h.
$$
This proves polynomial-time equivalence of the zero-budget restriction and positive exponential-sum comparison. The constructed instances have no interior effort thresholds: all scheduled effective reviewers always exert effort, and fillers never do.
Taking one source term shows that scalar comparison of $e^{-z}$ with a rational is already embedded with $m=1$.
No hardness classification for this arithmetic comparison problem is proved here.
The hull construction in Section 4 requires only restricted signed exponential comparisons.
For endpoints $i<j$ within a class, the slope is
$$
\frac{v_{s,j}-v_{s,i}}{b_{s,j}-b_{s,i}}
=
\frac{
(1-b_{s,i})e^{-A_s(b_{s,i})}
-(1-b_{s,j})e^{-A_s(b_{s,j})}
}{
b_{s,j}-b_{s,i}
}.
$$
Thus:
All coefficients and arguments are rational with polynomial bit length. A standard stack construction of each upper hull, followed by sorting its segments, uses $O(N\log N)$ such comparisons.
After greedy allocation, the resulting optimal policy has at most $m+1$ atoms. Its final comparison with $q$ is
$$
\sum_r\gamma_r e^{-r}\le1-q,
\qquad \gamma_r\ge0,
$$
with at most $m+1$ grouped terms. If $G=\sum_r\gamma_r>0$, divide by $G$ to obtain a positive exponential-sum comparison; if the resulting threshold exceeds $1$, the answer is immediate. If $G=0$, the policy value is $1$.
Consequently, exact decision admits a polynomial-time Turing reduction to:
Equality in the signed comparisons is itself recognizable by grouping arguments and applying Lindemann–Weierstrass. Their strict ordering remains an arithmetic issue.
The published reduction chooses a subset of indivisible assignments, and its displayed reliability construction uses logarithms and square roots. These features are visible in [Wang, An, and Jiang, Section IV-A](https://www3.ntu.edu.sg/home/boan/papers/IEEETCSS20.pdf). Therefore that reduction does not directly supply a reduction respecting both the rational input restriction and divisible assignment masses here.
Divisibility changes the optimum even in a small example. Take one class of mass $1$, one perfect reviewer, threshold $1/2$, and budget $1/4$. Every feasible policy concentrated at one checking probability has value at most $1/4$, because its probability is below the effort threshold.
The feasible measure
$$
\rho=\frac12\delta_0+\frac12\delta_{1/2}
$$
instead has value
$$
\frac12-\frac14e^{-1/2}>\frac14.
$$
The strict inequality follows from $e^{-1/2}<1$. Thus the whole-assignment selection argument does not transfer unchanged.
Additive approximation is fully established in polynomial time in $L+\log(1/\epsilon)$, with exact feasibility and a polynomial-size rational atomic output.
For exact decision, the proved results are finite reduction, attainment, polynomial-size rational optimal policies, decidability, a polynomial-size parametric budget description, and the arithmetic reductions above. They do not establish either requested exact-complexity classification.
⟨structured verdict parsed — rendered above⟩
The output is a correct partial solution. Its approximation theorem and supporting structural results withstand verification. It does not settle whether exact decision belongs to $\mathrm{P}$ or is $\mathrm{NP}$-hard, and explicitly acknowledges this limitation.
I found no false mathematical step in the results actually claimed as proved. The blocking issue is incomplete resolution of the exact-complexity question.
Verified.
The definitions of $d_t$, $A_s(x)$, and $f_s(x)$ reproduce the objective because effort zero contributes
$$
(2p_t^0-1)^2=0.
$$
The bounds
$$
0<d_t\le1,\qquad 0\le A_s(x)\le\ell/2
$$
follow from the reliability range and the reviewer-count sum.
The threshold set correctly handles all relevant cases:
On each half-open interval between thresholds, $A_s$ is constant and $f_s$ is affine. At the right endpoint, effort can increase, so the actual endpoint value is at least the affine continuation. This proves the stated endpoint-mixture inequality, including thresholds at $1$.
The replacement preserves both class mass and checking cost. Its weights are bounded Borel functions, so the integration argument applies to arbitrary finite Borel measures, not merely atomic measures.
The reverse inclusion follows directly from interpreting feasible LP weights as atomic measures. Consequently, the finite LP and the continuous problem have the same optimum.
The variable bound
$$
N\le m(\min\{\tau,\ell\}+2)
$$
is valid: each scheduled type consumes at least one reviewer position, and contributes at most one additional threshold.
Verified.
The finite polytope is nonempty and compact. Its objective has real coefficients but is still a continuous linear functional, so an optimal vertex exists.
Rational active constraints determine rational vertices. The invoked determinant argument gives polynomial vertex encoding length because the constraint matrix has polynomial dimension and rational coefficients of polynomial encoding length.
The positive-coordinate perturbation argument is valid. More than $m+1$ positive coordinates produces a nonzero dependence preserving every class mass and the budget quantity. Small perturbations in either direction remain feasible, contradicting extremality.
Thus an optimal policy has at most $m+1$ class-labelled atoms. Positivity of every class mass ensures that at most one class needs two atoms.
These are existence and representation-size results; they do not provide a polynomial-time method for optimizing the exact transcendental objective.
Verified, including constants and precision dependence.
For the large-exponent branch, $A\ge B=b+1$ implies
$$
e^{-A}<2^{-B}<\delta.
$$
Hence $u(A)=\delta$ satisfies both required one-sided inequalities.
For the Taylor branch, the remainder bound applies because $0\le A<B$. The factorial estimate and the choices of $n$ and $B$ give
$$
e^B\frac{A^n}{n!}
\le 2^{2B-n}
\le 2^{-b}.
$$
The reciprocal approximation is also correctly bounded, since $S\ge1$:
$$
0\le \frac1S-e^{-A}\le e^A-S\le\delta.
$$
The case $A=0$ gives $S=1$ and zero error.
The common denominator displayed for $S$ is valid, and its bit length is polynomial in the exponent encoding length and $b$. The large-exponent cutoff prevents a running time polynomial in the numerical value of $\ell$.
The coefficient error has the correct direction:
$$
0\le v_{s,i}-\widetilde v_{s,i}\le\delta.
$$
Total feasible mass is $1$, so this bounds the entire objective error by $\delta$, without an extra factor of $N$.
The rational LP theorem is applicable: the approximated objective and all constraints are rational, and feasibility and boundedness have been established. The cited [Adler–Beling paper](https://adler.ieor.berkeley.edu/ilans_pubs/lp_algebraic_stoc_1992.pdf) confirms the ordinary binary-encoding polynomial-time result for rational LPs.
The successive coordinate minimizations retain faces of the original polytope and ultimately yield an optimal vertex. Therefore the atom bound and the precision-independent bound on output masses remain valid.
The guarantee
$$
F(\widetilde\rho)\ge\mathrm{OPT}-\epsilon
$$
and exact feasibility follow as written.
The runtime claim
$$
\operatorname{poly}\!\left(m,\tau,L,\log(\ell+1),\log(1/\epsilon)\right)
$$
is justified, subject to the explicitly stated inclusion of the accuracy input’s encoding length. No polynomial dependence on $1/\epsilon$ is required.
Verified as a structural result.
The displayed calculation proves strict increase of every $f_s$, with the stated lower bound. Consecutive upper-hull vertices therefore have positive slopes bounded below by $e^{-\ell/2}$.
The convex-hull interpretation correctly describes mixtures of endpoint policies. Combined with the earlier endpoint domination, it determines the continuous optimum as well.
Within each class, hull slopes are nonincreasing. Sorting all segments by slope, with the prescribed tie handling, respects class order. The exchange inequality correctly verifies optimality against allocations of the same budget. Positive slopes justify using the entire budget.
The segment count and rationality of the budget breakpoints follow. Their encoding lengths remain polynomial even though selecting their order may require difficult comparisons.
The prover correctly distinguishes polynomial description size from polynomial-time exact construction.
Verified.
The stated Lindemann–Weierstrass theorem is correct. Its hypotheses are satisfied by distinct grouped rational exponents and rational coefficients. The theorem’s stated form agrees with [Popescu’s paper](https://arxiv.org/abs/2306.14352).
Grouping coefficients therefore decides equality of two feasible rational atomic policy values in polynomial time.
The transcendence argument is also valid: a nonzero positive-exponent coefficient would otherwise produce a nontrivial algebraic linear relation involving the corresponding exponentials and $e^0$.
The optimum classification handles the boundary budgets correctly:
The upper bound
$$
F(\rho)\le1-(1-\kappa)e^{-\ell/2}
$$
has the correct direction and is strictly less than $1$ for $\kappa<1$.
Recognizing the rational cases before refining approximation intervals removes the equality obstruction. In every remaining case, the rational query differs from the transcendental optimum, so the refinement algorithm terminates.
The small-gap example is correctly computed and has binary encoding length $O(n)$. It disproves a universal inverse-exponential gap bound in input length. As acknowledged, it does not establish hardness or rule out another polynomial-time exact algorithm.
Verified.
The forward reduction follows directly from the zero-budget objective.
For the converse construction, a binary bit of $2u_sv_s$ at an even position contributes one square; a bit at an odd position contributes twice that square. The constructed reviewer counts and reliabilities therefore realize the fractional exponent exactly.
The bound
$$
2^{2j}<v_s^2
$$
ensures admissible reliability. The integer exponent component is realized by perfect reviewers with count $k_s$.
Choosing a power-of-two $\ell$ larger than every effective reviewer count ensures strictly positive filler counts. The resulting masses are positive, normalized, and satisfy the balance equations.
The number of types, full array size, and binary lengths are polynomial in the source encoding. The dyadic-preservation claim is valid because division by the chosen $\ell$ preserves dyadic masses.
The decision equivalence has the correct inequality direction.
Verified.
After clearing denominators, the stub counts balance separately for each type. Matching them produces an $\ell$-regular bipartite multigraph.
The displayed neighborhood inequality establishes Hall’s condition; repeated perfect-matching removal gives the edge coloring used in the lift.
The clone construction preserves reviewer types and all degrees. Distinct colors give distinct shifts, eliminating repeated reviewer-assignment pairs. Nonzero shifts eliminate base self-edges, and edges between different owners cannot become self-review.
A potentially enormous realizing population need not be output, so its size does not invalidate the reduction’s polynomial encoding bound.
Verified.
The slope expression is correct. Comparisons of adjacent slopes use at most three exponential terms; comparisons of arbitrary segment slopes use at most four.
Hull construction and sorting need only polynomially many such comparisons. After allocation, the final policy comparison is a positive exponential-sum comparison after grouping and, when appropriate, normalization.
This is a polynomial-time oracle reduction, not an unconditional polynomial-time algorithm. The output makes that distinction correctly.
Verified within the stated scope.
The cited finite-agent construction selects assignments through a knapsack subset and displays logarithms and a square root in its reliability formula. These features appear in [Section IV-A of the extended paper](https://www3.ntu.edu.sg/home/boan/papers/IEEETCSS20.pdf), supporting the claim that this reduction does not directly meet the present input and divisibility requirements.
The illustrative mixture has cost $1/4$ and value
$$
\frac12-\frac14e^{-1/2}>\frac14.
$$
A policy concentrated at one feasible checking probability remains below the effort threshold and has value at most $1/4$.
This establishes the stated distinction. It does not exclude every possible adaptation of finite-agent hardness, and the prover does not claim otherwise.
Major — the requested exact classification remains unresolved.
Sections 5–7 establish decidability and arithmetic reductions, but neither a polynomial-time exact decision algorithm nor an $\mathrm{NP}$-hardness reduction.
No clarification alone repairs this incompleteness. A further round needs one of the following substantive results:
The approximation theorem and verified structural results can be retained. The exponential-sum equivalence identifies a concrete remaining arithmetic problem, but does not classify its complexity.
⟨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.