Answer: Polynomial-time solvable: \(O\!\left(L^4+(m+d)L^3(d+1)^2+\tau^2\right)\) bit operations suffice, and hence \(O(L^6)\) suffices under the stated encoding.
Theorem 3 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateLet ⪰∈L(2N) and A ⊆N. We have that R⪰, ˆw A = ˆR⪰ A.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of types \(T\), positive rational masses \(\mu_t\) summing to \(1\), and an explicitly represented rational polynomial \(F\) on a neighborhood of \([0,\mu]\), with \(\partial_t F(\mu/2)\ne 0\) for every \(t\), return the total preorder \(t\succeq u\) iff \(\operatorname{sgn}(\partial_t F(\mu/2))\ge \operatorname{sgn}(\partial_u F(\mu/2))\). This asks for the limiting ordinal Banzhaf ranking when each finite-population context includes each other member independently with probability \(1/2\), and coalition power is given by \(F\) of its type-mass vector.
A society is given by its support: a nonempty list \(T\) of \(\tau\) 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.
The input also contains a rational polynomial \(F\) in the \(m=\tau\) type-mass coordinates, represented by an explicit list of monomials with binary-rational coefficients and unary nonnegative integer exponents. Let \(L\) be the total input bit length and \(d\) the total degree.
Coalition mass vectors lie in \([0,\mu]=\prod_{t\in T}[0,\mu_t]\); higher values of \(F\) mean greater coalition power, and equal values mean indifference. Values and coefficients may have either sign; no monotonicity or normalization of \(F\) is imposed.
Assume \(\partial_tF(\mu/2)\ne0\) for every \(t\in T\). Return the total preorder defined by \(t\succeq u\iff\operatorname{sgn}(\partial_tF(\mu/2))\ge\operatorname{sgn}(\partial_uF(\mu/2))\); equal signs give tied types.
Is computing this preorder solvable in polynomial time, or is it NP-hard? State running times in \(m,\tau,L,d\).
For finite societies with a strict total order of coalitions, ranking individuals by the sum of their ordinal marginal contributions agrees with weighted majority comparisons: each comparison's weight counts the coalitions obtained by adding neither or both compared individuals that lie strictly between the two single-addition coalitions. This is an equivalence result, with no complexity classification ([Khani–Moretti–Öztürk](https://www.ijcai.org/proceedings/2019/0054.pdf)).
No result settling exactly the continuous computation above was located in the literature search.
Computing the requested preorder is polynomial-time solvable, even when \(m=\tau\) is part of the input. The algorithm evaluates the derivative signs exactly, so cancellation and arbitrarily small nonzero derivative values cause no difficulty.
A conservative running-time bound, using schoolbook integer arithmetic, is
\(O\!\left(L^4+(m+d)L^3(d+1)^2+\tau^2\right)\)
bit operations. The \(\tau^2\) term applies if the output is the full comparison matrix; an ordered list of tied classes avoids that term. Since \(m=\tau\le L\) and unary exponents imply \(d\le L\), this gives an \(O(L^6)\) bound.
Write the polynomial as
\(F(x)=\sum_{j=1}^{s}c_j\prod_{t=1}^{m}x_t^{\alpha_{jt}},\)
where \(s\le L\), every \(\alpha_{jt}\) is a nonnegative integer, and \(k_j:=\sum_t\alpha_{jt}\le d\).
All rational denominators below are chosen positive. Write \(c_j=u_j/v_j\), and set
\(C:=\prod_{j=1}^{s}v_j,\qquad A_j:=u_j(C/v_j).\)
Then \(C\) is positive and \(A_j\) is an integer, with \(c_j=A_j/C\). If the input contains repeated exponent vectors, combine their integer coefficients \(A_j\), and discard zero coefficients. This preserves the common denominator \(C\). Henceforth the displayed list is the resulting polynomial, whose degree is \(d\). The nonzero-derivative promise implies \(d\ge1\).
For the evaluation point \(q:=\mu/2\), write \(q_t=a_t/b_t\), and define
\(B:=\prod_{t=1}^{m}b_t,\qquad p_t:=a_t(B/b_t).\)
Thus \(q_t=p_t/B\). Positive masses give \(p_t>0\), and \(\sum_t\mu_t=1\) implies \(q_t\le1/2\), so \(p_t\le B/2\).
The total binary lengths of the input numerators and denominators are bounded by \(L\). Forming the midpoint denominators adds only \(O(m)\) bits. Consequently, \(B,C,p_t\), and \(A_j\) all have \(O(L)\) bits. Combining coefficients preserves this bound: each combined coefficient is a sum of at most \(L\) integers of \(O(L)\) bits.
For each monomial, compute the positive integer
\(P_j:=B^{d-k_j}\prod_{u=1}^{m}p_u^{\alpha_{ju}}.\)
For each coordinate, compute the signed integer
\(R_t:=\sum_{j=1}^{s}\alpha_{jt}A_jP_j.\)
We claim that
\(\displaystyle \partial_tF(q)=\frac{R_t}{C\,p_t\,B^{d-1}}.\)
To verify this, consider a monomial with \(\alpha_{jt}>0\). Its contribution to the expression on the right is
\(\displaystyle \frac{\alpha_{jt}A_jB^{d-k_j}\prod_u p_u^{\alpha_{ju}}} {C\,p_t\,B^{d-1}} = \frac{A_j}{C}\,\alpha_{jt} \left(\frac{p_t}{B}\right)^{\alpha_{jt}-1} \prod_{u\ne t}\left(\frac{p_u}{B}\right)^{\alpha_{ju}}, \)
which is exactly its contribution to \(\partial_tF(q)\). When \(\alpha_{jt}=0\), both contributions are zero. Summing proves the identity.
Because \(C,p_t,B\) are positive,
\(\operatorname{sgn}(\partial_tF(\mu/2))=\operatorname{sgn}(R_t).\)
Thus the algorithm only needs exact integer sign tests.
The preceding construction must be checked in the bit model; counting arithmetic operations alone would not suffice.
Since \(p_t\le B\) and the total number of factors in \(P_j\), counted with multiplicity, is \(d\),
\(0<P_j\le B^d.\)
Hence every \(P_j\) has \(O(Ld)\) bits. Also,
\(\displaystyle |R_t|\le s\,d\,\max_j|A_j|\,B^d.\)
Therefore every \(R_t\), and every partial sum used to compute it, has
\(O\!\left(L(d+1)+\log s+\log(d+1)\right)=O(L(d+1))\)
bits. Products can likewise be formed without exceeding this bound, by multiplying the factors of each \(P_j\) successively.
Denominator clearing and combining duplicate monomials take \(O(L^4)\) bit operations under a conservative implementation. Thereafter:
The total is \(O(s(m+d))\) arithmetic operations on integers of \(O(L(d+1))\) bits. Schoolbook multiplication takes quadratic time in that bit length; addition and comparison take no longer. Thus evaluation costs
\(O\!\left(s(m+d)L^2(d+1)^2\right) \subseteq O\!\left((m+d)L^3(d+1)^2\right).\)
This proves the stated polynomial bit bound. In particular, neither negative coefficients nor cancellation require numerical approximation.
Define
\(T_+:=\{t:R_t>0\},\qquad T_-:=\{t:R_t<0\}.\)
The promise ensures these sets partition \(T\). Return the nonempty classes in the order \(T_+,T_-\), with all types within each class tied. This is correct because positive derivative signs exceed negative derivative signs, while equal signs give indifference.
The [Khani–Moretti–Öztürk paper](https://www.ijcai.org/proceedings/2019/0054.pdf) concerns ordinal comparisons of finite coalitions. Its weighted-comparison representation is not needed here: the explicitly prescribed continuous preorder follows directly from polynomial-time exact evaluation.
⟨structured verdict parsed — rendered above⟩
The argument is correct and resolves the assigned task. It gives an exact polynomial-time algorithm under the stated encoding, including when \(m=\tau\) varies with the input. No major or minor mathematical gaps were found.
The common denominators \(C=\prod_j v_j\) and \(B=\prod_t b_t\) are positive integers. Their bit lengths are bounded by the sums of the bit lengths of their factors, hence by \(O(L)\). Replacing each mass by its midpoint adds only \(O(m)\) bits.
The divisions \(C/v_j\) and \(B/b_t\) are exact. Thus \(A_j\) and \(p_t\) are integers of \(O(L)\) bits. Combining at most \(L\) coefficients increases their bit lengths by at most \(O(\log L)\), preserving the asserted bound.
Combining duplicate monomials and removing zero coefficients preserves the polynomial. If this reduces its degree, using the resulting degree is legitimate and only improves the bounds in terms of the original input degree. The derivative promise excludes a constant polynomial, so \(d\ge1\).
Positive masses imply \(q_t>0\), hence \(p_t>0\). Since the masses sum to one, \(q_t\le1/2\), giving \(p_t\le B/2\).
Therefore the division by \(p_t\) in the derivative identity is valid for every coordinate, including when \(m=\tau=1\). All exponents \(d-k_j\) are nonnegative.
For a monomial with \(\alpha_{jt}>0\), its contribution to the proposed expression is
\[
\frac{\alpha_{jt}A_jB^{d-k_j}\prod_u p_u^{\alpha_{ju}}}
{Cp_tB^{d-1}}.
\]
Cancelling the displayed factors gives exactly the monomial’s derivative evaluated at \(q\), as shown in the output. In particular, the remaining power of \(B\) is \(B^{1-k_j}\), matching the total degree \(k_j-1\) of that derivative monomial.
When \(\alpha_{jt}=0\), both contributions vanish. Thus summing establishes the claimed identity for every coordinate. Its denominator is strictly positive, so the sign equality is correct.
Each \(P_j\) contains exactly \(d\) factors counted with multiplicity, each at most \(B\). Hence \(0<P_j\le B^d\), and its bit length is \(O(Ld)\). Successive multiplication of these positive integer factors respects the same bound.
The estimate
\[
|R_t|\le sd\max_j|A_j|B^d
\]
follows by bounding each summand’s absolute value. The same estimate bounds every partial sum, regardless of cancellation. Consequently, the asserted \(O(L(d+1))\) bit bound is valid for summands, sums, and the relevant intermediate products.
Exact integer arithmetic therefore handles negative coefficients and arbitrarily small nonzero derivative values without a precision assumption.
Computing \(P_j\) requires scanning its exponents and performing at most \(d\) multiplications. Processing its contributions to all coordinates requires \(O(m)\) arithmetic operations. This supports the total \(O(s(m+d))\) arithmetic-operation count.
Schoolbook arithmetic on integers of \(O(L(d+1))\) bits yields the stated evaluation bound
\[
O\!\left((m+d)L^3(d+1)^2\right),
\]
using \(s\le L\). The conservative \(O(L^4)\) preprocessing allowance covers denominator clearing and duplicate-monomial consolidation.
Producing a full comparison matrix takes \(O(\tau^2)\) additional operations. Producing the ordered tied classes requires only scanning and listing the types. Finally, \(m=\tau\le L\) and unary exponents give \(d\le L\), so the claimed \(O(L^6)\) bound follows.
The promise guarantees \(R_t\ne0\), so \(T_+\) and \(T_-\) partition the support. Returning their nonempty classes in that order implements exactly the requested sign comparison. It also handles the cases where either class is empty.
The finite-society equivalence is not used as a theorem in the algorithm or its analysis. No complexity inference from that equivalence is needed.
None is required. The polynomial-time conclusion and the stated running-time bounds are justified.
⟨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.