Answer: polynomial-time solvable
Theorem 2.1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateConsider a tournament T = (V, E) where K ∈V is a king. Let A = Nout(K) and B = V \(A ∪{K}) = Nin(K). Suppose that B is a disjoint union of three (possibly empty) sets H, I, J such that 1. |H| < |A| 2. inA(i) ≥log |V | for all i ∈I (i.e., outA(i) ≤|A| −log |V | for all i ∈I) 3. out(j) ≤|A| for all j ∈J. Then K is an SE winner, and we can compute a winning seeding for K in polynomial time. Note that the superking result [Vas10] corresponds to the special case where H = J = ∅, while the “king of high out-degree” result [SV11a] corresponds to the special case where I = ∅.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(n=2^k\) candidates \(V\), a target \(K\), and a distribution \(\mu\) with binary-rational masses over \(\tau\) strict rankings of \(V\), orient each pair by its strict majority under \(\mu\). Let \(A\) be the candidates that beat \(K\), and \(B\) those that beat \(K\)'s opponents but lose to \(K\). If \(K\) is a king and \(B=H\mathbin{\dot\cup}I\mathbin{\dot\cup}J\) with \(|H|<|A|\), \(\mathrm{in}_A(i)\ge\log n\) for every \(i\in I\), and \(\mathrm{out}(j)\le|A|\) for every \(j\in J\), find a balanced seeding in which \(K\) wins. What is the running time in \(n,\tau,L\), where \(L\) is the mass bit length?
Let \(V\) contain \(m=n=2^k\) candidates, with \(k\ge0\), and let \(K\in V\).
A society is given by its support: a list of \(\tau\) distinct strict rankings of \(V\), each with positive binary-rational mass; masses sum to \(1\). Here \(\tau\) is the support size, not the number of possible rankings, and \(L\) is the total bit length of the masses.
Write \(u\succ v\) when the mass ranking \(u\) above \(v\) exceeds \(1/2\); promise that no pair has equal support, so every match has a unique winner.
Define \(A=\{a:K\succ a\}\), \(B=\{b:b\succ K\}\), \(\mathrm{in}_A(v)=|\{a\in A:a\succ v\}|\), and \(\mathrm{out}(v)=|\{u\in V:v\succ u\}|\).
Promise that \(K\) is a king: every other candidate is beaten by \(K\), or by some candidate beaten by \(K\).
A partition \(B=H\mathbin{\dot\cup}I\mathbin{\dot\cup}J\) is supplied, allowing empty parts, with \(|H|<|A|\), \(\mathrm{in}_A(i)\ge\log_2 n\) for every \(i\in I\), and \(\mathrm{out}(j)\le|A|\) for every \(j\in J\).
A seeding assigns each candidate once to a leaf of a balanced single-elimination bracket; each match is won according to \(\succ\).
Is finding a seeding in which \(K\) wins on these promised inputs solvable in polynomial time in \(m=n,\tau,L\), or is it NP-hard?
For an explicitly supplied pairwise tournament, the same king and partition conditions guarantee a winning seeding computable in polynomial time ([source](https://www.cs.cornell.edu/~mpkim/pubs/siam2017-tournaments.pdf)).
No separate result specifically addressing the binary-rational distribution input was located.
Finding a winning seeding is solvable in deterministic polynomial time in \(n,\tau,L\). The distribution input can be converted exactly into an explicit pairwise tournament in polynomial time, after which the cited constructive theorem applies.
For \(n=1\), the strict condition \(|H|<|A|\) is impossible because both sets are empty. Thus there are no promised inputs of that size; the single-candidate bracket would otherwise be trivial. Below, consider \(n\ge 2\).
Write the supplied rankings as \(\pi_1,\ldots,\pi_\tau\), with respective masses \(w_1,\ldots,w_\tau\). For distinct candidates \(u,v\), define
\(s(u,v)=\sum_{\{t:\pi_t\text{ ranks }u\text{ above }v\}}w_t\).
By definition, \(u\succ v\) precisely when \(s(u,v)>1/2\).
We use the ordinary binary encoding of rational numbers: write \(w_t=p_t/q_t\), where the positive integers \(p_t,q_t\) are encoded in binary. A finite binary expansion of a dyadic rational can also be converted to this representation with only a linear increase in encoding length.
Define the positive integer common denominator and integer weights by
\(D=\prod_{t=1}^{\tau}q_t,\qquad W_t=p_t(D/q_t)\).
These quantities are computable by exact integer arithmetic. Their bit lengths are polynomially bounded:
For each unordered candidate pair, compute
\(S(u,v)=\sum_{\{t:\pi_t\text{ ranks }u\text{ above }v\}}W_t\).
Then the exact comparison is
\(u\succ v\quad\Longleftrightarrow\quad 2S(u,v)>D\).
All integers used in this comparison have \(O(L+1)\) bits. Thus even a majority margin that is extremely small causes no precision problem.
Precompute the position of every candidate in every supplied ranking. Each pair then requires at most \(\tau\) position comparisons and integer additions. There are \(\binom n2\) pairs, so constructing the entire adjacency matrix takes polynomial time in \(n,\tau,L\), including the cost of integer arithmetic.
Because each ranking is strict and the masses sum to \(1\), we have \(S(u,v)+S(v,u)=D\). The no-tie promise therefore ensures that exactly one direction is selected for each pair. The resulting directed graph \(T=(V,E)\), with \((u,v)\in E\) exactly when \(u\succ v\), is an explicit tournament.
Theorem 2.1 of Kim, Suksompong, and Vassilevska Williams states that, in a tournament on a power-of-two number of vertices, a king \(K\) has a polynomial-time computable winning balanced seeding whenever its inneighborhood admits the supplied three-part partition satisfying the inequalities in this question. The paper assumes balanced brackets and power-of-two sizes throughout. [Theorem 2.1 and its constructive proof](https://www.cs.cornell.edu/~mpkim/pubs/siam2017-tournaments.pdf).
Every hypothesis applies to our constructed tournament:
The theorem consequently supplies a balanced winning seeding for \(K\), computable in polynomial time from the explicit tournament.
Run the theorem’s algorithm on \(T\) and return its seeding.
For any fixed seeding, the winner under \(T\) equals the winner under the original society. Indeed, each first-round match has the same two candidates and the same outcome by construction of \(E\). Inductively, every later match receives the same winners from its two child matches and again has the same outcome. Thus the seeding returned by the theorem makes \(K\) win under the original distribution.
Tournament construction takes polynomial time in \(n,\tau,L\), and the subsequent seeding algorithm takes polynomial time in \(n\). Their composition is therefore polynomial in the requested parameters \(m=n,\tau,L\).
The explicit support representation is sufficient: the algorithm processes only the \(\tau\) supplied rankings and never enumerates all possible rankings. No separate structural theorem for binary-rational distributions is needed.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The exact conversion to a pairwise tournament is polynomial in the stated input parameters, and the cited theorem supplies the required winning seeding. No mathematical gaps or false steps were found.
The prover explicitly interprets binary-rational masses using ordinary binary numerator-and-denominator encoding. This is consistent with the task’s explicit support representation and total mass bit length \(L\). Its observation about converting finite binary expansions is also correct: the denominator’s binary length grows only linearly with the number of fractional digits.
For \(n=1\), both \(A\) and \(H\) are empty, so the promise \(|H|<|A|\) fails. Excluding this size therefore discards no promised input. Empty partition parts at larger sizes are allowed by both the task and the cited theorem.
Every step of the tournament construction is valid:
There is no hidden enumeration of rankings beyond the supplied support.
Theorem 2.1 has exactly the required hypotheses: a king \(K\), its outneighborhood \(A\), and a disjoint partition of its inneighborhood into possibly empty sets \(H,I,J\), satisfying the three stated inequalities. It concludes both existence of a winning seeding and polynomial-time computation. The paper’s standing assumptions specify balanced brackets and power-of-two sizes. Its proof uses the identity \(\log n-1=\log(n/2)\), confirming the intended base-two logarithm. [Theorem 2.1, pp. 1755–1756, and preliminaries, p. 1753](https://www.cs.cornell.edu/~mpkim/pubs/siam2017-tournaments.pdf).
The prover checks all hypotheses correctly. Exact preservation of every edge preserves the king property, both neighborhoods, and all degree counts. The supplied partition consequently satisfies the theorem without modification. Invoking this published constructive theorem is sufficient; reproducing its proof is unnecessary.
The induction over bracket rounds is valid. Identical first-round participants have identical match outcomes in the constructed tournament and the society. Identical child winners then give identical participants and outcomes at each subsequent match.
Thus the theorem’s winning seeding also makes \(K\) win under the original distribution. It assigns every candidate once to the leaves of the required balanced bracket.
The polynomial-time construction and polynomial-time seeding algorithm compose to give the claimed complexity in \(m=n,\tau,L\). This establishes the requested polynomial-time alternative for the promised inputs.
No additional lemma, clarification, or correction 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.