Answer: Computable in deterministic time polynomial in \(m,\tau,L,k\).
Theorem 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateLet ex be evidence about targets x1, . . . , xℓ̸= x, and ex 1, . . . , ex n be evidence about target x.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite target-strategy set \(F\), rational prior \(\pi\), finite set \(T\) of complete recommender, report, and context types, rational masses \(w_t\), and likelihoods \(\ell_t(f)\), compute the normalized weighted-evidence valuation \(\nu(f)=\frac{\pi(f)\prod_{t\in T}\ell_t(f)^{w_t}}{\sum_{g\in F}\pi(g)\prod_{t\in T}\ell_t(g)^{w_t}}\). Integer masses recover aggregation of discrete records; fractional masses use the power-likelihood extension.
Let \(F\) be an explicitly listed finite set of target strategies, with \(m=|F|\geq 1\), and let \(\pi:F\to\mathbb{Q}_{\geq 0}\) satisfy \(\sum_{f\in F}\pi(f)=1\).
A society is given by its support: the list \(T\) of the \(\tau\) complete recommender, report, and context types with positive mass, each mass \(w_t\) a binary rational. Here \(\tau=|T|\) is the support size, not the number of possible types; total mass need not equal \(1\).
For each type, an explicit table supplies finite rational likelihoods \(\ell_t(f)\geq 0\), incorporating its report and context. These tables are inputs; inferring them from a latent model is outside the problem.
Define \(a_f=\pi(f)\prod_{t\in T}\ell_t(f)^{w_t}\), require \(Z=\sum_{g\in F}a_g>0\), and define the weighted-evidence valuation \(\nu(f)=a_f/Z\). Zero likelihood to positive mass is zero, and an empty product is \(1\).
Integer masses represent repeated discrete records; arbitrary positive rational masses use this same power-likelihood definition.
Computing the valuation means, given a precision parameter \(k\geq 1\) in unary, computing dyadic values \(\widehat\nu(f)\) with \(\max_{f\in F}|\widehat\nu(f)-\nu(f)|\leq 2^{-k}\). Let \(L\) be the total bit length of the society, prior, likelihood tables, and type descriptions.
Is computing this weighted-evidence valuation possible in time polynomial in \(m,\tau,L,k\), or is it NP-hard under polynomial-time Turing reductions?
For discrete evidence, aggregation of valuations is established as normalized pointwise multiplication with correction for repeated inclusion of the prior, under a noncolluding strategy model; this is a semantic decomposition result, not a bit-complexity classification ([source](https://www.ifaamas.org/Proceedings/aamas2015/aamas/p563.pdf)).
No result settling the precise rational-mass computation problem above was located in the literature search.
The weighted-evidence valuation is computable in deterministic time polynomial in \(m,\tau,L,k\), including for arbitrary positive rational masses.
The proof uses rational approximations to log weights, followed by a stable normalization. It applies directly to the explicit likelihood tables specified in the question. The prior-corrected aggregation established in the [cited paper](https://www.ifaamas.org/Proceedings/aamas2015/aamas/p563.pdf) supplies semantic motivation; the bit-complexity argument below is independent of that decomposition.
Consequently, NP-hardness under polynomial-time Turing reductions would imply \(\mathrm P=\mathrm{NP}\).
Define the active set
\[ I=\{f\in F:\pi(f)>0\text{ and }\ell_t(f)>0\text{ for every }t\in T\}. \]
Because every listed mass is positive, \(a_f>0\) holds exactly when \(f\in I\). Thus \(Z>0\) is equivalent to \(I\ne\varnothing\). The active set can be determined by inspecting the rational inputs, and inactive strategies have valuation exactly zero.
For \(f\in I\), define the real log score
\[ s_f=\log\pi(f)+\sum_{t\in T}w_t\log\ell_t(f), \]
where \(\log\) denotes the natural logarithm. The specified power-likelihood definition gives
\[ a_f=e^{s_f}, \qquad \nu(f)=\frac{e^{s_f}}{\sum_{g\in I}e^{s_g}}. \]
Each positive input rational lies between \(2^{-L}\) and \(2^L\), since its numerator and denominator each have at most \(L\) bits. In particular, \(w_t\le 2^L\). Although scores can therefore have exponentially large magnitude, their integer parts require only polynomially many bits: indeed,
\[ |s_f|\le L(1+\tau2^L). \]
We first give an explicit rational algorithm for approximating a positive input rational \(x\) to absolute logarithmic error \(2^{-p}\).
Choose an integer \(h\) such that
\[ x=2^h y,\qquad 1\le y<2. \]
Binary lengths and exact rational comparisons determine \(h\) in polynomial time. The input bounds imply \(|h|\le L\), and \(y\) has \(O(L)\) bits.
For \(0\le z\le 1/3\), define
\[ H_N(z)=2\sum_{j=0}^{N-1}\frac{z^{2j+1}}{2j+1}. \]
Integrating the geometric expansion of \(2/(1-z^2)\) gives
\[ \log\frac{1+z}{1-z} = 2\sum_{j=0}^{\infty}\frac{z^{2j+1}}{2j+1}. \]
The tail satisfies
\[ 0\le \log\frac{1+z}{1-z}-H_N(z) \le 2\sum_{j=N}^{\infty}(1/3)^{2j+1} = \frac34\,9^{-N}. \]
Set \(z=(y-1)/(y+1)\), so \(0\le z<1/3\). Since \(z=1/3\) corresponds to \(y=2\), the rational number
\[ R_x=hH_N(1/3)+H_N(z) \]
satisfies
\[ |R_x-\log x| \le (L+1)\frac34\,9^{-N}. \]
Choosing
\[ N=p+\lceil\log_2(L+1)\rceil+2 \]
makes this error at most \(2^{-p}\).
This calculation has polynomial bit complexity. A summand has \(O(NL+\log N)\) bits; using the product of the summand denominators as a common denominator yields \(O(N^2L+N\log N)\) bits. Therefore exact evaluation of the finite rational sums takes time polynomial in \(L,p\).
Choose
\[ p=k+L+\lceil\log_2(\tau+1)\rceil+4. \]
Approximate every logarithm needed for the active strategies using Section 2, with absolute error at most \(2^{-p}\). Combine these rational approximations with the exact rational masses to obtain rational scores \(r_f\).
For every \(f\in I\),
\[ |r_f-s_f| \le \left(1+\sum_{t\in T}w_t\right)2^{-p} \le (1+\tau2^L)2^{-p} \le 2^{-(k+4)}. \]
Write \(\varepsilon=2^{-(k+4)}\).
There are at most \(m(\tau+1)\) logarithm evaluations. Multiplication by the masses and summation preserve polynomial bit length: the bit length of a product denominator is the sum of the bit lengths of its factors. Hence all \(r_f\) can be computed in time polynomial in \(m,\tau,L,k\).
Define the ideal normalized distribution associated with the approximate scores by
\[ \rho(f)=\frac{e^{r_f}}{\sum_{g\in I}e^{r_g}}. \]
From \(|r_f-s_f|\le\varepsilon\), both the individual weights and their sums differ multiplicatively by factors between \(e^{-\varepsilon}\) and \(e^\varepsilon\). Therefore
\[ e^{-2\varepsilon} \le \frac{\rho(f)}{\nu(f)} \le e^{2\varepsilon}. \]
Consequently,
\[ |\rho(f)-\nu(f)|\le e^{2\varepsilon}-1. \]
For \(0\le x\le1\), the exponential series gives \(e^x-1\le(e-1)x<2x\). Since \(2\varepsilon\le1\),
\[ |\rho(f)-\nu(f)| \le4\varepsilon = \frac14\,2^{-k}. \]
This bound requires no separation between scores and no lower bound on \(Z\).
Compute the rational maximum \(M=\max_{f\in I}r_f\), and set
\[ u_f=r_f-M,\qquad b_f=e^{u_f}. \]
Every \(u_f\le0\), every \(b_f\in(0,1]\), and at least one \(b_f=1\). Furthermore,
\[ \rho(f)=\frac{b_f}{\sum_{g\in I}b_g}. \]
Choose the integer cutoff and error tolerance
\[ H=k+\lceil\log_2(m+1)\rceil+4, \qquad \delta=2^{-H}. \]
We construct rational numbers \(c_f\in[0,1]\) satisfying \(|c_f-b_f|\le\delta\).
Case 1: \(u_f<-H\). Set \(c_f=0\). Since \(e>2\),
\[ |c_f-b_f|=e^{u_f}<e^{-H}<2^{-H}=\delta. \]
Case 2: \(-H\le u_f\le0\). Let \(d=6H\), and evaluate the rational Taylor polynomial
\[ P_f=\sum_{j=0}^{d-1}\frac{u_f^j}{j!}. \]
Taylor’s theorem, with \(e^v\le1\) between \(u_f\) and zero, gives
\[ |P_f-e^{u_f}|\le\frac{|u_f|^d}{d!}\le\frac{H^d}{d!}. \]
To bound the factorial, monotonicity of \(\log x\) gives
\[ \log(d!) \ge\int_1^d\log x\,dx =d\log d-d+1. \]
Thus \(d!\ge(d/e)^d\ge(d/3)^d\), using \(e<3\). Hence
\[ |P_f-e^{u_f}| \le \left(\frac{3H}{d}\right)^d = 2^{-d} \le\delta. \]
Set \(c_f=\min\{1,\max\{0,P_f\}\}\). Clipping to \([0,1]\) cannot increase distance from \(b_f\in[0,1]\).
The Taylor degree is \(O(k+\log m)\). Because \(u_f\) has polynomial bit length, exact rational evaluation of this polynomial also has polynomial bit complexity.
When \(u_f=0\), the polynomial and the clipped result are exactly one. Therefore, writing
\[ S=\sum_{g\in I}b_g,\qquad C=\sum_{g\in I}c_g, \]
we have \(S\ge1\), \(C\ge1\), and \(|S-C|\le m\delta\).
Define the computable rational probabilities \(q_f=c_f/C\). Then
\[ \left|q_f-\rho(f)\right| \le \frac{|c_f-b_f|}{C} + \frac{b_f|S-C|}{CS} \le (m+1)\delta \le \frac1{16}\,2^{-k}. \]
Thus exponentiation and normalization contribute at most this additional error.
For each active strategy, output
\[ \widehat\nu(f) = 2^{-(k+2)} \left\lfloor 2^{k+2}q_f\right\rfloor. \]
For inactive strategies, output zero. The rounding uses exact integer arithmetic and satisfies
\[ |\widehat\nu(f)-q_f|\le2^{-(k+2)}=\frac14\,2^{-k}. \]
Combining the three error bounds, for every active strategy,
\[ |\widehat\nu(f)-\nu(f)| \le \left(\frac14+\frac1{16}+\frac14\right)2^{-k} = \frac9{16}\,2^{-k} < 2^{-k}. \]
Inactive strategies have zero error.
All operations use polynomially many rational arithmetic steps on numbers with polynomial bit length. Each output has \(O(k)\) bits. The algorithm therefore meets both the required accuracy and the polynomial running-time bound.
The argument covers integer masses, arbitrary positive rational masses, and empty evidence. No assumption on total mass is needed.
⟨structured verdict parsed — rendered above⟩
The proof is correct and rigorous. It establishes a deterministic algorithm with running time polynomial in \(m,\tau,L,k\) for the stated approximation problem, including arbitrary positive rational masses. No major or minor mathematical issues were found.
The characterization of \(I\) is correct: a strategy has positive weight exactly when its prior and all its likelihoods are positive, because every listed mass is positive. Consequently, \(Z>0\) is equivalent to \(I\neq\varnothing\).
Determining \(I\) requires only inspecting the explicit rational inputs. Setting all inactive outputs to zero is exact. For active strategies, the logarithmic representation of \(a_f\) and its normalization follows directly from the given power-likelihood definition.
A positive rational whose numerator and denominator have at most \(L\) bits lies between \(2^{-L}\) and \(2^L\). Thus its absolute natural logarithm is at most \(L\), and each mass is at most \(2^L\). The displayed bound
\[
|s_f|\le L(1+\tau2^L)
\]
is therefore valid.
The distinction between exponentially large numerical magnitude and polynomial representation length is handled correctly. The algorithm never attempts to represent the unnormalized exponential weights exactly.
The binary scaling \(x=2^hy\), with \(1\le y<2\), can be found using integer bit lengths and exact rational comparisons. The bounds on \(h\) and the representation length of \(y\) are valid.
The logarithm series applies throughout the stated interval. Its tail computation is correct:
\[
2\sum_{j=N}^{\infty}(1/3)^{2j+1}=\frac34\,9^{-N}.
\]
Substituting \(z=(y-1)/(y+1)\) gives the required logarithm of \(y\), while substituting \(1/3\) gives the logarithm of \(2\). Multiplication by a possibly negative \(h\) is correctly handled by the absolute-error bound.
The chosen \(N\) suffices for error at most \(2^{-p}\). The stated summand and common-denominator bit bounds are polynomial in \(L,p\), so exact evaluation does have polynomial bit complexity.
The logarithm errors are correctly amplified by the exact masses:
\[
|r_f-s_f|\le(1+\tau2^L)2^{-p}.
\]
With the stated choice of \(p\), this is at most \(2^{-(k+4)}\). This includes the case \(\tau=0\).
There are at most \(m(\tau+1)\) logarithm evaluations. Multiplying their rational outputs by the input masses and summing them preserves polynomial bit length, as claimed.
The score-error bound implies the stated multiplicative bounds on individual weights and their sums, hence
\[
e^{-2\varepsilon}\le\frac{\rho(f)}{\nu(f)}\le e^{2\varepsilon}.
\]
These ratios are well-defined because all active strategies have positive valuation.
The resulting absolute-error bound is valid. The exponential-series inequality applies because \(2\varepsilon\le1\), and the constants give
\[
|\rho(f)-\nu(f)|\le4\varepsilon=\frac14\,2^{-k}.
\]
Neither a score-separation assumption nor a positive quantitative lower bound on \(Z\) is required.
The maximum of the rational approximate scores can be computed exactly. Subtracting it ensures all shifted arguments are nonpositive and at least one is exactly zero.
For \(u_f<-H\), discarding the corresponding exponential incurs error strictly below \(2^{-H}\). The cutoff uses natural exponential arguments consistently; the comparison follows from \(e>2\).
Taylor’s theorem is applied with its hypotheses satisfied: the exponential has all required derivatives, and each derivative is at most one on the interval between \(u_f\) and zero. Thus the remainder bound
\[
|P_f-e^{u_f}|\le\frac{|u_f|^d}{d!}
\]
is correct.
The integral estimate for \(\log(d!)\), the use of \(e<3\), and the substitution \(d=6H\) all check out. They yield error at most \(2^{-d}\le\delta\).
Clipping cannot increase error relative to a value in \([0,1]\). Exact rational evaluation has polynomial bit complexity because both the degree and the argument’s representation length are polynomially bounded.
At a maximizing strategy, \(u_f=0\), so the computed weight is exactly one. Consequently, both normalization denominators satisfy \(S,C\ge1\); division by a small computed denominator is avoided.
The bounds \(|S-C|\le m\delta\) and
\[
|q_f-\rho(f)|\le(m+1)\delta\le\frac1{16}\,2^{-k}
\]
follow correctly from the displayed decomposition. All divisions are by positive quantities.
The floor operation produces the required dyadic outputs using exact integer arithmetic. Its error is at most \(\frac14\,2^{-k}\).
The accumulated error is correctly computed as
\[
\frac9{16}\,2^{-k}<2^{-k}.
\]
The task does not require the dyadic outputs to sum exactly to one, so the use of independent downward rounding is permissible.
The number of operations and the bit lengths of their operands are polynomial in the stated parameters. The unary encoding of \(k\) is consistent with the precision-dependent work and output length.
Empty evidence, a single active strategy, zero priors or likelihoods, and unrestricted total mass are all covered. The cited semantic decomposition is not used as a theorem in the computational proof.
The consequence concerning NP-hardness under polynomial-time Turing reductions is correct for this polynomial-time approximation task. No additional clarification or repair is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.