Answer: \(\mathrm{NP}\)-complete
Theorem 4.3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAssume that a tournament $T$ is generated according to the generalized random model, and that $ p_{i,j} \in \left[100\log n/n, 1 - 100\log n/n\right] $ for all $i\neq j$. Then with high probability, all alternatives in $T$ are single-elimination winners, and a winning bracket of each alternative can be computed in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a candidate set \(C\) with \(|C|=2^r\), a support \(T\) of \(\tau\) complete rankings with positive rational masses \(\mu_t\) summing to \(1\), and a target \(c^\star\), define \(a\succ_\mu b\) when \(\sum_{t:\,a\succ_t b}\mu_t>1/2\), restricting inputs to those with no tied pair. Is there a balanced binary bracket using each candidate once whose champion under \(\succ_\mu\) is \(c^\star\); if so, find one, with complexity measured in \(|C|\), \(\tau\), and mass bit length \(L\)?
Let \(C\) be a candidate set with \(m=|C|=2^r\), where \(r\geq1\) is an integer, and let \(c^\star\in C\).
A society is given by its support: a list \(T\) of \(\tau\) distinct strict complete rankings, each with positive binary rational mass \(\mu_t\), with \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number \(m!\) of possible rankings; let \(L\) be the total bit length of the masses.
For distinct candidates, define \(a\succ_\mu b\) precisely when \(\sum_{t\in T:\,a\succ_t b}\mu_t>1/2\); require that this sum never equals \(1/2\).
A bracket assigns every candidate exactly once to the leaves of a perfect binary tree of depth \(r\). Each internal node advances the winner under \(\succ_\mu\) of its two child winners; the root winner is the champion.
The computational problem is to decide whether some bracket has champion \(c^\star\), and, if so, find one. Measure running times in \(m,\tau,L\).
Is this decision problem in \(\mathrm{P}\), with a winning bracket computable in polynomial time, or is it \(\mathrm{NP}\)-hard?
For independently oriented tournament edges with probabilities in \([100\ln m/m,1-100\ln m/m]\), with probability tending to one every candidate has a winning bracket computable in polynomial time. [Manurangsi–Suksompong](https://link.springer.com/article/10.1007/s10458-022-09557-7)
For arbitrary explicitly supplied deterministic pairwise outcomes, balanced bracket selection is \(\mathrm{NP}\)-complete. [Aziz et al.](https://www.cse.unsw.edu.au/~tw/agmmswaij2018.pdf)
No result for exactly the rational-mass support representation above was verified.
The decision problem is \(\mathrm{NP}\)-complete. Hardness holds even when all masses are dyadic rationals, the support size is \(\tau=O(m^2)\), and the total mass encoding length is \(L=O(m^2\log m)\).
Consequently, deciding existence and constructing a winning bracket in time polynomial in \(m,\tau,L\) is possible if and only if \(\mathrm{P}=\mathrm{NP}\).
A tournament on \(C\) specifies exactly one directed edge \(a\to b\) or \(b\to a\) for each pair of distinct candidates; the edge points from winner to loser.
Aziz et al., Theorem 1, prove that the following problem is \(\mathrm{NP}\)-complete: given an explicitly represented tournament and a distinguished candidate, decide whether some balanced knockout bracket makes that candidate win. Their setting uses a power-of-two number of candidates, a balanced binary tree with each candidate appearing once at a leaf, and deterministic outcomes with every match allowed. Their hardness reduction itself produces a power-of-two number of candidates. Thus its bracket model coincides with the one in the question. [Aziz et al., *Fixing balanced knockout and double elimination tournaments*, pp. 1–3](https://www.cse.unsw.edu.au/~tw/agmmswaij2018.pdf).
It remains to prove that every such tournament has a polynomial-size realization by a support satisfying all the requirements in the question.
Lemma. Let \(G\) be any tournament on \(m\geq 2\) candidates. In polynomial time one can construct distinct strict complete rankings with positive dyadic masses summing to one whose strict majority tournament is exactly \(G\). The construction satisfies \(\tau=O(m^2)\) and \(L=O(m^2\log m)\).
Proof. We first construct a multiset of rankings and then merge identical rankings.
For each edge \(a\to b\) of \(G\), list the remaining candidates in an arbitrary fixed order \(x_1,\ldots,x_{m-2}\). Insert these two rankings:
\(R^1_{ab}: \quad a\succ b\succ x_1\succ\cdots\succ x_{m-2},\)
\(R^2_{ab}: \quad x_{m-2}\succ\cdots\succ x_1\succ a\succ b.\)
When \(m=2\), the remaining list is empty, and both rankings put \(a\) above \(b\).
Define the unnormalized margin of \(u\) over \(v\) to be the number of rankings putting \(u\) above \(v\), minus the number putting \(v\) above \(u\).
The two rankings for \(a\to b\) contribute margin \(2\) to \(a\) over \(b\). Their contribution to every other unordered pair is zero, as follows:
These cases cover every pair other than \(\{a,b\}\). Consequently, after adding the gadget for every edge, each edge \(a\to b\) of \(G\) has margin exactly \(2\).
There are \(\binom m2\) gadgets and hence
\(N=2\binom m2=m(m-1)\)
ranking occurrences. In particular, \(N\) is positive and even.
To obtain dyadic masses, let \(P\) be the smallest power of two with \(P\geq N\). Then \(N\leq P<2N\), and \(P-N\) is even. Choose any strict complete ranking \(R\) and add \((P-N)/2\) copies of the pair consisting of \(R\) and its complete reverse. Each such pair contributes zero margin to every candidate pair.
The resulting multiset has exactly \(P\) ranking occurrences and still gives margin \(2\) to every edge of \(G\). Give each occurrence mass \(1/P\). For every edge \(a\to b\), let \(A\) be the number of occurrences putting \(a\) above \(b\), and \(B\) the number putting \(b\) above \(a\). Completeness of the rankings and the margin calculation give
\(A+B=P,\qquad A-B=2.\)
Therefore,
\(\displaystyle \sum_{t:\,a\succ_t b}\mu_t=\frac{A}{P}=\frac12+\frac1P>\frac12.\)
The reverse direction has mass \(\frac12-\frac1P\), so no pair is tied.
Finally, for each distinct ranking \(t\), let \(k_t\) be its multiplicity and output the single support entry with mass
\(\displaystyle \mu_t=\frac{k_t}{P}.\)
Every output mass is positive and dyadic, and their sum is \(\sum_t k_t/P=1\). Merging preserves every pairwise mass sum.
There are at most \(N\) distinct rankings from the edge gadgets, and padding introduces at most two additional ranking types. Thus
\(\tau\leq N+2=O(m^2).\)
Since \(1\leq k_t\leq P<2m(m-1)\), each mass requires \(O(\log m)\) bits, giving \(L=O(m^2\log m)\). The raw list contains \(O(m^2)\) rankings of length \(m\); constructing and sorting that list to merge duplicates takes polynomial time. This proves the lemma. ∎
Take an instance \((G,c^\star)\) of the deterministic problem from Section 1, with \(m=2^r\), and apply the lemma. Keep the candidate set and distinguished candidate unchanged.
The resulting society satisfies
\(a\succ_\mu b\quad\Longleftrightarrow\quad a\to b\text{ in }G.\)
Consider any assignment of candidates to the leaves of the perfect binary tree. Its winner is identical under \(G\) and under the constructed society. Indeed, the leaf labels agree; inductively, if the winners at both children agree, the winner at their parent agrees because the pairwise outcomes agree. Applying this induction through the root proves the assertion.
Therefore,
\(\displaystyle c^\star\text{ has a winning bracket in }G \quad\Longleftrightarrow\quad c^\star\text{ has a winning bracket in the constructed society}.\)
The construction is polynomial, preserves the power-of-two candidate count, and produces only valid instances. It is therefore a polynomial many-one reduction proving \(\mathrm{NP}\)-hardness.
A certificate is a permutation of the candidates, specifying their order at the leaves. Its length is \(O(m\log m)\).
To verify it, first compute the majority tournament exactly. Write each input mass as \(\mu_t=p_t/q_t\), with positive integers \(p_t,q_t\), and set
\(\displaystyle D=\prod_{t\in T}q_t,\qquad w_t=p_t(D/q_t).\)
The binary length of \(D\) is \(O(L)\). All these integers can be computed in polynomial time. For any distinct \(a,b\),
\(\displaystyle a\succ_\mu b \quad\Longleftrightarrow\quad 2\sum_{t:\,a\succ_t b}w_t>D.\)
After recording candidate positions in each ranking, all pairwise comparisons require \(O(\tau m^2)\) additions and comparisons of integers with polynomially bounded bit length. Thus this computation is polynomial in \(m,\tau,L\), without numerical approximation.
Check that the certificate lists each candidate exactly once, and then evaluate its \(m-1\) internal matches. Accept precisely when the root winner is \(c^\star\). This is a polynomial-time verifier.
If invalid encodings are to be rejected rather than excluded by promise, validity is also polynomial-time checkable: verify the rankings, distinct support entries, positive masses, normalization, the power-of-two candidate count, and absence of pairwise ties.
Together with Section 3, this proves \(\mathrm{NP}\)-completeness.
If \(\mathrm{P}=\mathrm{NP}\), a winning bracket can also be constructed in polynomial time. Consider the auxiliary question whether a specified prefix of the leaf permutation extends to a winning bracket. This question belongs to \(\mathrm{NP}\): a completion is a certificate checked by the verifier above.
Under \(\mathrm{P}=\mathrm{NP}\), test candidate extensions one leaf at a time. Whenever the current prefix has a winning completion, at least one unused candidate preserves that property. At most \(m^2\) extension tests produce a complete winning bracket. Conversely, a polynomial-time algorithm that decides existence and returns a bracket would solve the \(\mathrm{NP}\)-complete decision problem.
The stated random-tournament guarantee is compatible with this conclusion: it concerns typical instances under a particular distribution, whereas the reduction establishes worst-case hardness. The support representation permits every deterministic tournament with polynomial encoding size.
⟨structured verdict parsed — rendered above⟩
The output proves the requested problem is \(\mathrm{NP}\)-complete, including under its stated restrictions on support size and dyadic mass encoding. The reduction, exact arithmetic, and search consequence are correct. No major or minor mathematical issues were found.
The application of Aziz et al., Theorem 1, is valid.
The [cited paper](https://www.cse.unsw.edu.au/~tw/agmmswaij2018.pdf) defines its problem using a power-of-two player count, a balanced binary tree, deterministic pairwise outcomes, and unrestricted matches. It explicitly identifies existence of a winning draw with existence of a winning leaf seeding. Theorem 1 establishes NP-completeness, and its reduction chooses a power-of-two player count.
Thus the source problem has the same bracket structure as the target problem. Passing between a deterministic pairwise comparison matrix and an explicitly oriented tournament preserves the input size polynomially.
Finding: The theorem is stated sufficiently precisely, and its hypotheses match the proposed reduction. There is no missing restriction involving byes, forbidden matches, or an unbalanced tree.
For the gadget associated with \(a\to b\), both rankings place \(a\) above \(b\), so its contribution to that directed margin is exactly \(2\).
The cancellation claims exhaust the other possibilities:
Hence each gadget has zero margin on every other unordered pair. Summing the gadgets therefore gives margin exactly \(2\) in the specified direction for every tournament edge.
Finding: The computation and its quantifiers are correct. No interactions between different gadgets invalidate the margin calculation.
The occurrence count is
\[
N=2\binom m2=m(m-1).
\]
For every \(m\geq2\), this is positive and even.
The smallest power of two \(P\geq N\) satisfies \(N\leq P<2N\). Since \(P\geq2\), both \(P\) and \(N\) are even, so the specified padding count is a nonnegative integer.
A ranking and its complete reverse have zero combined margin on every pair. Consequently, padding changes the total occurrence count to \(P\) while preserving all margins.
For an edge \(a\to b\), the equations \(A+B=P\) and \(A-B=2\) give precisely
\[
\frac AP=\frac12+\frac1P.
\]
The opposite direction consequently has mass \(\frac12-\frac1P\). These values lie within the permissible probability range, and neither equals \(\frac12\).
The smallest case also works: when \(m=2\), \(N=P=2\), the two gadget rankings coincide, no padding is required, and merging produces one ranking of mass \(1\).
Finding: The padding, constants, strict inequalities, and boundary case are correct.
Merging occurrences by identical complete rankings preserves every pairwise mass sum. Every resulting mass is positive, is dyadic, and the masses sum to \(1\).
There are at most \(N\) gadget ranking types and at most two additional padding types. Thus the claimed bound \(\tau\leq N+2\) holds, including when some types coincide.
Both \(k_t\) and \(P\) have binary length \(O(\log m)\). Therefore each mass has an encoding of that size, and the claimed total mass length \(L=O(m^2\log m)\) follows. Reducing the fractions, if required by the encoding convention, preserves these bounds.
The rankings themselves also have polynomial total encoding size: there are \(O(m^2)\) occurrences, each containing \(m\) candidate labels. Constructing and merging this list is polynomial.
Finding: All support requirements and polynomial size claims are established.
The constructed majority relation agrees with the source tournament on every distinct candidate pair.
The induction through the bracket is valid: corresponding child winners agree, and the agreed pairwise relation then determines the same parent winner. Because leaf assignments use every candidate exactly once, the child winners represent distinct candidates whenever they meet.
The construction preserves the candidate set, distinguished candidate, and power-of-two count. The equivalence of winning-bracket existence therefore holds in both directions.
Finding: This is a valid polynomial many-one reduction and establishes NP-hardness for valid target instances.
A leaf permutation is a polynomial-length certificate, and checking that it is a permutation is polynomial.
For binary rational masses, the product denominator \(D\) has bit length \(O(L)\). The divisions \(D/q_t\) are exact, and the resulting integer weights and sums have polynomially bounded bit lengths. The comparison
\[
2\sum_{t:\,a\succ_t b}w_t>D
\]
is exactly the required strict majority test.
Recording positions in each ranking makes the stated polynomial number of pairwise arithmetic operations sufficient. Evaluating the bracket then requires \(m-1\) matches.
The listed validity checks are also polynomial, so the proof works whether malformed encodings are excluded or rejected.
Finding: Membership in NP is proved using exact arithmetic; the argument does not depend on numerical approximation.
The prefix-extension question belongs to NP because a full winning permutation certifies a positive answer. Under \(\mathrm{P}=\mathrm{NP}\), polynomially many such decision queries construct a winning bracket on a positive instance. An initial existence test handles negative instances.
Conversely, the proposed combined polynomial decision and construction algorithm would decide the NP-complete problem. Thus the stated equivalence with \(\mathrm{P}=\mathrm{NP}\) is justified.
The final observation correctly distinguishes a distributional guarantee from worst-case hardness. It supplies context rather than an additional premise needed by the reduction.
None. The submitted proof resolves the assigned problem as written.
⟨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.