Answer: \(\mathrm{NP}\text{-complete}\)
Theorem 5.2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor $s = n/2$, TFP is NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m=2^r\) candidates, a rational distribution \(\mu\) over complete rankings, \(m/2\) designated seeds, and a target candidate \(c^\star\), define \(a\succ_\mu b\) when \(a\) has strict majority support over \(b\). Decide whether a valid seeded knockout bracket exists whose winner under \(\succ_\mu\) is \(c^\star\).
Let \(C\) contain \(m=2^r\) candidates, with integer \(r\ge 2\). A society is given by its support: a list of \(\tau\) distinct strict complete rankings of \(C\), each with a 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 input bit length.
Define \(a\succ_\mu b\) when the mass ranking \(a\) above \(b\) exceeds \(1/2\). Promise that no pair has mass exactly \(1/2\), so every match has a unique winner.
The input also specifies distinct candidates assigned seed numbers \(1,\ldots,m/2\), and a target \(c^\star\in C\), which may be seeded or unseeded.
A bracket assigns each candidate once to the leaves of a balanced binary knockout tree. It is valid if, for every \(k\in\{1,\ldots,r-1\}\), the top \(2^k\) seeds occupy different depth-\(k\) subtrees, with the root at depth \(0\). Validity concerns their initial positions, regardless of subsequent eliminations. Each match advances its winner under \(\succ_\mu\).
Is deciding whether a valid bracket makes \(c^\star\) win solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
With pairwise outcomes supplied as a tournament graph, this decision problem with \(m/2\) numbered seeds is NP-complete ([Manurangsi and Suksompong](https://arxiv.org/pdf/2204.11171)).
No result settling the exact rational-distribution input version was located in the literature search.
The decision problem is \(\mathrm{NP}\)-complete. The key is a polynomial-size realization of every tournament by a rational distribution over distinct rankings. The construction below uses dyadic masses, so it also covers the interpretation of “binary rational” as a finite binary fraction.
We use the stated theorem of Manurangsi and Suksompong: tournament fixing with \(m/2\) numbered seeds is \(\mathrm{NP}\)-complete. Their model uses \(m=2^r\) players and requires the top \(2^k\) seeds to be separated until the appropriate round. This is exactly separation into distinct depth-\(k\) subtrees in the initial bracket; their discussion also specifies that later elimination does not change these placement constraints. See [Section 2 and Theorem 5.2](https://arxiv.org/pdf/2204.11171).
Thus it suffices to transform an arbitrary tournament into a polynomial-size society inducing precisely its edges, while retaining the candidates, seed assignments, and target.
Lemma. Every tournament \(T\) on \(m\ge4\) candidates has a polynomial-time constructible society satisfying:
Proof. We first construct a multiset of rankings, then merge repeated rankings.
For every directed edge \(a\to b\) of \(T\), choose an ordering \(x_1,\ldots,x_{m-2}\) of the other candidates and add the following two rankings, written from most preferred to least preferred:
\[ \text{} \]
\(a>b>x_1>\cdots>x_{m-2}\),
\(x_{m-2}>\cdots>x_1>a>b\).
For two distinct candidates \(u,v\), define their count margin as the number of rankings placing \(u\) above \(v\), minus the number placing \(v\) above \(u\).
The displayed pair contributes \(2\) to the count margin of \(a\) over \(b\). It contributes zero to every other pair:
There are \(\binom m2\) edges, so the multiset contains \(N=2\binom m2=m(m-1)\) rankings. For each edge \(u\to v\), its count margin is exactly \(2\): its own gadget contributes \(2\), and all other gadgets contribute zero.
Let \(Q\) be the smallest power of two with \(Q\ge N\). Then \(N\le Q<2N\). Both \(N\) and \(Q\) are even. Add \((Q-N)/2\) copies of a neutral pair consisting of an arbitrary ranking and its reverse. Each neutral pair contributes zero to every count margin.
The resulting multiset therefore has exactly \(Q\) rankings and still has count margin \(2\) on every directed edge of \(T\).
For each distinct ranking \(\pi\) occurring in this multiset, let \(h_\pi\) be its positive multiplicity and assign mass \(\mu_\pi=h_\pi/Q\). These masses are positive, dyadic, and sum to \(1\). Merging identical rankings preserves every pairwise comparison mass.
For an edge \(u\to v\), write \(A_{uv}\) for the number of multiset rankings placing \(u\) above \(v\). Strict completeness gives \(A_{uv}+A_{vu}=Q\), while the construction gives \(A_{uv}-A_{vu}=2\). Consequently,
\(\mu(u\text{ above }v)=A_{uv}/Q=\frac12+\frac1Q>\frac12\).
The reverse comparison has mass \(\frac12-\frac1Q\). Thus the majority tournament is exactly \(T\), and every pair satisfies the no-tie promise.
Finally, there are at most \(Q<2m(m-1)\) distinct rankings. A ranking requires \(O(m\log m)\) bits under candidate labels of \(O(\log m)\) bits. Each numerator \(h_\pi\) and the denominator \(Q\) require \(O(\log m)\) bits. Hence the entire society has encoding length \(O(m^3\log m)\). Generating the rankings and grouping identical ones take polynomial time. This proves the lemma.
Take a tournament-graph instance \((T,\text{seed assignments},c^\star)\) from Section 1. Replace \(T\) by the society constructed in Section 2, copying the candidate set, every numbered seed assignment, and the target unchanged.
This is a polynomial-time transformation, and its output satisfies every input requirement.
For any leaf assignment:
Hence a valid bracket makes \(c^\star\) win in the tournament instance if and only if one does so in the society instance. This proves \(\mathrm{NP}\)-hardness.
A certificate lists the candidates assigned to the \(m\) leaf positions, requiring \(O(m\log m)\) bits.
A verifier checks that every candidate occurs exactly once. For each \(k\in\{1,\ldots,r-1\}\), it identifies the depth-\(k\) subtree containing each of the top \(2^k\) seeds and checks that these subtrees are distinct. These checks take polynomial time.
Pairwise majority outcomes can also be computed exactly in polynomial time. Write each input mass as \(p_i/q_i\), with the integers encoded in binary, and let \(B=\prod_{i=1}^{\tau}q_i\). The bit length of \(B\) is at most the sum of the denominator bit lengths, hence \(O(L)\). For candidates \(a,b\), compute the integer
\(S_{ab}=\sum_{i:\,a\text{ above }b\text{ in ranking }i}p_i(B/q_i)\).
Then \(a\succ_\mu b\) precisely when \(2S_{ab}>B\). All these computations use polynomially many operations on integers of polynomial bit length. The verifier then simulates the \(m-1\) bracket matches and checks that the root winner is \(c^\star\).
Thus the problem belongs to \(\mathrm{NP}\). Together with the reduction, this establishes \(\mathrm{NP}\)-completeness.
⟨structured verdict parsed — rendered above⟩
The argument is correct and resolves the task: the rational-distribution input problem is \(\mathrm{NP}\)-complete. No major or minor mathematical gaps were found.
The prover invokes a precise external result: tournament fixing with exactly \(m/2\) numbered seeds is \(\mathrm{NP}\)-complete.
This citation is accurate. Theorem 5.2 states hardness for \(s=n/2\), and Section 2 specifies balanced brackets with a power-of-two number of players, numbered seeds, and the hierarchical seed-separation constraints. Its discussion of seed transfer confirms that elimination does not remove the constraints arising from initial seed positions. These are the conventions used in the task. [Manurangsi and Suksompong, Section 2 and Theorem 5.2](https://arxiv.org/pdf/2204.11171)
The hypotheses match:
The external theorem is therefore used legitimately.
For an edge \(a\to b\), both displayed rankings put \(a\) above \(b\), giving count margin \(2\).
The cancellation claim covers every other unordered pair:
Each ranking contains every candidate exactly once and is strict and complete. Thus the gadget construction meets the ranking requirements.
There is one gadget for each of the \(\binom m2\) tournament edges. Consequently, the total number of rankings, counted with multiplicity, is
\(N=2\binom m2=m(m-1)\).
For any edge \(u\to v\), its own gadget contributes margin \(2\), while every other gadget contributes zero. The resulting margin is therefore exactly \(2\), as claimed.
For the smallest power of two \(Q\) satisfying \(Q\ge N\), the bounds \(N\le Q<2N\) hold, including when \(N\) itself is a power of two.
Since \(m\ge4\), both \(N\) and \(Q\) are even. Hence \((Q-N)/2\) is a nonnegative integer. Adding that many ranking–reverse pairs produces exactly \(Q\) rankings. Every such pair contributes zero margin to every candidate pair, so padding preserves all margins.
Merging repeated rankings also preserves comparison masses. Each retained ranking has positive multiplicity \(h_\pi\), and its assigned mass \(h_\pi/Q\) is positive and dyadic. The masses sum to \(1\), and the resulting support consists of distinct rankings.
The majority calculation is correct. For an edge \(u\to v\), the two equations
\(A_{uv}+A_{vu}=Q\) and \(A_{uv}-A_{vu}=2\) imply
\(A_{uv}/Q=1/2+1/Q\).
The reverse comparison has mass \(1/2-1/Q\). Thus every tournament edge is realized in the intended direction, and no pair ties.
The support size is at most \(Q<2m(m-1)\), so it is \(O(m^2)\).
With candidates represented by indices, each ranking takes \(O(m\log m)\) bits. Since \(1\le h_\pi\le Q=O(m^2)\), each mass requires \(O(\log m)\) bits using a binary numerator and denominator. Explicit finite binary fractions satisfy the same bound.
The resulting society therefore has encoding length \(O(m^3\log m)\). Generating \(O(m^2)\) rankings of length \(m\), padding them, and grouping identical rankings are polynomial-time operations. The stated bounds are sound.
The reduction retains the candidate set, numbered seeds, and target.
Bracket validity is unchanged because it depends only on seed positions. Every match outcome is unchanged because the constructed society induces exactly the source tournament.
The stated induction over the tree is valid: corresponding leaves contain the same candidates, and identical winners at the two child nodes yield the same winner at their parent. Consequently, corresponding brackets have the same root winner.
This establishes both directions of the claimed equivalence and proves \(\mathrm{NP}\)-hardness.
The certificate is a permutation of candidates over the leaf positions, with polynomial length. Checking candidate uniqueness and every required seed-separation condition takes polynomial time.
The exact-arithmetic argument is also valid. For positive denominators \(q_i\), the product \(B=\prod_i q_i\) has bit length \(O(L)\), and each division \(B/q_i\) is exact. The sums \(S_{ab}\) have polynomial bit length: their terms have polynomial bit length, and summing \(\tau\) terms adds at most \(O(\log\tau)\) bits.
The comparison \(2S_{ab}>B\) exactly implements the required strict majority test. Computing the needed outcomes and simulating the \(m-1\) matches therefore takes polynomial time.
No additional mathematical clarification or repair is required. The stray empty display in Section 2 can be deleted as a formatting cleanup; it does not affect verification.
⟨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.