Answer: —
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet sc be the probability of success for column c as before. Let µc be the expected number of inspections that column c incurs if its entries are inspected in increasing or- der of their probability of success, conditioning on the event that column c is inspected and infeasible.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many types \(T\) with masses \(\mu_t\), options \(c\in C\), and rates \(\lambda_{tc}>0\), place independent Poisson failure processes of rate \(\lambda_{tc}\) on each type-mass interval of length \(\mu_t\), for every option \(c\). Find a fixed measurable scan order over the type-mass intervals for all options that minimizes expected total scanned mass until an option is certified failure-free or every option is rejected. This is the limit of finite instances with \(n_t/N\to\mu_t\), per-agent failure probabilities \(\lambda_{tc}/N\), and inspection cost normalized by \(N\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass \(\mu_t\) a binary rational; \(\tau\) is the support size, not the number of possible types. Assume \(\sum_t\mu_t=1\), \(\tau\geq1\), and \(m=|C|\geq1\). Each rate \(\lambda_{tc}>0\) is a binary rational; \(L\) is the total input bit length.
For every \((t,c)\), take a separate interval \(I_{tc}=[0,\mu_t)\) carrying a homogeneous Poisson point process of intensity \(\lambda_{tc}\); all these processes are mutually independent. An option is feasible exactly when its intervals contain no failure points.
A fixed measurable scan order is a measure-preserving measurable bijection, modulo null sets, from \([0,m)\) onto the disjoint union of the \(I_{tc}\). It is chosen before observing failures, may interleave options and split type intervals, and scans each point once.
Scanning reveals encountered failure points. Reject an option at its first revealed failure and skip all its remaining mass at zero cost. Certify an option as failure-free once all its mass has been scanned without failure, with certification understood almost surely. Stop at the first certification or when every option is rejected.
The cost is total mass actually scanned, counted separately for each option; minimize its expectation over fixed measurable scan orders. The only dependence on observations is rejection, skipping, and stopping.
Is finding an optimal fixed measurable scan order solvable in polynomial time in \(m,\tau,L\), or is this optimization problem NP-hard?
For finite matrices of mutually independent Bernoulli entries with success probabilities strictly between \(0\) and \(1\), an optimal fixed inspection permutation with unit inspection costs and the same skipping and stopping rules can be found in polynomial time. [Lee and Goel](https://www.ijcai.org/Proceedings/16/Papers/053.pdf)
No result settling this exact continuous Poisson scan problem was located in the literature search.
I do not settle whether the stated optimization problem is polynomial-time solvable or NP-hard.
The new result is a polynomial-time reduction showing that its priority comparisons can encode arbitrary rational exponential-sum sign comparisons, even with only two options having the same feasibility probability.
More precisely, define the following auxiliary problem: given binary-encoded rationals $a_i,q_i$, determine the sign of
$$ F=\sum_{i=1}^{n}a_i e^{q_i}. $$
I prove:
This strengthens the characterization in the notes: the restricted priority formulas have the full comparison power of explicit rational exponential sums.
Throughout, “binary rational” means a rational represented by a binary numerator and denominator, as in the bit model used in the notes.
I first prove the structural results needed for the reduction.
Fix an admissible scan and pull its intervals back to the parameter interval $[0,m)$. Let $E_c$ be the measurable set of positions assigned to option $c$. These sets partition $[0,m)$ modulo null sets, and each has Lebesgue measure $1$.
Define
$$ X_c(s)=\operatorname{Leb}(E_c\cap[0,s)), \qquad b_c=\inf\{s:X_c(s)=1\}. $$
The function $X_c$ is continuous and nondecreasing, with $X_c(0)=0$ and $X_c(m)=1$. Consequently, $b_c$ exists and $X_c(b_c)=1$.
The map $s\mapsto X_c(s)$ compresses option $c$ into its local scan order on $[0,1)$. Here are the measure-theoretic details.
Under Lebesgue measure restricted to $E_c$, the cumulative distribution function of the scan position is $X_c$. This distribution has no atoms, so the cumulative-distribution transformation sends it to uniform measure on $[0,1)$. Moreover, if two distinct positions have the same cumulative value, $X_c$ is constant between them. Nontrivial plateau interiors form a countable family; their intersections with $E_c$, together with their endpoints, have measure zero. Outside these sets, the map is injective, and a generalized inverse supplies a measurable inverse. Thus compression is a measure-preserving bijection modulo null sets.
The failure intensity measures are absolutely continuous with respect to Lebesgue measure. There are almost surely finitely many failures, since the sum of all interval intensities is finite. Hence failures almost surely avoid the discarded null sets, and compression preserves their local order.
For a failure realization outside this null event, let $Z_c$ denote the cost of inspecting option $c$ alone in its compressed order: its first failure’s local position if it is infeasible, and $1$ if it is feasible.
Order options so that
$$ b_1\leq b_2\leq\cdots\leq b_m, $$
breaking ties deterministically, and concatenate their compressed local orders.
If at least one option is feasible, let $j$ be the first feasible option in this sequence. The concatenated scan costs
$$ \sum_{i<j}Z_i+1. $$
The original scan first certifies an option at position $b_j$. By that position, each earlier option has encountered its first failure and incurred cost $Z_i$, and option $j$ has incurred cost $1$. Any other inspected mass contributes a nonnegative additional cost. Therefore, the original scan costs at least the displayed quantity.
If all options are infeasible, both scans incur exactly $\sum_c Z_c$.
Thus serialization cannot increase cost, pathwise outside a null event. Taking expectations proves the claim.
Consider one option in a local order with rate function $r(x)$ on $[0,1)$. Write
$$ H(x)=\int_0^x r(u)\,du. $$
The Poisson void probability gives
$$ \Pr(Z>x)=e^{-H(x)} $$
for almost every $x\in[0,1)$. The tail-integral identity therefore gives its expected inspection cost
$$ A=\mathbb E[Z]=\int_0^1 e^{-H(x)}\,dx. $$
Its feasibility probability is
$$ p=e^{-H(1)} =\exp\left(-\sum_t\mu_t\lambda_{tc}\right), $$
independently of the local order.
For a prefix of mass $x$, let $y_t$ be the amount inspected from type $t$. Then
$$ 0\leq y_t\leq\mu_t, \qquad \sum_t y_t=x, \qquad H(x)=\sum_t\lambda_{tc}y_t. $$
This last expression is maximized by filling types in decreasing rate order. Indeed, if a lower-rate type has positive allocated mass while a higher-rate type has unused mass, transferring mass to the higher-rate type increases the expression. Filling successive types by this rule produces the decreasing-rate prefix.
Let $H^\downarrow$ be the cumulative hazard in decreasing rate order. We have, for every $x$,
$$ H^\downarrow(x)\geq H(x). $$
Consequently,
$$ \int_0^1e^{-H^\downarrow(x)}\,dx \leq \int_0^1e^{-H(x)}\,dx. $$
Decreasing rate order therefore minimizes $A$ while preserving $p$.
Let $A_c$ be the minimum expected inspection cost of option $c$, attained by decreasing rate order, and let $p_c$ be its feasibility probability.
For a block permutation $\sigma$, independence between options gives expected total cost
$$ \mathcal C(\sigma) = \sum_{j=1}^m A_{\sigma(j)} \prod_{i<j}(1-p_{\sigma(i)}). $$
Reaching a block means that all previous options are infeasible. This event is independent of that block’s inspection cost, which justifies the formula.
For adjacent options $c,d$, the conditional expected costs of their two orders are
$$ A_c+(1-p_c)A_d \quad\text{and}\quad A_d+(1-p_d)A_c. $$
Their difference is
$$ A_cp_d-A_dp_c. $$
The probabilities of proceeding past both options agree, so subsequent contributions cancel. Since every $p_c>0$, define
$$ K_c=\frac{A_c}{p_c}. $$
The adjacent exchange favors $c$ before $d$ precisely when $K_c\leq K_d$. Repeated exchanges remove all inversions without increasing expected cost.
Combining the preceding arguments proves:
Optimal-scan theorem. An optimal scan exists as a permutation of the original type intervals. Within each option, order types by decreasing rate; order the resulting option blocks by increasing $K_c$.
To express $K_c$, let the decreasing rates and corresponding masses be $r_{ic}$ and $\ell_{ic}$, and define suffix hazards
$$ S_{ic}=\sum_{j=i}^{\tau}r_{jc}\ell_{jc}, \qquad S_{\tau+1,c}=0. $$
Integration within each constant-rate segment gives
$$ K_c= \sum_{i=1}^{\tau} \frac{e^{S_{ic}}-e^{S_{i+1,c}}}{r_{ic}}. $$
Thus each comparison $K_c-K_d$ is a rational linear combination of at most $2\tau+2$ exponentials of rational numbers. All its rational data have polynomial bit length: they are obtained by polynomially many rational products, sums, and reciprocals of the input data.
This is the new reduction.
Start with
$$ F=\sum_{i=1}^{n}a_i e^{q_i}, \qquad a_i,q_i\in\mathbb Q. $$
Group equal exponents and remove zero coefficients. If no terms remain, return sign zero directly. Otherwise, define
$$ f(z)=\sum_{i=1}^{n}a_i e^{q_i z}, \qquad \alpha=\max\{0,-\min_i q_i\}. $$
Set
$$ g(z)=e^{\alpha z}(e^z-1)^2f(z). $$
Expanding and grouping terms produces
$$ g(z)=\sum_{s\in T}b_s e^{sz}, $$
where $T$ contains at most $3n$ distinct nonnegative rational exponents, and every $b_s$ is rational.
Because $(e^z-1)^2$ has a zero of order two at zero,
$$ \sum_{s\in T}b_s=g(0)=0, \qquad \sum_{s\in T}s b_s=g'(0)=0. $$
On the other hand,
$$ g(1)=e^\alpha(e-1)^2F. $$
The multiplying factor is strictly positive, so $g(1)$ has the same sign as $F$.
Let
$$ H=\max T. $$
After zero coefficients have been removed, $H>0$. In fact, the largest exponent arising from the largest exponent of $f$ plus the shift and $2$ has a nonzero coefficient: it cannot be canceled by any lower shifted term.
For $0\leq y<H$, define
$$ u(y) = 1+ \sum_{\substack{s\in T\\s>0,\ b_s>0}} b_s\,\mathbf 1_{[0,s)}(y), $$
and
$$ v(y) = 1+ \sum_{\substack{s\in T\\s>0,\ b_s<0}} (-b_s)\,\mathbf 1_{[0,s)}(y). $$
Both functions are positive, nonincreasing step functions with rational values and rational breakpoints.
Their difference is
$$ u(y)-v(y) = \sum_{\substack{s\in T\\s>0}} b_s\,\mathbf 1_{[0,s)}(y). $$
Using the first-moment identity,
$$ \int_0^H(u(y)-v(y))\,dy = \sum_{s\in T}s b_s = 0. $$
Hence they have a common positive rational integral
$$ D = \int_0^H u(y)\,dy = \int_0^H v(y)\,dy. $$
Explicitly,
$$ D = H+\sum_{\substack{s\in T\\b_s>0}}b_s s. $$
Normalize them:
$$ \rho_1(y)=\frac{u(y)}D, \qquad \rho_2(y)=\frac{v(y)}D. $$
Each $\rho_c$ is positive and nonincreasing, with integral $1$.
Their exponential-integral difference is
$$ \begin{aligned} \int_0^H e^y(\rho_1(y)-\rho_2(y))\,dy &= \frac1D \sum_{\substack{s\in T\\s>0}}b_s(e^s-1)\\ &= \frac1D\sum_{s\in T}b_s e^s\\ &=\frac{g(1)}D. \end{aligned} $$
The second equality uses $\sum_s b_s=0$, including the coefficient at exponent zero if present.
For each $c\in\{1,2\}$, define
$$ x_c(y)=\int_y^H\rho_c(z)\,dz. $$
Because $\rho_c>0$, this is a continuous, strictly decreasing, piecewise linear bijection from $[0,H]$ to $[0,1]$, with
$$ x_c(H)=0, \qquad x_c(0)=1. $$
Define the option’s rate profile by
$$ r_c(x_c(y))=\frac1{\rho_c(y)} $$
away from breakpoints.
All rates and segment endpoints are rational. As $x$ increases, $y$ decreases; since $\rho_c$ is nonincreasing in $y$, $\rho_c(y)$ increases along this scan. Thus $r_c(x)$ is nonincreasing in $x$, exactly the optimal internal rate order established above.
On a density segment with value $\rho$ and hazard-coordinate length $\Delta y$, the corresponding mass-coordinate segment has length $\rho\Delta y$ and rate $1/\rho$. Its total hazard is therefore $\Delta y$. Summing segments gives
$$ \int_0^1r_c(x)\,dx=H. $$
More generally, the remaining hazard after reaching $x_c(y)$ is $y$:
$$ \int_{x_c(y)}^1r_c(x)\,dx=y. $$
Using the formula $K_c=\int_0^1 e^{H-H_c(x)}\,dx$ and changing coordinates yields
$$ K_c=\int_0^H e^y\rho_c(y)\,dy. $$
Consequently,
$$ K_1-K_2 = \frac{g(1)}D = \frac{e^\alpha(e-1)^2}{D}F. $$
This is the required sign-preserving identity. Also,
$$ p_1=p_2=e^{-H}. $$
The two rate profiles initially may have different segment lengths. The society requires the same type masses for both options, so this must be repaired explicitly.
Take the union of their rational breakpoints in mass coordinate:
$$ 0=x_0<x_1<\cdots<x_\tau=1. $$
Create type $t$ with mass
$$ \mu_t=x_t-x_{t-1}, $$
and assign $\lambda_{tc}$ to be the constant value of $r_c$ on $(x_{t-1},x_t)$.
Every mass and rate is positive rational, and the masses sum to $1$. Refinement preserves each rate profile and hence preserves $K_c$ and $p_c$. Ordering these types by increasing $t$ already gives decreasing rates for both options.
There are at most $3n$ positive hazard breakpoints, so each profile has at most $3n$ segments. Their common refinement has at most $6n-1$ segments. Thus the constructed support size is linear in the number of input terms.
Finally, this construction has polynomial bit complexity. Grouping terms, forming $D$, computing density values, integrating constant density segments, taking reciprocals, and refining breakpoints all use polynomially many rational operations. The numerators and denominators arising from these explicit sums and products have polynomial bit length in the original input. No exponential needs to be numerically evaluated to construct the society.
Reduction theorem. In polynomial time, any explicit rational exponential sum can be converted into a two-option society with common support and equal feasibility probabilities such that
$$ \operatorname{sgn}(K_1-K_2)=\operatorname{sgn}(F). $$
The existence of an optimal block scan alone does not rule out an algorithm using an interleaved optimal output. For two options, a stronger statement holds.
Fix any measurable scan, and let option $c$ have the earlier deterministic completion position $b_c$. Write $d$ for the other option and set
$$ x=X_d(b_c). $$
On the event that both options are feasible, the original scan costs $1+x$: it has inspected all of option $c$ and mass $x$ of option $d$ by its first certification.
The serialized scan putting $c$ first costs $1$ on this event. By Section 1.1, it costs no more on every other realization outside a null event.
The probability that both options are feasible is $p_cp_d>0$. Hence, if $x>0$, serialization decreases expected cost by at least
$$ p_cp_d x>0. $$
Such a scan cannot be optimal. Every optimal scan therefore has $x=0$.
Since the two option sets partition the scan parameter interval,
$$ b_c=X_c(b_c)+X_d(b_c)=1. $$
Option $c$ consequently occupies $[0,1)$ modulo null sets, and option $d$ occupies $[1,2)$ modulo null sets.
This also excludes tied completion positions: a tie would give $X_d(b_c)=1$.
For either block order, replacing its local orders by decreasing rate order cannot increase expected cost. When $K_1\neq K_2$, the minimum expected costs of the two block orders differ by
$$ p_1p_2(K_1-K_2), $$
which is nonzero. Therefore, every optimal measurable scan must start with the option having smaller priority.
Use the natural finite output representation: a permutation of the input intervals. Section 1 proves that this representation always contains an optimal scan.
An oracle that determines signs of explicit rational exponential sums supplies every priority comparison. Rational rate sorting followed by comparison-based option sorting therefore constructs an optimal scan using polynomially many oracle calls of polynomial input size.
Conversely, suppose an algorithm outputs such an optimal permutation in polynomial time. Given an exponential sum:
If option $1$ is first, the sum is negative; if option $2$ is first, it is positive. Section 3 proves that an optimal output cannot evade this choice through interleaving.
Thus:
Computational equivalence. Constructing an optimal scan in the finite interval-permutation representation is polynomial-time Turing equivalent to determining signs of explicit rational exponential sums.
This equivalence establishes neither polynomial-time solvability nor NP-hardness. It shows that the priority formulas’ positive-coefficient structure and shared type masses do not make their comparisons less general.
The Lindemann–Weierstrass theorem states that exponentials of distinct algebraic numbers are linearly independent over the algebraic numbers. See [Theorem 13 of *Identity Testing for Circuits with Exponentiation Gates*](https://drops.dagstuhl.de/storage/00lipics/lipics-vol362-itcs2026/html/LIPIcs.ITCS.2026.95/LIPIcs.ITCS.2026.95.html).
After grouping equal rational exponents, both exponents and coefficients are algebraic, and the remaining exponents are distinct. The theorem therefore implies
$$ \sum_s b_s e^s=0 \quad\Longleftrightarrow\quad b_s=0\text{ for every grouped exponent }s. $$
Equality testing takes polynomial-time rational arithmetic.
For an unequal comparison, certified numerical intervals converging to its value eventually exclude zero. This yields a terminating exact algorithm. It does not yield a polynomial running-time bound without further control of sign determination.
If $m=1$, sorting types by decreasing rational rate suffices.
If $\tau=1$, normalization forces $\mu_1=1$, and
$$ K_c = \frac{e^{\lambda_{1c}}-1}{\lambda_{1c}} = \int_0^1e^{\lambda_{1c}u}\,du. $$
This is strictly increasing in $\lambda_{1c}$, since the integrand strictly increases for every $u>0$. Sorting options by increasing rational rate therefore solves this case in polynomial time.
To avoid the tolerance-encoding issue identified by the verifier, state the guarantee with a precision parameter: for any integer $b\geq1$, an expected cost within $2^{-b}$ of optimum can be obtained in time polynomial in $m,\tau,L,b$.
Set
$$ \varepsilon=2^{-b}, \qquad \delta=\frac{\varepsilon}{m(m+1)}. $$
Compute rational approximations satisfying
$$ 0<a_c\leq1, \qquad 0\leq q_c\leq1, \qquad |a_c-A_c|\leq\delta, \qquad |q_c-p_c|\leq\delta. $$
Sort by $a_c/q_c$, placing zero $q_c$ values last. The adjacent-exchange argument proves that this minimizes
$$ \widetilde{\mathcal C}(\sigma) = \sum_{j=1}^m a_{\sigma(j)} \prod_{i<j}(1-q_{\sigma(i)}). $$
For factors in $[0,1]$, telescoping the product difference gives
$$ \left| \prod_{i<j}(1-p_{\sigma(i)}) - \prod_{i<j}(1-q_{\sigma(i)}) \right| \leq(j-1)\delta. $$
Because $a_c\leq1$, the difference between corresponding objective summands is at most $j\delta$. Uniformly over permutations,
$$ |\mathcal C(\sigma)-\widetilde{\mathcal C}(\sigma)| \leq\frac{m(m+1)}2\delta. $$
Applying this bound to a surrogate minimizer $\widehat\sigma$ and a true minimizer $\sigma^*$ gives
$$ \mathcal C(\widehat\sigma) \leq \mathcal C(\sigma^*)+m(m+1)\delta = \operatorname{OPT}+\varepsilon. $$
For completeness, the required numerical approximations have polynomial bit complexity. If
$$ H_{ic}=\sum_{j=1}^i r_{jc}\ell_{jc}, \qquad H_{0c}=0, $$
then
$$ A_c= \sum_{i=1}^{\tau} \frac{e^{-H_{i-1,c}}-e^{-H_{ic}}}{r_{ic}}, \qquad p_c=e^{-H_{\tau c}}. $$
Every reciprocal rate is at most $2^L$. Approximating each exponential to absolute error $\delta/(8\tau2^L)$ makes the error in $A_c$ at most $\delta/4$. Clamping that approximation to $[\delta/2,1]$ preserves error at most $\delta$ and ensures positivity. Clamp the feasibility approximation to $[0,1]$.
Here is an explicit polynomial-time routine for approximating $e^{-v}$, where $v\geq0$ is rational, to error $2^{-N}$:
A Taylor polynomial of degree
$$ M=N+\lceil\log_2 k\rceil+2 $$
has error at most $1/(M+1)!\leq2^{-M}$. Clamping cannot increase this error. Since
$$ |x^k-y^k|\leq k|x-y| \qquad(0\leq x,y\leq1), $$
the final error is less than $2^{-N}$. Here $k\leq N+1$, and all rational intermediates have polynomial bit length.
This supplies the claimed approximation algorithm and explicitly repairs both minor issues in the notes.
The unresolved target is still the exact binary-input classification.
The new reduction shows that proving polynomial-time priority comparisons would also prove polynomial-time sign determination for arbitrary explicit rational exponential sums. Conversely, a polynomial-time algorithm for those signs would complete the optimal-scan algorithm.
No polynomial-time sign algorithm or NP-hardness reduction for that auxiliary problem is established here. Accordingly, I claim only partial progress.
⟨structured verdict parsed — rendered above⟩
Assessment: correct partial progress. The output establishes the structural characterization, the reduction to and from rational exponential-sum sign determination in the stated finite output representation, and the additive approximation guarantee. It does not resolve the polynomial-time versus NP-hardness question in USER_TASK, and it explicitly acknowledges this.
I found no false central step or major gap in the partial results. There is one minor notation omission.
The construction respects the intended input model:
The computational equivalence is expressly restricted to outputting a permutation of the input intervals. This is a sufficient representation for an optimal scan by Section 1. It does not specify computational access to an arbitrary measurable scan encoded in some other representation.
The output makes no unsupported claim that exponential-sum sign determination is NP-hard or polynomial-time solvable.
The properties of $X_c$ and $b_c$ are correct. In particular, continuity and monotonicity ensure that the first position at which $X_c$ reaches $1$ exists and satisfies $X_c(b_c)=1$.
The compression argument is valid:
Consequently, the claimed measure-preserving bijection modulo null sets is justified. Absolute continuity of the intensity measures ensures that Poisson failures almost surely avoid the removed sets. Finite total intensity ensures finitely many failures almost surely.
The pathwise comparison also checks out. If $j$ is the first feasible option in completion-position order, every earlier option has encountered its first failure by $b_j$. Its scanned cost is therefore $Z_i$, while option $j$ contributes $1$. Other inspected mass is nonnegative.
Tied completion positions do not invalidate the comparison: all options with an earlier or tied completion position have exhausted their mass by that position, unless already rejected.
When all options are infeasible, both scans incur exactly the sum of their first-failure local positions. Thus serialization genuinely dominates the original scan.
Finding: Section 1.1 is sound.
The void probability and tail-integral expression are correct:
$$ A=\int_0^1 e^{-H(x)}\,dx. $$
The possible atom at $Z=1$ causes no problem for this formula.
For any prefix, the allocated masses satisfy the stated capacity constraints. The exchange argument correctly shows that decreasing rate order maximizes prefix hazard at every prefix mass. It therefore minimizes $A$ while leaving total hazard, and hence feasibility probability, unchanged.
Equal rates may be ordered arbitrarily.
Finding: Section 1.2 is sound.
Independence correctly gives the expected-cost formula. The adjacent-order difference is
$$ A_cp_d-A_dp_c = p_cp_d(K_c-K_d). $$
All feasibility probabilities are strictly positive, so division by $p_c$ is legitimate. Sorting by increasing $K_c$ eliminates all inversions without increasing expected cost.
The suffix-hazard formula is also correct. Each segment contributes
$$ \frac{e^{S_{ic}}-e^{S_{i+1,c}}}{r_{ic}}. $$
After grouping exponentials, each option contributes at most $\tau+1$ distinct exponents, yielding the claimed bound of $2\tau+2$ for a comparison. The rational coefficients and exponents have polynomial bit length.
Finding: The optimal-scan theorem is established. Its sorting prescription alone does not establish polynomial-time exact computation, because the signs of its comparisons remain to be computed.
Multiplication by $e^{\alpha z}(e^z-1)^2$ gives nonnegative rational exponents and at most $3n$ terms before grouping.
The double zero at $z=0$ correctly yields
$$ \sum_s b_s=0, \qquad \sum_s sb_s=0. $$
The factor relating $g(1)$ to $F$ is strictly positive.
The largest generated exponent cannot cancel: it comes uniquely from the largest original exponent and the highest shift. Thus $H>0$ after grouping and deleting zero coefficients.
Finding: Section 2.1 is sound, including the nonempty-support case.
Both $u$ and $v$ are positive, nonincreasing rational step functions. Their common integral follows from the first-moment identity, and $D$ is strictly positive.
The exponential-integral identity correctly handles exponent zero. Specifically, the zeroth-moment identity justifies replacing the sum over positive exponents of $b_s(e^s-1)$ by the full sum of $b_se^s$.
Finding: Section 2.2 is sound.
Strict positivity of the densities makes each $x_c$ a continuous, strictly decreasing bijection with the stated endpoints.
The direction of monotonicity is correct: increasing scan mass corresponds to decreasing hazard coordinate, so the resulting rates are nonincreasing in scan mass.
The segment calculations verify both total hazard $H$ and remaining hazard $y$. The change of coordinates consequently gives
$$ K_c=\int_0^H e^y\rho_c(y)\,dy. $$
This establishes the claimed sign-preserving identity and equal feasibility probabilities.
Minor issue: The notation $H_c(x)$ in the displayed formula immediately preceding this change of coordinates is not explicitly defined. Its intended meaning is clear from Section 1.2, but it should be stated.
Minimum clarification: Define $H_c(x)$ as the cumulative hazard of the constructed option $c$.
Taking the union of the mass-coordinate breakpoints produces positive rational type masses summing to $1$. Both rates are constant on every resulting type interval, and refinement preserves both priority values.
The support-size bound is valid: the common refinement of two partitions with at most $3n$ segments each has at most $6n-1$ segments.
The construction uses explicit rational sums, products, reciprocals, and comparisons with polynomially bounded expression sizes. Its bit-complexity claim is justified; it does not rely on evaluating any exponential.
Finding: The reduction theorem is established.
The strict-improvement argument is valid.
On the event that both options are feasible, the original scan incurs $1+x$, while serialization incurs $1$. This event has probability $p_cp_d>0$. Serialization is no worse on the other realizations, so any $x>0$ excludes optimality.
When $x=0$, the partition identity gives $b_c=1$. Thus the first option occupies the first unit interval modulo null sets, and the second occupies the second unit interval. Tied completion positions would force $x=1$ and are therefore excluded.
Finally, an internally suboptimal order cannot rescue the wrong option-block order: its cost is at least the minimum for that block order. The stated difference between those minima is correct.
Finding: Section 3 establishes the claimed necessity of whole-option blocks for two options.
The forward oracle reduction is valid: rate sorting uses rational comparisons, and option sorting uses polynomially many exponential-sum sign queries of polynomial input size.
The reverse reduction correctly reads the sign from the first option after separately handling equality. The negative and positive directions agree with the sign-preserving priority identity.
The Lindemann–Weierstrass theorem is stated correctly, and its hypotheses are satisfied: grouped exponents are distinct rationals, hence algebraic, and coefficients are algebraic. The cited [Theorem 13](https://drops.dagstuhl.de/storage/00lipics/lipics-vol362-itcs2026/html/LIPIcs.ITCS.2026.95/LIPIcs.ITCS.2026.95.html) confirms the stated linear-independence result.
Equality detection by grouping is therefore valid. Certified intervals eventually determine any nonzero comparison, establishing termination without a polynomial running-time guarantee.
Finding: The stated computational equivalence is established. It leaves the requested exact complexity classification unresolved.
The special cases are correct:
The approximation analysis also checks out:
The numerical implementation is sufficient. The exponential precision gives total error at most $\delta/4$ in $A_c$. Clamping to $[\delta/2,1]$ preserves the required error bound even when $A_c$ is smaller than $\delta/2$.
The cutoff and Taylor routine are correct. In the non-cutoff branch, $k\leq N+1$, the alternating-series remainder satisfies the stated bound, and powering amplifies error by at most $k$. Rational intermediate bit lengths remain polynomial in input length and $N$.
Finding: The additive approximation guarantee is established. It does not resolve exact optimal-order construction.
The write-up needs only the explicit definition of $H_c(x)$ to make its partial results fully self-contained.
Resolving USER_TASK requires additional mathematics: either a polynomial-time exact sign algorithm sufficient for the priority comparisons, or a valid hardness result transferred through the reduction. Equality testing, terminating numerical computation, and additive approximation do not supply that classification.
⟨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.