Answer: Computing \(\operatorname{TEQ}(T_\mu)\) on the promised inputs is polynomial-time solvable in \(m,\tau,L\).
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateSchwartz’s Conjecture holds for all tournaments whose triangle packing number and triangle covering num- ber are equal. Moreover, τ can be calculated in polynomial time for these tournaments. A proper subclass of the tournaments who have equal num- ber of triangle packing and triangle covering are the ones where triangles are pairwise vertex-disjoint. In this case, each triangle is a homogenous set and the tournaments are transi- tive over the triangles.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given (m) alternatives and a finite support \{(\pi_i,\mu_i)\}_{i=1}^{\tau} of complete rankings with positive binary-rational masses summing to 1, suppose every pair has a strict weighted majority comparison and the resulting tournament T_\mu has equal triangle packing and covering numbers. Compute \operatorname{TEQ}(T_\mu).
Let \(m\geq 1\). A society is given by its support: \(\tau\) distinct strict complete rankings \(\pi_i\) of the alternatives, each with positive binary-rational mass \(\mu_i\), where \(\sum_i\mu_i=1\). Here \(\tau\) is the support size, not the number of possible rankings; \(L\) is the total input bit length.
Define \(T_\mu\) by \(a\to b\) exactly when \(\sum_{i:a\succ_{\pi_i}b}\mu_i>1/2\). Every pair is promised to have a strict majority comparison.
A triangle is a directed cycle on three vertices. The triangle packing number is the maximum number of vertex-disjoint triangles; the triangle covering number is the minimum number of vertices meeting every triangle. These two integer numbers are promised equal for \(T_\mu\).
For any nonempty tournament \(T\), put \(N_T^-(v)=\{u:u\to v\}\). A nonempty set \(A\subseteq V(T)\) is \(\operatorname{TEQ}\)-retentive if \(\operatorname{TEQ}(T[N_T^-(v)])\subseteq A\) for every \(v\in A\) with \(N_T^-(v)\neq\varnothing\). Recursively, \(\operatorname{TEQ}(T)\) is the union of all inclusion-minimal retentive sets; for a singleton tournament it is that singleton.
Is computing \(\operatorname{TEQ}(T_\mu)\) on these promised inputs solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For explicitly given tournaments with equal triangle packing and covering numbers, \(\operatorname{TEQ}\) is computable in polynomial time and the minimal retentive set is unique ([Mnich, Shrestha and Yang, 2015](https://www.ijcai.org/Proceedings/15/Papers/091.pdf)). No separate result for this exact rational-mass input problem was identified in the search.
Computing \(\operatorname{TEQ}(T_\mu)\) on the promised inputs is polynomial-time solvable in \(m,\tau,L\). The support representation allows the entire majority tournament to be constructed using polynomially many exact integer operations. The stated theorem for explicit tournaments then applies.
Let \(V\) be the set of \(m\) alternatives. Write each input mass as \(\mu_i=p_i/q_i\), where \(p_i,q_i\) are positive integers encoded in binary. This also covers dyadic rationals under the usual explicit binary encoding.
Define
\[
D=\prod_{i=1}^{\tau}q_i,
\qquad
w_i=p_i(D/q_i).
\]
Each \(w_i\) is an integer, and \(\mu_i=w_i/D\). The normalization premise gives
\[
\sum_{i=1}^{\tau}w_i=D.
\]
The bit length of \(D\) is at most \(1+\sum_i\operatorname{bitlength}(q_i)\), hence is \(O(L)\). Moreover, positivity and normalization imply \(w_i\leq D\), so every \(w_i\) also has \(O(L)\) bits. Products, exact divisions, and multiplications needed to construct these integers therefore take polynomial time in \(\tau,L\).
For each ranking, construct a table \(\operatorname{pos}_i(a)\) giving the position of alternative \(a\). For every unordered pair \(\{a,b\}\), compute the integer
\[
S_{ab}=\sum_{\substack{1\leq i\leq\tau\\
\operatorname{pos}_i(a)<\operatorname{pos}_i(b)}}w_i.
\]
Then, exactly,
\[
a\to b
\quad\Longleftrightarrow\quad
\sum_{i:a\succ_{\pi_i}b}\mu_i>\frac12
\quad\Longleftrightarrow\quad
2S_{ab}>D.
\]
All partial sums are at most \(D\), so these calculations use integers of \(O(L)\) bits. There are \(\binom m2\) pairs, each requiring at most \(\tau\) additions. Thus constructing all majority comparisons takes polynomial time in \(m,\tau,L\).
Because every ranking is strict and complete, the total mass preferring \(b\) to \(a\) is \(1-S_{ab}/D\). The strict-majority promise excludes \(2S_{ab}=D\), so exactly one orientation is assigned to each pair. The resulting adjacency matrix is precisely \(T_\mu\), with \(O(m^2)\) entries.
Theorem 1 of [Mnich, Shrestha and Yang (2015)](https://www.ijcai.org/Proceedings/15/Papers/091.pdf) states that, for tournaments whose triangle packing and triangle covering numbers are equal, the minimal retentive set is unique and the tournament equilibrium set is computable in polynomial time.
Its hypotheses hold here:
Consequently, running that algorithm on the constructed adjacency matrix returns exactly \(\operatorname{TEQ}(T_\mu)\). For \(m=1\), one may simply return the unique alternative.
The first stage takes polynomial time in \(m,\tau,L\) and produces an explicit tournament of size \(O(m^2)\). The second stage takes polynomial time in that explicit size. Their composition is therefore polynomial-time.
No recognition algorithm for the packing–covering equality is needed: it is a promise. Nor is it necessary to enumerate rankings outside the given support or expand rational masses into individual voters. A separate theorem for the rational-mass representation is unnecessary because the polynomial-time construction transfers the explicit-tournament result.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument establishes polynomial-time computation on the promised inputs. No mathematical errors, missing hypotheses, or substantive gaps were found.
Writing each mass as \(\mu_i=p_i/q_i\), with positive binary-encoded integers, is consistent with the task’s explicit rational representation. The argument also covers explicitly encoded dyadic rationals.
The product \(D=\prod_{i=1}^{\tau}q_i\) is positive, and each \(q_i\) divides it. Thus \(w_i=p_i(D/q_i)\) is an integer and satisfies \(\mu_i=w_i/D\). Multiplying the promised normalization by \(D\) gives exactly \(\sum_i w_i=D\). These steps are valid without requiring the fractions to be reduced.
The stated bound on the bit length of \(D\) is valid: the bit length of a product is bounded by the sum of the factors’ bit lengths, up to the stated harmless additive constant. Since denominator encodings are part of the input, this is \(O(L)\).
Positivity and \(\sum_iw_i=D\) imply \(0<w_i\leq D\), including when \(\tau=1\). Consequently, each weight has \(O(L)\) bits. Intermediate denominator products and the quotients \(D/q_i\) also have \(O(L)\) bits; input numerators have at most \(L\) bits. Standard binary integer multiplication and division therefore justify the polynomial-time arithmetic claim. The proof does not confuse a polynomial number of operations with polynomial bit complexity.
Strict complete rankings permit the position tables used in the proof. For a chosen ordering of each unordered pair, the sum \(S_{ab}\) includes exactly the masses of rankings preferring \(a\) to \(b\), after scaling by \(D\). Hence
\[
a\to b
\quad\Longleftrightarrow\quad
\frac{S_{ab}}{D}>\frac12
\quad\Longleftrightarrow\quad
2S_{ab}>D.
\]
The equivalence is correct because \(D>0\).
Every summand is positive, so every partial sum is at most \(D\). Doubling the sum increases its bit length by at most one. Thus the comparisons remain polynomial-time exact computations.
There are \(\binom m2\) unordered pairs, each requiring at most \(\tau\) weight additions. Constructing the position tables also takes polynomial time. The total construction cost is therefore polynomial in \(m,\tau,L\).
Completeness and strictness of each ranking imply that the opposite preference has total mass \(1-S_{ab}/D\). The strict-majority promise excludes equality with one half, so exactly one direction is selected for every pair. The constructed adjacency matrix consequently represents precisely \(T_\mu\). Its \(O(m^2)\) size is polynomial in the requested parameters.
The cited result is accurately stated. Theorem 1 establishes uniqueness of the minimal retentive set and polynomial-time computation of the tournament equilibrium set for tournaments with equal triangle packing and covering numbers. The paper’s definitions of triangles, packing, covering, and recursive retentiveness agree with those in the task. [Mnich, Shrestha and Yang (2015), Theorem 1 and Section 2](https://www.ijcai.org/Proceedings/15/Papers/091.pdf).
All necessary hypotheses are supplied: the constructed object is an explicit nonempty tournament, and equality of the two triangle numbers is promised. The theorem requires no additional condition on the rankings or rational masses. Its application is fully justified.
Applying the cited polynomial-time algorithm to an adjacency matrix of polynomial size gives a polynomial-time composed algorithm. A recognition procedure or certificate for the promised equality is unnecessary.
The singleton case is explicitly handled correctly. Other small tournaments fall within the stated theorem. Distinctness of support rankings imposes no additional obligation on the construction. No enumeration of absent rankings or expansion into individual voters is needed.
No additional clarification or repair is required.
⟨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.