d4-conf-ijcai-2007-0021 (d4-conf-ijcai-2007-0021)

Given a total reporter mass \(N>0\), a finite-support distribution \(\mu\) over rational report types \(q_i=(b_i,d_i,u_i)\), a valid upper bound \(B\) on each type's implied evidence total, and \(\varepsilon>0\), compute \(E=N\sum_{i=1}^{\tau}\mu_i Z^{-1}(q_i)\) to additive error at most \(\varepsilon\) in each coordinate.

A society is given by its support: a list of \(\tau\) distinct rational report types \(q_i=(b_i,d_i,u_i)\), each with positive binary rational mass \(\mu_i\), where \(\sum_i\mu_i=1\). Here \(\tau\) counts supported types, not possible types; the number of outcome categories is fixed at \(m=2\).
Evidence consists of real pairs \((r,s)\) with \(r,s\geq0\) and \(t=r+s>0\). Define \(f_{r,s}(x)=x^r(1-x)^s/\int_0^1 y^r(1-y)^s\,dy\) and \(c(r,s)=\frac12\int_0^1|f_{r,s}(x)-1|\,dx\).
Set \(\alpha=(r+1)/(r+s+2)\) and \(Z(r,s)=(\alpha c(r,s),(1-\alpha)c(r,s),1-c(r,s))\). Each input report satisfies \(b_i,d_i,u_i>0\), \(b_i+d_i+u_i=1\), and is promised to have a unique preimage \((r_i,s_i)=Z^{-1}(q_i)\) with \(0<r_i+s_i\leq B\).
The inputs \(N,B,\varepsilon>0\) are binary rationals; \(N\) is total reporter mass. Compute a rational approximation to \(E=N\sum_{i=1}^{\tau}\mu_i(r_i,s_i)\) with additive error at most \(\varepsilon\) in each coordinate. Let \(L\) be the total input bit length, including \(N,B,\varepsilon\); running times use the bit model and are expressed in \(m,\tau,L\) and these numerical parameters.

Is this approximation problem solvable in time polynomial in \(m,\tau,L\), or is it NP-hard under polynomial-time Turing reductions?

