Answer: Polynomial-time solvable in \(O(\tau^2L^3)\) bit operations under standard binary rational encoding.
Proposition 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateLet |W | be the number of selected witnesses in Al- gorithm 1 line 3.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of interchangeable witness types \(T\), rational masses \(\mu_t\) summing to one, and indicators \(a_t\) specifying which types are selected for a reputation query, compute the normalized directed pair-query mass \(\lambda_{tu}=a_ta_u\mu_t\mu_u\) for each type pair and its total \(\Lambda=\sum_{t,u}\lambda_{tu}\).
A society is given by its support: a nonempty list \(T\) of \(\tau\) interchangeable witness types with positive binary rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
Each type represents an atomless population of witnesses. An input indicator \(a_t\in\{0,1\}\) specifies whether all witnesses of type \(t\) are selected for the reputation query; the selected population may be empty.
The protocol queries every ordered pair of distinct selected witnesses. Distinct witnesses may have the same type; individual self-pairs have zero product mass, so type pairs \((t,t)\) are included.
The required outputs are the exact binary rational values \(\lambda_{tu}=a_ta_u\mu_t\mu_u\) for every \((t,u)\in T\times T\), and \(\Lambda=\sum_{t,u\in T}\lambda_{tu}\). Normalization is relative to the entire society, without conditioning on selection.
Can this exact computation be performed in time polynomial in \(\tau\) and \(L\), or is it NP-hard?
For a finite selected witness set \(W\), the additional communication cost of querying witness pairs is \(O(|W|^2)\). [Bonnet (2012)](https://doi.org/10.3233/978-1-61499-098-7-187)
No result settling this exact mass-output problem was identified in the literature search.
The exact mass-output problem is polynomial-time solvable. Under the standard encoding of rational numbers by binary numerators and denominators, a direct algorithm takes \(O(\tau^2L^3)\) bit operations, including reduction of every output fraction to lowest terms.
Write each input mass as \(\mu_t=p_t/q_t\), where \(p_t\) and \(q_t\) are positive integers given in binary. Define the selected mass by \(S=\sum_{t\in T}a_t\mu_t\).
By the required definition of the outputs and distributivity of finite sums,
\(\displaystyle \Lambda=\sum_{t\in T}\sum_{u\in T}a_ta_u\mu_t\mu_u=\left(\sum_{t\in T}a_t\mu_t\right)^2=S^2.\)
The sum includes the terms with \(t=u\), as required. Distinct witnesses of the same type contribute to those terms; the problem explicitly stipulates that individual self-pairs have zero product mass.
If selection is empty, then \(S=0\), every \(\lambda_{tu}=0\), and \(\Lambda=0\). No conditioning or division by the selected mass is needed.
First, for every ordered pair \((t,u)\in T\times T\):
To compute \(\Lambda\), form the common denominator \(Q=\prod_{t\in T}q_t\) and the integer \(P=\sum_{t\in T}a_tp_t(Q/q_t)\). Every division \(Q/q_t\) is exact because \(q_t\) is a factor of \(Q\).
Consequently, \(P/Q=S\). Output \(\Lambda=P^2/Q^2\), reduced to lowest terms, using \(0/1\) when \(P=0\).
These constructions give precisely the required pair masses and total mass.
For a positive integer \(n\), let \(b(n)=\lfloor\log_2 n\rfloor+1\) be its binary length. Because \(L\) is the total input bit length, the combined lengths of the input numerators and denominators are at most \(L\).
For each pair, multiplication produces integers satisfying \(b(p_tp_u)\leq b(p_t)+b(p_u)\leq 2L\) and \(b(q_tq_u)\leq 2L\). Reducing the fraction cannot increase these lengths.
The common denominator also has polynomial size: \(b(Q)\leq\sum_{t\in T}b(q_t)\leq L\). Moreover, the normalization assumption gives the exact integer identity
\(\displaystyle \sum_{t\in T}p_t(Q/q_t)=Q.\)
All summands are positive, and each indicator belongs to \(\{0,1\}\). Thus \(0\leq P\leq Q\). Every partial sum used to construct \(P\) is also at most \(Q\). Therefore all integers involved in constructing \(P,Q,P^2,Q^2\) have \(O(L)\) bits.
Schoolbook multiplication and division of integers with \(O(L)\) bits take \(O(L^2)\) bit operations. The Euclidean algorithm uses \(O(L)\) divisions on such integers, giving the sufficient bound \(O(L^3)\) for each greatest-common-divisor computation.
It follows that:
The total running time is therefore \(O(\tau^2L^3)\), polynomial in both parameters.
The prescribed computation consists entirely of exact rational arithmetic on numbers whose bit lengths remain polynomially bounded. The finite-witness communication cost does not obstruct this algorithm: the required outputs aggregate population mass by the explicitly listed witness types.
This establishes polynomial-time solvability. No literature result or complexity assumption is needed.
⟨structured verdict parsed — rendered above⟩
Result: proved. The prover correctly resolves the prescribed exact mass-output problem with a polynomial-time algorithm. The stated \(O(\tau^2L^3)\) bit-operation bound is valid. No major or minor issues were found.
The algorithm uses the explicitly listed support \(T\), its masses, and the selection indicators. It produces every ordered type-pair output, including diagonal pairs.
This matches the task’s population model: diagonal type pairs remain included, and individual self-pairs require no subtraction. The prover also correctly uses normalization relative to the entire society, without conditioning on selection.
The stated numerator-and-denominator encoding is a standard interpretation of binary rational input. The argument also applies when the input masses are restricted to dyadic rationals.
The identity
\[
\Lambda
=\sum_{t\in T}\sum_{u\in T}a_ta_u\mu_t\mu_u
=\left(\sum_{t\in T}a_t\mu_t\right)^2
=S^2
\]
follows directly from distributivity over finite sums. There are no omitted terms or symmetry factors: the outputs concern ordered pairs.
The empty-selection case is correctly handled. All pair masses and the total mass are zero, and the algorithm never divides by the selected mass.
When either indicator is zero, the required pair mass is zero, represented correctly as \(0/1\).
Otherwise, the constructed fraction
\[
\frac{p_tp_u}{q_tq_u}
\]
equals the required product. Its denominator is positive. Dividing both integers by their greatest common divisor preserves its value and produces a fraction in lowest terms. This also applies when \(t=u\).
The product \(Q=\prod_{t\in T}q_t\) is positive, and every \(q_t\) divides \(Q\). Consequently, each division used to construct \(P\) is exact, and
\[
\frac{P}{Q}
=\sum_{t\in T}a_t\frac{p_t}{q_t}
=S.
\]
Thus \(P^2/Q^2\) gives precisely \(\Lambda\). Reduction preserves that value, and the separate \(P=0\) branch supplies the canonical zero representation.
The pair-product bounds are correct, including repeated factors on diagonal pairs. Reduction cannot increase numerator or denominator lengths.
The bound
\[
b(Q)\leq\sum_{t\in T}b(q_t)\leq L
\]
is also valid, including denominators equal to one.
Normalization yields the stated integer identity
\[
\sum_{t\in T}p_t(Q/q_t)=Q.
\]
Because these summands are positive and selection indicators are zero or one, \(P\), its individual selected summands, and its partial sums are bounded by \(Q\). Intermediate products constructing \(Q\) are likewise bounded by \(Q\), since all factors are positive integers.
Squaring increases bit length by at most a constant factor. Therefore the claimed \(O(L)\) bound on integer sizes is justified.
The stated schoolbook multiplication and division bounds are valid for operands with \(O(L)\) bits. The standard Euclidean algorithm performs \(O(L)\) divisions on such operands, so the conservative \(O(L^3)\) greatest-common-divisor bound is sufficient.
The counts of pair computations, common-denominator operations, reductions, and output bits are correct. Since the support is nonempty, the remaining costs are absorbed by \(O(\tau^2L^3)\).
The finite-witness communication bound does not affect the specified aggregate computation. Polynomial-time solvability is established without a literature result or a complexity assumption.
Required clarification: none.
⟨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.