Answer: Polynomial time in \(T,\tau,L,E\). Exact prediction and posterior maintenance take \(O(L+\tau L^2+T\tau(E+L))\) bit operations using integer ratios whose numerators and denominators have \(O(L)\) bits.
Proposition 3.1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithms 3, 4 and 5 can be implemented in time complexity O(T|H|). The preceding positive result, however, cannot be applied for Al- gorithm 6. Indeed, at each step t, Algorithm 6 requires computing the Dempster combination of two non-binary mass functions: in par- ticular, my is simple, while mt is separable, i.e. obtained as the Dempster combination of simple mass functions [44]. Unfortunately, in general and without any further assumption on H, this problem is known to be #P-complete [42], even for simple mass functions [43].
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support \(S\) of \(\tau\) evaluable binary prediction policies, a rational distribution \(\mu\) over \(S\), and a realizable sequence of \(T\) labeled cases, compute each online prediction by choosing the label with at least as much mass among policies consistent with prior cases, and update the posterior mass after each label. What exact running time and bit complexity suffice in \(T\), \(\tau\), the rational input length \(L\), and the policy evaluation cost?
A society is given by its support: a list \(S\) of \(\tau\geq1\) distinct types with positive binary-rational masses \(\mu(h)\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each type is a deterministic, evaluable binary prediction policy \(h:(X\times\{0,1\})^*\times X\to\{0,1\}\), where cases in \(X\) have finite encodings; the label-domain size is \(m=2\).
There are \(T\geq1\) rounds. At round \(t\), the learner receives \(x_t\), predicts before receiving \(y_t\), and then observes \(y_t\). Write \(z_{t-1}=((x_1,y_1),\ldots,(x_{t-1},y_{t-1}))\).
The sequence is realizable: some \(h\in S\) satisfies \(h(z_{t-1},x_t)=y_t\) for every \(t\).
Initialize \(p_1(h)=\mu(h)\). Predict \(1\) exactly when \(\sum_{h:h(z_{t-1},x_t)=1}p_t(h)\geq\sum_{h:h(z_{t-1},x_t)=0}p_t(h)\); otherwise predict \(0\).
After observing \(y_t\), maintain exactly \(p_{t+1}(h)=p_t(h)\mathbf{1}\{h(z_{t-1},x_t)=y_t\}/\sum_{g:g(z_{t-1},x_t)=y_t}p_t(g)\). Realizability ensures a positive denominator.
Let \(L\) be the total binary input length, including masses, policy descriptions and cases, and let \(E\) bound the bit-operation cost of one policy evaluation on an actual history and current case.
Is this exact online prediction and posterior-maintenance problem solvable in polynomial time in \(T,\tau,L,E\), or is it NP-hard? What running-time and bit-complexity bounds suffice, with \(m=2\)?
Known discrete result: uniform-prior Halving can be implemented in time \(O(T|H|)\) for an explicitly listed finite expert set \(H\).
That result does not specify exact rational bit-complexity bounds for the arbitrary-prior problem defined here.
The problem is solvable in polynomial time in \(T,\tau,L,E\). With ordinary binary encodings of rational numbers, a sufficient running-time bound is
\(O\!\left(L+\tau L^2+T\tau(E+L)\right)\).
All integers used for maintaining the posterior have \(O(L)\) bits.
The key is to retain the original masses of surviving types and maintain one shared normalization denominator. There is no need to multiply successively computed posterior fractions.
Index the support as \(S=\{h_1,\ldots,h_\tau\}\), and write each input mass as \(\mu(h_i)=a_i/b_i\), where \(a_i,b_i\) are positive integers encoded in binary. This includes dyadic masses. Because the masses sum to \(1\), each \(a_i\leq b_i\).
Let \(\ell(b_i)\) denote the binary length of \(b_i\). Define
\(B=1+\sum_{i=1}^{\tau}\ell(b_i)\),
\(Q=\prod_{i=1}^{\tau}b_i\), and
\(w_i=a_i(Q/b_i)\).
These definitions have the following consequences:
The denominator encodings form part of the input, so \(B=O(L)\).
Using schoolbook integer arithmetic, multiplying or dividing integers of at most \(B\) bits costs \(O(B^2)\) bit operations. Computing \(Q\), then each exact quotient \(Q/b_i\) and weight \(w_i\), therefore costs \(O(\tau B^2)\) bit operations. This is a sufficient bound; no fast arithmetic is required.
Posterior probabilities will be represented as ratios of binary integers. Even dyadic priors can yield non-dyadic posteriors: surviving masses \(1/4\) and \(1/2\) normalize to \(1/3\) and \(2/3\).
For each round \(t\), let \(V_t\) be the indices consistent with all previous observations:
\(V_t=\{i:h_i(z_{s-1},x_s)=y_s\text{ for every }1\leq s<t\}\).
Set \(W_t=\sum_{i\in V_t}w_i\).
We maintain the exact representation
\(p_t(h_i)=w_i/W_t\) for \(i\in V_t\), and \(p_t(h_i)=0\) otherwise.
We prove this invariant by induction.
Initially, \(V_1=\{1,\ldots,\tau\}\) and \(W_1=Q\). Thus \(p_1(h_i)=w_i/Q=a_i/b_i=\mu(h_i)\), as required.
Suppose the invariant holds at round \(t\). After observing \(y_t\), define
\(V_{t+1}=\{i\in V_t:h_i(z_{t-1},x_t)=y_t\}\).
The update’s denominator is exactly
\(\sum_{i\in V_{t+1}}p_t(h_i)=W_{t+1}/W_t\).
Consequently, each surviving type receives posterior
\((w_i/W_t)/(W_{t+1}/W_t)=w_i/W_{t+1}\),
and every other type receives posterior zero. This proves the induction step.
Realizability supplies an index \(i^\star\) consistent with every observed round. Hence \(i^\star\in V_t\) for every \(t\), and \(W_t\geq w_{i^\star}>0\). All normalizations are therefore defined.
At round \(t\), evaluate each surviving policy on the actual history and current case. Compute the two integer sums
\(C_{t,b}=\sum_{\{i\in V_t:h_i(z_{t-1},x_t)=b\}}w_i\)
for \(b\in\{0,1\}\).
The total posterior mass predicting \(b\) is \(C_{t,b}/W_t\). Because \(W_t>0\), comparing these posterior masses is equivalent to comparing their integer numerators. Predict \(1\) exactly when \(C_{t,1}\geq C_{t,0}\), preserving the specified tie rule.
Store the evaluated prediction of each surviving type. After receiving \(y_t\), discard types whose stored prediction differs from \(y_t\), and set \(W_{t+1}=C_{t,y_t}\). Thus no policy needs to be evaluated twice in the same round.
This implements both the prescribed prediction and the prescribed posterior update exactly.
Each round requires at most \(\tau\) policy evaluations, costing \(O(\tau E)\) bit operations. There are at most \(\tau\) additions of integers having at most \(B\) bits, followed by one comparison and at most \(\tau\) membership updates. The remaining cost is \(O(\tau B)\).
Including preprocessing and input reading, the total cost is therefore
\(O\!\left(L+\tau B^2+T\tau(E+B)\right)
=O\!\left(L+\tau L^2+T\tau(E+L)\right)\).
The posterior can be stored using one numerator per type—either \(w_i\) or zero—and the shared positive denominator \(W_t\). Numerators and the denominator each have at most \(B=O(L)\) bits. Posterior storage therefore requires \(O(\tau L)\) bits, in addition to the input, retained history, and policy-evaluation workspace.
If every posterior must be explicitly emitted after every round, output the fractions \(w_i/W_t\) for survivors and \(0/1\) otherwise. This adds \(O(T\tau B)\) output bits and bit operations, already covered by the bound above.
If the output convention additionally requires each fraction to be reduced, a simple sufficient bound is
\(O\!\left(L+\tau B^2+T\tau(E+B^3)\right)\).
Indeed, the Euclidean algorithm uses \(O(B)\) divisions: every two successive remainder steps reduce the remainder by at least a factor of two. Each schoolbook division costs \(O(B^2)\), giving \(O(B^3)\) per reduction. Reduction is unnecessary for exact maintenance.
There is no additional combinatorial search over types: the explicitly listed support is scanned directly. Arbitrary rational priors introduce polynomial integer-arithmetic costs.
The qualification involving \(E\) matters. Evaluable policies need not have polynomial evaluation cost in their description length. The bound establishes polynomial time in the parameters requested; when policy evaluation is itself polynomially bounded in the input size, it gives a polynomial-time algorithm in the usual input-length sense. NP-hardness under polynomial-time reductions in that regime would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly: exact prediction and posterior maintenance are polynomial in \(T,\tau,L,E\). The stated arithmetic and storage bounds are sufficient. No major or minor issues were found.
\[
O\!\left(L+\tau L^2+T\tau(E+L)\right)
\]
is sufficient. The shared-denominator representation uses \(O(\tau L)\) posterior-storage bits. The claim about \(O(L)\)-bit integers concerns posterior maintenance; the write-up correctly accounts for policy-evaluation workspace separately.
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.