Answer: \(\mathrm{NP}\)-complete under the stated promises.
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateTFP is NP-hard even when the player of interest v is a king with out(v) = |V | /4.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m=2^k\) candidates, a target \(c^\star\), and a distribution \(\mu\) over \(\tau\) supported complete rankings with binary rational masses, assume every candidate pair has a strict majority and the induced tournament makes \(c^\star\) a king with out-degree \(m/4\). Decide whether there is a balanced single-elimination seeding in which \(c^\star\) wins. The input is the ranking support and masses, with complexity measured in \(m\), \(\tau\), and their bit length \(L\).
Let \(C\) be a set of \(m=2^k\) candidates, with integer \(k\geq 2\), and let \(c^\star\in C\).
A society is given by its support: \(\tau\) distinct strict complete rankings \(R_i\) of \(C\), each with positive binary rational mass \(p_i\), where \(\sum_{i=1}^{\tau}p_i=1\). Here \(\tau\) is the support size, not the number of possible rankings; \(L\) is the total input bit length. State running times in \(m,\tau,L\).
Define \(x\to y\) when \(\sum_{i:x\succ_{R_i}y}p_i>1/2\). Promise that every pair has a strict majority, so these edges form a tournament.
Promise that \(c^\star\) has exactly \(m/4\) outgoing edges and is a king: for every \(y\neq c^\star\), either \(c^\star\to y\) or there exists \(z\) with \(c^\star\to z\to y\).
A seeding assigns each candidate exactly once to the leaves of a complete binary tree of height \(k\); at each internal node, the candidate that beats the other child’s winner advances. The society and match outcomes remain fixed.
Is deciding whether some seeding makes \(c^\star\) win solvable in polynomial time in \(m,\tau,L\), or is it NP-hard, under these promises?
For an explicitly supplied tournament, this decision problem is NP-hard even when the target is a king with out-degree \(m/4\). [Kim and Williams](https://www.ijcai.org/Proceedings/15/Papers/085.pdf)
No result explicitly classifying the supported rational-distribution formulation under these same promises was identified in the search.
The problem is \(\mathrm{NP}\)-complete under the stated promises. The key is that every explicitly supplied tournament can be represented by a rational society with support size \(\tau=O(m^2)\) and total encoding length \(L=O(m^3\log m)\). This representation preserves every match outcome, and therefore both promises and every seeding’s winner.
The construction below uses dyadic masses, so it works whether “binary rational” means a rational encoded in binary or a rational with a finite binary expansion.
Let \(T\) be any tournament on the candidate set \(C\), with \(|C|=m\). Fix an ordering of \(C\).
For each edge \(a\to b\) of \(T\), list the remaining candidates in the fixed order as \(d_1,\ldots,d_{m-2}\), and introduce these two rankings:
\[ a\succ b\succ d_1\succ\cdots\succ d_{m-2}, \qquad d_{m-2}\succ\cdots\succ d_1\succ a\succ b. \]
For an ordered pair \((x,y)\), define its *count margin* in a multiset of rankings as the number ranking \(x\) above \(y\), minus the number ranking \(y\) above \(x\).
The two rankings associated with \(a\to b\) contribute:
Thus this pair of rankings contributes only to its designated edge.
There are \(q=2\binom{m}{2}=m(m-1)\) rankings, counted with multiplicity. For every edge \(x\to y\) of \(T\), the resulting count margin is exactly \(2\): its own gadget contributes \(2\), and every other gadget contributes \(0\).
Let \(M\) be the smallest power of two satisfying \(M\geq q\). Then \(q\leq M<2q\). Since \(m\geq4\), both \(q\) and \(M\) are even.
Choose any ranking \(Q\), and append \((M-q)/2\) copies of the pair consisting of \(Q\) and its reverse. Each appended pair contributes margin \(0\) to every candidate pair. The multiset now contains exactly \(M\) rankings, while every tournament edge still has count margin \(2\).
Give each occurrence mass \(1/M\). For any edge \(x\to y\) of \(T\), let \(N_{xy}\) count occurrences ranking \(x\) above \(y\). Completeness of the rankings and the margin calculation give
\[ N_{xy}+N_{yx}=M, \qquad N_{xy}-N_{yx}=2. \]
Consequently,
\[ \Pr[x\succ y]=\frac{N_{xy}}{M} =\frac12+\frac1M>\frac12. \]
The induced majority tournament is therefore exactly \(T\), with no ties.
Merge identical rankings. If a distinct ranking \(R\) occurs \(n_R\) times, assign it mass \(p_R=n_R/M\). These masses are positive dyadic rationals, and
\[ \sum_R p_R=\frac{\sum_R n_R}{M}=1. \]
Merging preserves all pairwise probabilities. The output therefore has distinct support and satisfies
\[ \tau\leq M<2m(m-1)=O(m^2). \]
Using candidate labels of \(O(\log m)\) bits, each ranking needs \(O(m\log m)\) bits. Each mass needs \(O(\log m)\) bits because both its numerator and denominator are at most \(M=O(m^2)\). Hence
\[ L=O(\tau m\log m)=O(m^3\log m). \]
Generating the rankings and merging duplicates by comparison sorting takes \(O(m^3(\log m)^2)\) bit operations. Indeed, there are \(O(m^2)\) strings of length \(O(m\log m)\), and sorting uses \(O(m^2\log m)\) comparisons.
This proves a polynomial-time representation lemma without assuming that all possible rankings are supplied.
Use the stated explicit-tournament hardness theorem: deciding whether a target can win a balanced single-elimination tournament is \(\mathrm{NP}\)-hard even when the target is a king of out-degree exactly \(m/4\). Kim and Williams state this as Theorem 1, and their preliminaries specify tournament sizes that are powers of two. [Kim and Williams, *Fixing Tournaments for Kings, Chokers, and More*](https://www.ijcai.org/Proceedings/15/Papers/085.pdf)
Take such an instance \((T,c^\star)\), and apply the representation construction from Section 1. Keep the candidate set and target unchanged.
Because the constructed society induces exactly \(T\):
For any particular seeding, its winner is also unchanged. To prove this, induct upward through the bracket. Each leaf contains the same candidate in both formulations. At an internal node, the induction hypothesis gives the same two child winners, and the preserved tournament edge gives the same match winner. Thus the root winner agrees.
It follows that
\[ c^\star\text{ wins some seeding in }T \quad\Longleftrightarrow\quad c^\star\text{ wins some seeding for the constructed society}. \]
The construction has polynomial running time and output length, and always produces an instance satisfying the promises. It is therefore a polynomial-time reduction establishing \(\mathrm{NP}\)-hardness.
A certificate lists the candidates at the leaves in their fixed left-to-right order. Its length is \(O(m\log m)\).
Pairwise majorities can be computed exactly in polynomial time. Write each input mass as \(p_i=a_i/b_i\), with positive integers encoded in binary, and set
\[ D=\prod_{i=1}^{\tau}b_i, \qquad w_i=a_i(D/b_i). \]
The bit length of \(D\) is \(O(L)\), because the sum of the denominator encoding lengths is at most \(L\). For a valid society, \(0<w_i\leq D\) and \(\sum_iw_i=D\).
After recording each candidate’s position in each ranking, determine every majority by the exact comparison
\[ 2\sum_{i:x\succ_{R_i}y}w_i>D. \]
Using elementary integer arithmetic, forming the common denominator and weights takes \(O(\tau L^2)\) bit operations. Computing all pairwise comparisons takes \(O(\tau m^2L)\) bit operations. Thus a sufficient preprocessing bound is
\[ O(\tau L^2+\tau m^2L). \]
The verifier then checks that the certificate is a permutation and evaluates the bracket using \(m-1\) tournament-table lookups.
The input validity conditions are also polynomial-time checkable. In particular, after computing the tournament, the degree and king promises require \(O(m^2)\) table lookups: for each candidate not beaten directly by \(c^\star\), inspect the out-neighbors of \(c^\star\) for a two-edge witness.
Hence the language that rejects invalid inputs and accepts valid promised inputs exactly when a winning seeding exists belongs to \(\mathrm{NP}\). Together with Section 2, this proves the claimed completeness result. A polynomial-time algorithm in \(m,\tau,L\) would therefore imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover’s output resolves the task. The representation construction is correct, preserves all promises and seeding outcomes, and has polynomial output length and running time. The cited hardness theorem applies exactly. The membership argument establishes the stronger claim of \(\mathrm{NP}\)-completeness.
The two-ranking gadget is correct. For the designated edge \(a\to b\), both rankings place \(a\) above \(b\), giving count margin \(2\). Every other unordered pair falls into one of the two cases explicitly checked:
Thus every other pair receives margin \(0\). These cases exhaust the pairs.
Combining the gadgets is correct. There are \(\binom m2\) edges and two occurrences per edge, so \(q=m(m-1)\). For each edge of \(T\), precisely its own gadget contributes margin \(2\); all other gadgets contribute \(0\). Repeated rankings do not affect this multiset calculation.
The padding count is valid. Because \(m\geq4\), \(q\) is a positive even integer. The smallest power of two \(M\geq q\) satisfies \(q\leq M<2q\) and is even. Therefore \((M-q)/2\) is a nonnegative integer.
A ranking and its reverse contribute zero margin to every pair, so padding preserves every margin and produces exactly \(M\) occurrences.
The probability calculation is correct. Strict completeness gives
\[
N_{xy}+N_{yx}=M.
\]
For an edge \(x\to y\), the established margin gives
\[
N_{xy}-N_{yx}=2.
\]
Consequently,
\[
\Pr[x\succ y]=\frac12+\frac1M>\frac12.
\]
Thus every edge is realized in its specified direction, and no pair ties.
Merging duplicates satisfies the support requirement. Each retained ranking has positive multiplicity \(n_R\), hence positive mass \(n_R/M\). The masses sum to \(1\), and merging preserves all pairwise probabilities. Because \(M\) is a power of two, the masses are dyadic under either interpretation of “binary rational” discussed by the prover.
The encoding bounds are valid. There are at most \(M=O(m^2)\) distinct rankings. A ranking requires \(O(m\log m)\) bits with the stated candidate labels; a mass requires \(O(\log m)\) bits. Therefore
\[
L=O(m^3\log m).
\]
The construction time is a valid upper bound. Sorting \(O(m^2)\) ranking strings uses \(O(m^2\log m)\) comparisons, each costing at most \(O(m\log m)\) bit operations. Generating the strings, counting duplicates, and writing their masses fit within the claimed
\[
O(m^3(\log m)^2)
\]
bound.
The external theorem is accurately stated and applicable. Theorem 1 of the cited paper establishes hardness when the distinguished candidate is a king with out-degree exactly one quarter of the tournament size. Its preliminaries restrict tournament sizes to powers of two, and its seeding convention describes the same balanced elimination bracket as the task. Thus there is no mismatch in the degree condition, king condition, or bracket model. [Kim and Williams, Theorem 1 and Section 1.1](https://www.ijcai.org/Proceedings/15/Papers/085.pdf)
Both structural promises are preserved. The representation retains the candidate set, target, and every tournament edge. The target’s out-degree and all required two-edge witnesses therefore remain unchanged. Strict pairwise majorities follow from the normalization calculation.
The equivalence of winning seedings is proved. The upward induction has a valid leaf base case. At each internal node, identical child winners and identical match outcomes imply identical parent winners. It follows for every seeding that its winner agrees between the explicit tournament and the society.
The resulting equivalence, together with polynomial construction time and output length, establishes a polynomial many-one reduction. Its outputs always satisfy the promises.
The certificate is adequate. A leaf-order permutation determines the entire bracket and has length \(O(m\log m)\). Checking that every candidate appears exactly once and evaluating the bracket verifies a proposed winning seeding.
The exact arithmetic is correct. For
\[
D=\prod_i b_i,\qquad w_i=a_i(D/b_i),
\]
each division is exact. The bit length of \(D\) is bounded by the sum of denominator encoding lengths, hence by \(O(L)\). For a valid society, the weights are positive integers summing to \(D\).
The test
\[
2\sum_{i:x\succ_{R_i}y}w_i>D
\]
is exactly the required strict-majority test.
The arithmetic bounds are sufficient. Elementary multiplication and division on \(O(L)\)-bit integers support the claimed \(O(\tau L^2)\) bound for forming the denominator and weights. Summing weights for all pairs supports the stated \(O(\tau m^2L)\) bound after ranking positions are recorded.
Validity checks are polynomial. Ranking completeness and distinctness, mass positivity and normalization, the power-of-two size condition, absence of majority ties, target degree, and the king condition are all polynomial-time checkable. The stated \(O(m^2)\) tournament-table lookup bound for checking the king condition is valid.
Defining a language that rejects invalid inputs makes the completeness claim precise; the hardness reduction produces valid instances of that language.
No false steps, unjustified theorem applications, or substantive omissions were found. No repair or additional clarification is needed. The output establishes \(\mathrm{NP}\)-hardness for the supported rational-distribution formulation under exactly the requested promises, and also establishes membership in \(\mathrm{NP}\).
⟨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.