For single-report inversion, [Wang and Singh (2007)](https://www.ijcai.org/Proceedings/07/Papers/250.pdf) establish a bisection iteration lower bound of \(\Omega(\log(1/\delta))\) for fixed evidence bound and interval tolerance \(\delta\), without bounding certainty-evaluation bit cost.
[A later model](https://www.csc2.ncsu.edu/faculty/mpsingh/papers/mas/TAAS-10-certainty.pdf) uses \(\alpha=r/(r+s)\) and numerical quadrature, so its inversion algorithm concerns a different map. No bit-complexity classification for the exact mass-aggregation problem above was found.

Status and proved progress

I do not resolve the complexity classification for arbitrary reports. I prove a polynomial-time algorithm for the nontrivial subclass in which every supported report satisfies $b_i=d_i$.

The new ingredient is an explicit inverse-conditioning bound:
$$ C_{1/2}'(t)\geq \frac{2^{-36}}{(B+1)^4} \qquad (0<t\leq B). $$
Its dependence on $B$ requires only $O(\log(B+1))$ precision bits, even when the numerical value of $B$ is exponentially large.

I also prove that the general aggregation problem is polynomial-time Turing equivalent to single-report inversion. All results used below are proved here; the forward-evaluation proof is specialized to the symmetric family.

1. Reduction to scalar inversion

For a report $q=(b,d,u)$, define
$$ \alpha=\frac{b}{b+d}, \qquad c_*=1-u. $$
The input assumptions imply $0<\alpha<1$ and $0<c_*<1$.

If $t=r+s$, the specified posterior mean gives
$$ r=\alpha(t+2)-1, \qquad s=(1-\alpha)(t+2)-1. $$
Consequently, the feasible scalar interval is
$$ I_\alpha=[t_{\min}(\alpha),B], \qquad t_{\min}(\alpha)= \max\left\{\frac1\alpha,\frac1{1-\alpha}\right\}-2. $$
Indeed, these two lower bounds on $t$ are exactly the conditions $r\geq0$ and $s\geq0$.

Define
$$ C_\alpha(t)= c\bigl(\alpha(t+2)-1,(1-\alpha)(t+2)-1\bigr). $$
Inversion is therefore equivalent to finding the promised unique solution of
$$ C_\alpha(t)=c_*, \qquad t\in I_\alpha. $$
For $\alpha=1/2$, extend the interval to include $t=0$, where the density is uniform and $C_{1/2}(0)=0$. Since $c_*>0$, this adds no solution.

A scalar approximation $\widehat t$ induces rational evidence approximations satisfying
$$ |\widehat r-r|=\alpha|\widehat t-t|, \qquad |\widehat s-s|=(1-\alpha)|\widehat t-t|. $$
Thus scalar error at most $\delta$ suffices for coordinate error at most $\delta$.

Aggregation equivalence

Use the usual output convention of rational dyadic approximations with polynomial encoding length.

Suppose single-report inversion is available with coordinate tolerance $\delta$. For each supported report, request tolerance
$$ \delta=\frac{\varepsilon}{N} $$
and return
$$ \widehat E=N\sum_{i=1}^{\tau}\mu_i(\widehat r_i,\widehat s_i). $$
For either coordinate $j$,
$$ |\widehat E_j-E_j| \leq N\sum_{i=1}^{\tau}\mu_i\delta = \varepsilon. $$
The tolerance has polynomial encoding length, there are $\tau$ queries, and the rational arithmetic has polynomial overhead.

Conversely, a single-report inversion instance is an aggregation instance with $\tau=1$, $\mu_1=1$, and $N=1$.

Hence the two promised approximation problems are polynomial-time Turing equivalent. In particular, any hardness of the aggregation problem is already present at one supported report.

2. The symmetric family

Assume $b=d$. Then $\alpha=1/2$, so necessarily
$$ r=s=\frac t2. $$
Write
$$ p=\frac t2, \qquad h(x)=\log\bigl(4x(1-x)\bigr), \qquad I_p=\int_0^1 e^{p h(x)}\,dx. $$
The normalized density is
$$ f_t(x)=\frac{e^{p h(x)}}{I_p}. $$
The factor $4^p$ cancels during normalization, so this is exactly the density in the task.

For $t>0$, $f_t$ is symmetric about $1/2$, strictly increasing on $(0,1/2)$, and tends to zero at both endpoints. Also $I_p<1$, so $f_t(1/2)>1$. There is therefore a unique $\ell=\ell(t)\in(0,1/2)$ such that
$$ f_t(\ell)=1, \qquad \{x:f_t(x)>1\}=(\ell,1-\ell). $$
Denote the certainty of this family by
$$ C(t)=C_{1/2}(t). $$

2.1. Quantitative bounds on the crossing point

We first prove
$$ \ell>\frac18, \qquad \frac12-\ell\geq\frac{1}{64(t+1)}. $$

Since
$$ \int_0^1h(x)\,dx=\log4-2, $$
Jensen's inequality gives
$$ I_p\geq \exp\bigl(p(\log4-2)\bigr). $$
Moreover,
$$ h(1/8)=\log(7/16)<\log4-2. $$
The last inequality is equivalent to $7e^2<64$, which follows from $e<3$. Hence
$$ f_t(1/8) \leq \exp\bigl(p(h(1/8)-(\log4-2))\bigr) <1. $$
Strict increase on $(0,1/2)$ proves $\ell>1/8$.

For the second bound, put
$$ a_0=\log(4/3). $$
On a set of measure $1/2$, namely $[0,1/4]\cup[3/4,1]$, one has $4x(1-x)\leq3/4$. Everywhere else, $4x(1-x)\leq1$. Thus
$$ I_p\leq \frac{1+e^{-pa_0}}2. $$
Using $-\log z\geq1-z$ and $1-e^{-z}\geq z/(1+z)$ for $z\geq0$, we obtain
$$ -\log I_p \geq \frac{pa_0}{2(1+pa_0)}. $$
The elementary integral bounds $1/4\leq a_0<1$ imply
$$ -\frac{\log I_p}{p}\geq\frac{1}{8(t+1)}. $$

The crossing equation gives $p h(\ell)=\log I_p$. On $[1/8,1/2]$,
$$ 0\leq h'(x)=\frac{1-2x}{x(1-x)}\leq8. $$
Consequently,
$$ \frac{1}{8(t+1)} \leq-h(\ell) = \int_\ell^{1/2}h'(x)\,dx \leq8\left(\frac12-\ell\right), $$
which proves the claimed lower bound on $1/2-\ell$.

2.2. Derivative as a covariance

Let $X$ have density $f_t$, and put
$$ A_t=(\ell,1-\ell). $$
Differentiating the normalized density yields
$$ \partial_t f_t(x) = \frac12 f_t(x)\bigl(h(x)-\mathbb E_t[h(X)]\bigr). $$
For any fixed positive $t$, this differentiation is justified in a neighborhood of $t$: near the endpoints, the required dominating functions are constant multiples of a positive power of $x(1-x)$ times $1+|\log x|+|\log(1-x)|$, which are integrable.

Because the positive and negative parts of $f_t-1$ have equal integrals,
$$ C(t)=\int_0^1(f_t(x)-1)_+\,dx. $$
The equation $f_t(x)=1$ has only two solutions. Differentiating the positive part almost everywhere, with the same integrable domination, gives
$$ C'(t) = \frac12\operatorname{Cov}_t\bigl(\mathbf 1_{A_t}(X),h(X)\bigr). $$

For independent variables $X,Y$ with density $f_t$,
$$ \operatorname{Cov}_t(\mathbf 1_{A_t},h) = \frac12\int_0^1\int_0^1 \bigl(\mathbf 1_{A_t}(x)-\mathbf 1_{A_t}(y)\bigr) \bigl(h(x)-h(y)\bigr) f_t(x)f_t(y)\,dx\,dy. $$
Here $A_t$ is a strict superlevel set of $h$, since $f_t=e^{ph}/I_p$ and $p>0$. Every integrand in this formula is therefore nonnegative.

This proves monotonicity and permits a quantitative estimate by restricting the double integral.

2.3. A uniform derivative lower bound

Fix $B>0$ and $0<t\leq B$. Set
$$ d=\frac12-\ell, \qquad w=\frac{1}{1024(B+1)}. $$
The crossing-point bound implies
$$ d\geq\frac{1}{64(B+1)}, \qquad w\leq\frac d{16}. $$
Consider the intervals
$$ U=[\ell-2w,\ell-w], \qquad V=[\ell+w,\ell+2w]. $$
They have length $w$, with $U$ outside $A_t$ and $V$ inside $A_t$.

Every point between their endpoints lies in $(1/16,1/2)$. On that interval,
$$ 0<h'(x)\leq16. $$
Since $\partial_x\log f_t=p h'$, and $f_t(\ell)=1$, we have
$$ |\log f_t(x)|\leq16Bw\leq\frac1{64} \qquad (x\in U\cup V). $$
In particular, $f_t(x)\geq1/2$ there.

For points between $U$ and $V$,
$$ \frac12-x\geq d-2w\geq\frac d2. $$
As $x(1-x)\leq1/4$,
$$ h'(x)\geq8\left(\frac12-x\right)\geq4d. $$
Therefore, whenever $x\in V$ and $y\in U$,
$$ h(x)-h(y)\geq8dw. $$

Restricting the covariance integral to $V\times U$ and $U\times V$ now gives
$$ C'(t) \geq \frac12(8dw)\left(\frac w2\right)^2 = dw^3. $$
Thus
$$ \boxed{ C'(t)\geq\frac{2^{-36}}{(B+1)^4} \qquad (0<t\leq B). } $$

Finally, $C$ is continuous at zero. Indeed, $f_t(x)\to1$ for every interior $x$, while for $0\leq p\leq1$,
$$ 0\leq f_t(x)\leq\frac1{I_1}, $$
an integrable constant bound. Dominated convergence applies.

The mean value theorem, including intervals with left endpoint zero, consequently proves
$$ C(t_2)-C(t_1) \geq \kappa_B(t_2-t_1), \qquad 0\leq t_1<t_2\leq B, $$
where
$$ \kappa_B=\frac{2^{-36}}{(B+1)^4}. $$
In particular, if $C(t_*)=c_*$, then
$$ |C(t)-c_*|\geq\kappa_B|t-t_*|. $$

3. Polynomial-time certainty evaluation for symmetric evidence

Theorem. Given a nonnegative rational $t$ of encoding length $T$ and an integer $n\geq1$, one can compute a rational approximation to $C(t)$ with error at most $2^{-n}$ in time polynomial in $T+n$.

The case $t=0$ returns zero. Assume henceforth that $t>0$, and put $k=t+2$.

3.1. A transformation with uniform analytic and tail bounds

Use the increasing substitution
$$ x(v)=\frac{1+\tanh(v/\sqrt k)}2, \qquad v\in\mathbb R, $$
and define
$$ F(v)=\cosh(v/\sqrt k)^{-k}, \qquad J=\int_{\mathbb R}F(v)\,dv. $$
Direct substitution into the unnormalized symmetric beta density gives
$$ f_t(x(v))x'(v)=\frac{F(v)}J, \qquad x'(v)=\frac{\operatorname{sech}^2(v/\sqrt k)}{2\sqrt k}. $$
In particular,
$$ I_p=\frac{J}{2\sqrt k}. $$

Let $\phi(v)=\log F(v)$. Then
$$ \phi(0)=\phi'(0)=0, \qquad \phi''(v)=-\operatorname{sech}^2(v/\sqrt k). $$
For $|v|\leq1$, because $k\geq2$ and $\cosh1<2$,
$$ -1\leq\phi''(v)\leq-\frac14. $$
Global concavity therefore gives, for $R\geq1$,
$$ \int_{|v|>R}F(v)\,dv\leq8e^{-(R-1)/4}. $$
Also $\phi''\geq-1$ implies $\phi(v)\geq-v^2/2$, so
$$ J\geq\int_{-1/2}^{1/2}e^{-v^2/2}\,dv>\frac12. $$
The preceding tail bound at $R=1$ gives the convenient upper bound $J\leq10$.

For complex $z=u+iy$ with $|y|\leq1/2$, define
$$ F(z)=\exp\bigl(-k\operatorname{Log}\cosh(z/\sqrt k)\bigr). $$
The logarithm is analytic on a neighborhood of this closed strip: the real part of $\cosh(z/\sqrt k)$ is positive there.

The identity
$$ |\cosh((u+iy)/\sqrt k)|^2 = \cosh^2(u/\sqrt k)-\sin^2(y/\sqrt k) $$
and $-\log(1-a)\leq2a$ for $0\leq a\leq1/8$ give
$$ \log|F(u+iy)| \leq \log F(u)+y^2 \leq\frac14. $$
Hence $|F(z)|<2$ throughout that closed strip. This supplies a fixed analytic neighborhood independently of the numerical size of $t$.

3.2. Certified integration in polynomial bit complexity

We show how to integrate $F$ over a rational interval of polynomial length to any requested absolute precision.

Partition the interval into cells of length at most $1/16$. On each cell, interpolate at $M\geq2$ equally spaced rational nodes.

Cauchy's estimate on a circle of radius $1/4$ around any real point gives
$$ \frac{|F^{(M)}(x)|}{M!}\leq2\cdot4^M. $$
These circles lie strictly inside the established analytic strip. The real interpolation remainder therefore bounds the error of the exact degree-$M-1$ interpolant by
$$ 2\left(\frac14\right)^M. $$

Sampling errors can also be controlled explicitly. For a cell of length $a$, the denominator in the $j$th Lagrange basis polynomial has absolute value
$$ \left(\frac a{M-1}\right)^{M-1}j!(M-1-j)!. $$
Each numerator has absolute value at most $a^{M-1}$. Thus the sum of absolute basis values is bounded by
$$ \frac{2^{M-1}(M-1)^{M-1}}{(M-1)!} \leq(2e)^{M-1} \leq2^{4M}. $$
To obtain uniform interpolation error at most $\gamma$, it therefore suffices to choose $M=O(\log(1/\gamma))$ and sample each value with absolute error at most $\gamma 2^{-4M-1}$.

All nodes and computed sample values are rational. The resulting polynomial has rational coefficients and can be integrated exactly by rational arithmetic. Its degree and coefficient encoding length are polynomial in the input size and requested precision.

For completeness, the necessary elementary-function evaluations admit certified polynomial bit cost:

• Square roots of positive rationals can be enclosed by rational bisection.
• For positive arguments, normalize to $[1,2]$ and evaluate logarithms using

$$ \log y= 2\sum_{j=0}^{\infty} \frac{((y-1)/(y+1))^{2j+1}}{2j+1}. $$
The ratio has absolute value at most $1/3$, so truncation has a certified geometric error.

• Exponentials on arguments of polynomial magnitude can be evaluated by Taylor series with a certified remainder, or by argument reduction followed by squaring.
• A very negative final exponent in $F(v)$ can be replaced by zero once its certified upper bound makes the exponential smaller than the required error.

Here $|v|$ is polynomial in the requested precision and interval length, $k\leq2^{O(T)}$, and $\sqrt k\geq\sqrt2$. Evaluation of
$$ F(v)=\exp\bigl(-k\log\cosh(v/\sqrt k)\bigr) $$
therefore needs only polynomially many working bits. Multiplication by $k$ requires $O(T)$ additional guard bits. The potentially enormous negative final exponent is handled by the stated truncation rule.

To approximate $J$ to error $2^{-q}$, take
$$ R=16(q+10). $$
The tail bound is smaller than $2^{-q}/2$. Integrate $F$ over $[-R,R]$ by the preceding construction with total error at most $2^{-q}/2$. There are $O(q)$ cells and each has polynomial degree. This computes $J$ in time polynomial in $T+q$.

3.3. Computing the crossing and certainty

Put
$$ M_0=\frac{2\sqrt k}{J}=\frac1{I_p}>1, \qquad h_0=\frac{\log M_0}{t}. $$
The ratio of the transformed beta density to the transformed uniform density is
$$ \frac{F(v)/J}{x'(v)} = M_0\cosh(v/\sqrt k)^{-t}. $$
Thus its positive crossing is
$$ v_0= \sqrt k\, \log\left(e^{h_0}+\sqrt{e^{2h_0}-1}\right). $$
The region where $f_t>1$ corresponds to $(-v_0,v_0)$, giving
$$ C(t)= \frac2J\int_0^{v_0}F(v)\,dv - \tanh(v_0/\sqrt k). $$

We verify the conditioning and size bounds needed to use this formula.

The crossing-point estimates in Section 2 give
$$ h_0\geq\frac{1}{16(t+1)}. $$
Jensen's inequality gives the upper bound
$$ h_0\leq\frac{2-\log4}{2}<\frac12. $$
Since $t$ is a positive rational of encoding length $T$,
$$ t\geq2^{-O(T)}, \qquad t+1\leq2^{O(T)}. $$
Consequently, $h_0$ and $e^{2h_0}-1$ are bounded below by $2^{-O(T)}$. Division by $t$, the square root in the crossing formula, and multiplication by $\sqrt k$ therefore require only $O(T)$ additional guard bits to obtain any specified absolute accuracy. The logarithm's argument stays bounded away from zero.

The integration interval also has polynomial length. Write $z_0=v_0/\sqrt k$. Since $\log\cosh z_0=h_0<1/2$, we have $z_0<2$. On $[0,2]$, $\cosh z<5$, so integrating $\operatorname{sech}^2z\geq1/25$ twice yields
$$ \log\cosh z\geq\frac{z^2}{50}. $$
If $t\geq1$, it follows that
$$ v_0^2 \leq 50\frac{k}{t}\log M_0 \leq150\log(4\sqrt k) = O(T+1), $$
where $M_0\leq4\sqrt k$ follows from $J>1/2$. If $t<1$, then $k<3$ and $v_0<2\sqrt3$. Thus in all cases $v_0=O(T+1)$.

Finally, choose $\zeta=2^{-n-6}$. Compute rational approximations with
$$ |\widehat J-J|\leq\zeta, \qquad |\widehat v-v_0|\leq\zeta, $$
clipping $\widehat v$ to zero if necessary. Use additional guard bits when computing $\widehat v$, as justified above. Compute
$$ \widehat H\approx\int_0^{\widehat v}F(v)\,dv $$
to absolute error $\zeta$, and approximate $\tanh(\widehat v/\sqrt k)$ to error $\zeta$.

Because $F(v)\leq1$ on the real line,
$$ \left|\widehat H-\int_0^{v_0}F(v)\,dv\right|\leq2\zeta. $$
Also $\widehat J\geq1/4$ and $\int_0^{v_0}F\leq J/2$. These bounds give error at most $20\zeta$ in the normalized integral term. The hyperbolic-tangent term has error at most $2\zeta$, since $|\tanh'|\leq1$ and $\sqrt k\geq1$.

The total error is therefore at most $22\zeta<2^{-n}$. Every operation has bit cost polynomial in $T+n$. This proves the forward-evaluation theorem.

4. Polynomial-time inversion and aggregation for symmetric reports

Theorem. For $m=2$, the promised aggregation problem restricted to inputs satisfying $b_i=d_i$ for every supported type is solvable in time polynomial in $\tau$ and $L$.

For one report, let $t_*\in(0,B]$ be its promised solution and let $\delta>0$ be the desired scalar tolerance.

If $B\leq2\delta$, return $B/2$. Otherwise, define
$$ \eta=\frac{\kappa_B\delta}{8}, \qquad \kappa_B=\frac{2^{-36}}{(B+1)^4}. $$
Maintain a bracket initially equal to $[0,B]$. At its midpoint $x$, evaluate $C(x)$ to absolute error at most $\eta$.

If
$$ |\widehat C(x)-c_*|\leq2\eta, $$
then
$$ |C(x)-c_*|\leq3\eta<\kappa_B\delta. $$
The inverse-conditioning bound proves $|x-t_*|<\delta$, so return $x$.

Otherwise, the residual sign is certified: an approximation error of $\eta$ cannot change the sign of a residual whose estimated magnitude exceeds $2\eta$. Strict monotonicity then permits the appropriate bisection step.

If the bracket reaches width at most $2\delta$, return its midpoint. The bracket still contains $t_*$, so this answer also has error at most $\delta$.

There are
$$ O\bigl(1+\log^+(B/\delta)\bigr) $$
iterations. The required forward precision has
$$ O\bigl(1+\log(B+1)+\log^+(1/\delta)\bigr) $$
bits. Both quantities are polynomial in the binary input length. Bisection midpoints have polynomial encoding length, so Section 3 proves polynomial total bit cost.

For aggregation, use $\delta=\varepsilon/N$, invert each report, and return
$$ \widehat E= N\sum_{i=1}^{\tau}\mu_i \left(\frac{\widehat t_i}{2},\frac{\widehat t_i}{2}\right). $$
Each evidence coordinate has error at most $\delta$, and the weighted estimate from Section 1 gives error at most $\varepsilon$ in each aggregate coordinate. This proves the theorem.

5. What remains unresolved

The general scalar reduction fixes the posterior mean, so its density is
$$ f_{\alpha,t}(x)\propto x^{\alpha(t+2)-1}(1-x)^{(1-\alpha)(t+2)-1}. $$
Its score involves
$$ h_\alpha(x)=\alpha\log x+(1-\alpha)\log(1-x). $$
Unlike the symmetric case, the density is not simply an exponential of $h_\alpha$ relative to uniform measure:
$$ f_{\alpha,t}(x)\propto \frac{\exp((t+2)h_\alpha(x))}{x(1-x)}. $$
Thus the set where $f_{\alpha,t}>1$ need not be a superlevel set of $h_\alpha$. The nonnegative covariance integrand used in Section 2 is unavailable.

This obstruction occurs within the permitted domain. At a boundary point with $r=0$ and $s>0$, the density exceeds one near zero, although $h_\alpha(x)\to-\infty$ there. Near one the density is below one while $h_\alpha(x)$ also tends to $-\infty$. Hence membership in the high-density set is not determined by an upper threshold on $h_\alpha$.

This observation does not disprove general monotonicity. It identifies the precise missing step in extending the proof.

The logarithmic bisection iteration calculation in the [2007 paper](https://www.ijcai.org/Proceedings/07/Papers/250.pdf) does not supply the general certified evaluation and inverse-conditioning estimates needed for a polynomial bit-complexity classification.

The unrestricted target therefore remains open here: I have proved neither a polynomial-time algorithm for asymmetric reports nor an NP-hardness reduction.

⟨structured verdict parsed — rendered above⟩

Verification report

Assessment: partial. The output establishes substantive progress: a correct reduction to scalar inversion, an aggregation–inversion equivalence under its stated output convention, and a polynomial-time algorithm for symmetric reports, subject to minor numerical exposition gaps. It does not classify the unrestricted problem, and explicitly acknowledges this.

I found no false central mathematical step.

1. Scalar reduction and aggregation equivalence

The identities
$$ \alpha=\frac{b}{b+d}, \qquad c_*=1-u $$
follow from the report map and positivity assumptions. Solving the posterior-mean equation gives exactly
$$ r=\alpha(t+2)-1, \qquad s=(1-\alpha)(t+2)-1. $$
The stated lower endpoint is precisely the condition that both evidence coordinates be nonnegative. The promise ensures the interval is nonempty.

For symmetric reports, the interval includes $t=0$, which is excluded from the original evidence domain. The output explicitly treats this as a continuous extension and correctly observes that $c_*>0$ excludes an added solution.

The coordinate-error formulas are correct. The aggregation estimate correctly uses positive masses summing to one:
$$ |\widehat E_j-E_j| \leq N\sum_i\mu_i\delta =\varepsilon. $$
The tolerance $\delta=\varepsilon/N$ has polynomial encoding length. Polynomial overhead for rational arithmetic follows under the expressly stated convention that oracle outputs have polynomial encoding length. The reverse reduction with one supported report preserves the promises.

Finding: this equivalence is established. It transfers complexity classifications; it does not itself provide one.

2. Symmetric density and crossing bounds

For $b=d$, the conclusion $r=s=t/2$ is correct. The normalization by $I_p$ correctly cancels the factor $4^p$.

For $t>0$, symmetry, strict increase on the left half, endpoint limits, and $I_p<1$ establish exactly two crossings and the stated central high-density interval.

Both quantitative crossing bounds check out:

• Jensen’s inequality applies because $h$ is integrable under uniform measure. The comparison at $1/8$ is strict: $e<3$ indeed implies $7e^2<64$.
• The estimate on the two outer quarter-intervals correctly bounds $I_p$.
• The subsequent logarithmic and exponential inequalities give the stated lower bound for $-\log I_p/p$.
• The derivative bound for $h$ on $[1/8,1/2]$ correctly converts that bound into the distance estimate.

Finding: the crossing estimates are valid, including their constants and their full range $t>0$.

3. Differentiation and inverse conditioning

The normalized-density derivative is correct. The stated endpoint domination justifies differentiation locally at every positive $t$.

Differentiating the positive-part representation is also justified: the crossing set has measure zero, and the density derivatives admit an integrable local dominating function. The moving high-density interval introduces no omitted boundary contribution.

The independent-copy covariance identity has the correct factor. Since the high-density interval is a superlevel set of $h$, its integrand is nonnegative almost everywhere.

For the quantitative restriction:

• The crossing bounds place both auxiliary intervals inside the required domain and on opposite sides of the crossing.
• The estimates on $\log f_t$ correctly imply $f_t\geq1/2$ there.
• The lower bound for $h'$ gives the claimed separation of $h$ between the intervals.
• Restricting to both ordered rectangles gives exactly

$$ C'(t)\geq dw^3 \geq \frac{2^{-36}}{(B+1)^4}. $$

Continuity at zero follows from the stated constant domination. The mean value theorem applies even when the left endpoint is zero: continuity is needed at that endpoint, whereas differentiability is needed only in the open interval.

Finding: the derivative lower bound and resulting inverse-conditioning estimate are established.

4. Polynomial-time certainty evaluation

Transformation, tails, and analyticity

The substitution, Jacobian, transformed density, and identity
$$ I_p=\frac{J}{2\sqrt{k}} $$
are correct.

The second derivative of $\log F$ is correctly computed. Its bounds near zero and global concavity justify the stated exponential tails. The estimates $J>1/2$ and $J\leq10$ are valid.

The complex logarithm is analytic in a neighborhood of the stated strip because the real part of the hyperbolic cosine is positive there. The modulus identity and logarithmic inequality correctly establish the uniform bound $|F|<2$.

Finding: the analytic neighborhood and tail estimates are uniform in the numerical value of $t$, as required.

Quadrature and elementary evaluation

The Cauchy derivative estimate and real interpolation remainder yield the stated interpolation error. The bound on the sum of absolute Lagrange basis values correctly controls sampling errors. Exact integration of the rational interpolants has polynomial arithmetic cost when node and sample encoding lengths are polynomial.

The elementary-function discussion identifies suitable algorithms and the relevant magnitude bounds. In particular, multiplication by $k$ requires only a number of guard bits proportional to its binary encoding length. It does not require time polynomial in the numerical value of $k$.

Minor issue: the write-up does not explicitly give the elementary-function truncation orders, remainder bounds, and allocation of sample accuracy across a whole integration interval. These are routine numerical details, rather than missing structural mathematics, but the claim of a fully specified certified algorithm is slightly stronger than the presentation.

Minimum clarification: specify the truncation and working-precision rules for the elementary evaluations, and specify how the interval length converts the requested total integration error into a uniform interpolation-error target.

Crossing formula and final error

The transformed crossing equation and explicit expression for $v_0$ are correct.

The lower and upper bounds for $h_0$ follow from the preceding crossing estimate and Jensen’s inequality. They justify the claimed polynomial guard-bit requirements, including when $t$ is very small or very large.

The bound on the integration interval is also valid. The argument gives a polynomial bound on $v_0$ without requiring a number of quadrature cells proportional to the numerical value of $t$.

Finally, the error accounting checks out:

• The integration and endpoint errors contribute at most $2\zeta$ to the unnormalized integral.
• The denominator bounds give at most $20\zeta$ in the normalized integral term.
• The hyperbolic-tangent term contributes at most $2\zeta$.

Thus the total error is below $2^{-n}$.

Finding: the evaluation theorem is sound in substance, with the minor certification details identified above.

5. Symmetric inversion and aggregation

The initial shortcut has error at most $\delta$.

In the remaining case, an estimated residual of magnitude at most $2\eta$ gives a true residual of magnitude at most $3\eta$, which the inverse-conditioning estimate converts into scalar error below $\delta$.

Otherwise, the residual sign is certified, and strict monotonicity preserves the bracket. Returning its midpoint at width at most $2\delta$ is valid.

The iteration count, evaluation precision, and midpoint encoding lengths are polynomial in the binary input length. The aggregation calculation then gives the requested coordinate tolerances.

Finding: the symmetric subclass is correctly handled in polynomial time, subject to the minor numerical exposition issue.

6. Unrestricted target and cited result

The asymmetric density and score are correctly written. The extra factor involving $x(1-x)$ prevents the symmetric superlevel-set argument from transferring automatically.

The boundary example with $r=0$ and $s>0$ correctly demonstrates this obstruction. It does not disprove monotonicity, and the output appropriately avoids that inference.

The description of the earlier bisection result is accurate: its proof counts interval halvings and does not bound the bit cost of certainty evaluation. [Wang and Singh, Section 3.4](https://www.ijcai.org/Proceedings/07/Papers/250.pdf).

Major scope limitation: no algorithm or hardness reduction is supplied for arbitrary asymmetric reports. The uniqueness promise alone supplies neither certified inversion complexity nor inverse conditioning.

Minimum requirement to settle the assignment: establish the unrestricted inversion complexity or provide a valid hardness reduction. This requires additional mathematics; it is not an expositional repair.

The direction is promising because the output proves meaningful results and accurately identifies their limits. The unrestricted continuous problem remains unresolved.

⟨structured verdict parsed — rendered above⟩