Answer: \(\mathrm{P}\): the continuous decision problem is exactly rational linear-program feasibility with polynomial encoding length.
Theorem 10 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateTOURNAMENT VALUE MAXIMIZATION is solvable in linear time if the game-value function is player popularity-based and there are only two different player popularity values.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given ordered finite strength tiers \(T\), rational masses \(\mu_t\) summing to one, bracket height \(h\), two popularity values \(q_t\) in \(\{a,b\}\), and target \(B\), let \(N=2^h\) and use normalized mass-flow variables \(y_{t,r}\) and \(a_{i,r}\) for type mass assigned to \(r\)-round subtournaments and open-subtournament counts divided by \(N\). Require \(a_{0,h}=1/N\), \(a_{0,r}=0\) for \(r<h\), \(\sum_r y_{t,r}=\mu_t\), \(a_{i,r}=a_{i-1,r}-y_{i,r}+\sum_{s>r}y_{i,s}\), \(0\le y_{i,r}\le a_{i-1,r}\), and \(a_{\tau,r}=0\). Decide whether there is a feasible trajectory with \(\sum_{t,r} r q_t y_{t,r}\) at least \(B\).
A society is given by its support: a list of \(\tau\) strength types \(T=(1,\ldots,\tau)\), ordered strictly from strongest to weakest, with positive binary-rational masses \(\mu_i\) summing to \(1\). Here \(m=|T|=\tau\) is the support size, not the number of possible types.
Each type has popularity \(q_i\in\{a,b\}\), where \(a>b\geq0\) are binary-encoded integers and both values occur. A match contributes its winner's popularity. The input also contains a unary-encoded height \(h\geq1\) and binary-rational threshold \(B\); set \(N=2^h\). Let \(L\) be the total input bit length.
For \(0\leq r\leq h\), an open subtournament has \(2^r\) positions; assigning its winner closes it and opens one subtournament of each height \(0,\ldots,r-1\). Height \(0\) means a single position and contributes no wins.
A continuous trajectory consists of nonnegative real variables \(y_{i,r}\), the mass of type \(i\) assigned as winners of height-\(r\) subtournaments, and \(a_{i,r}\), the open-subtournament counts divided by \(N\) after processing types \(1,\ldots,i\).
Require \(a_{0,h}=1/N\), \(a_{0,r}=0\) for \(r<h\), and \(\sum_{r=0}^{h}y_{i,r}=\mu_i\) for every \(1\leq i\leq\tau\).
For every \(1\leq i\leq\tau\) and \(0\leq r\leq h\), require \(0\leq y_{i,r}\leq a_{i-1,r}\), \(a_{i,r}=a_{i-1,r}-y_{i,r}+\sum_{s=r+1}^{h}y_{i,s}\), and \(a_{\tau,r}=0\). Newly opened subtournaments become available only to later types.
The decision problem asks whether such a trajectory exists with normalized value \(\sum_{i=1}^{\tau}\sum_{r=0}^{h}r q_i y_{i,r}\geq B\).
Is this continuous decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? State running times in \(m,\tau,h,L\).
For explicitly listed discrete players with a strict strength order and two winner-popularity values, tournament value maximization has a linear-time algorithm. [Source](https://arxiv.org/html/2309.09967v2#S4.SS3)
No result settling this exact continuous trajectory problem was located in the literature search.
The stated continuous decision problem is in \(\mathrm{P}\). It is exactly feasibility of a rational linear program of polynomial encoding length. This settles the specified trajectory model, including the restriction that newly opened subtournaments are available only to later types.
Write \(H=h+1\). Use the \(2\tau H\) real variables \(y_{i,r}\) and \(a_{i,r}\), for \(1\leq i\leq\tau\) and \(0\leq r\leq h\). Treat \(a_{0,r}\) as the specified constants.
Impose the following constraints:
Every expression is affine in the variables; the popularities, masses, and threshold are input constants.
Equivalence. A trajectory answering the original question positively satisfies every constraint above. Conversely, a feasible point supplies nonnegative trajectory variables satisfying every defining condition and the required value threshold. In particular, availability uses \(a_{i-1,r}\), so openings produced while processing type \(i\) cannot be used by that same type.
Thus the reduction is exact. It introduces neither an integrality condition nor a relaxation of the stated model.
Let \(d=2\tau H\) be the number of variables. There are:
Replacing each equality by two inequalities yields \(p=5\tau H+2\tau+2H+1\) inequalities. Hence \(d,p=O(\tau H)\).
All matrix coefficients outside the threshold row belong to \(\{-1,0,1\}\). A threshold coefficient \(r q_i\) has bit length \(O(L+\log H)\), because \(r\leq h\) and \(q_i\) is a binary-encoded input integer.
The initial constant \(1/N=2^{-h}\) has an ordinary numerator–denominator encoding of length \(O(h)\): its denominator is a binary one followed by \(h\) zeros. Consequently, the magnitude of \(N\) does not force an exponentially long formulation.
Set \(D=\tau(h+1)\). A dense encoding of the inequality system has total bit length bounded by
\(S=O\!\left(D^2+D(L+\log(h+1))+L+h\right).\)
Since the height is unary encoded, \(h\leq L\). Therefore this simplifies to
\(S=O(D^2+DL).\)
The formulation can be constructed in polynomial time in this bound.
Use the standard rational linear-programming theorem: feasibility of an explicitly encoded system of rational linear equalities and non-strict inequalities is decidable in time polynomial in its total binary encoding length. This theorem applies to arbitrary rational polyhedra, including those of lower dimension; it does not require a strictly feasible point. See [MIT’s ellipsoid-method lecture, Section 3.12](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf).
All its hypotheses hold here: the formulation is explicit, all coefficients are rational, and its encoding length is polynomial in the original input length. Applying that theorem gives a deterministic bit running time of
\(\left((\tau(h+1))^2+\tau(h+1)L\right)^{O(1)}.\)
Because \(m=\tau\), this is also
\(\left((m(h+1))^2+m(h+1)L\right)^{O(1)}=\operatorname{poly}(m,h,L).\)
Finally, explicit support listing implies \(\tau\leq L\), and unary height implies \(h\leq L\). The running time is therefore \(L^{O(1)}\), proving membership in \(\mathrm{P}\).
The threshold is included directly as a non-strict inequality. Accordingly, the algorithm decides exact feasibility even when the optimum equals \(B\); no numerical tolerance or approximation assumption is needed.
This proof does not require the discrete-player algorithm or the restriction to two popularity values. It also establishes polynomial-time solvability of the same trajectory problem with arbitrary explicitly listed binary-rational popularities.
The established running time is polynomial in numerical encoding length; no strongly polynomial or linear-time claim is made. Under polynomial-time many-one reductions, NP-hardness of this problem would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output correctly establishes that the specified continuous decision problem belongs to \(\mathrm{P}\). The linear formulation is exact, its encoding length is polynomial, and the stated rational linear-programming theorem applies. No mathematical gaps or false claims were found.
The proposed variables are precisely the trajectory variables required by the task. Treating \(a_{0,r}\) as constants correctly incorporates the initial state without introducing additional variables.
Every defining condition is included:
Both directions of the claimed equivalence follow directly from these identical conditions. In particular, the use of the preceding state \(a_{i-1,r}\) correctly prevents openings created by type \(i\) from becoming available to that same type.
The boundary heights are also handled correctly. At \(r=h\), the update sum is empty. At \(r=0\), the objective coefficient is zero, as required for a position contributing no wins.
There is no omitted integrality requirement: the task explicitly permits nonnegative real variables.
With \(H=h+1\), the variable count \(d=2\tau H\) is correct.
Before converting equalities, there are \(3\tau H+1\) inequalities and \(\tau+\tau H+H\) equalities. Replacing every equality with two inequalities therefore gives exactly
\[ p=5\tau H+2\tau+2H+1. \]
Thus \(d,p=O(\tau H)\), as claimed.
The coefficient claims are correct. Outside the threshold row, variable coefficients belong to \(\{-1,0,1\}\). The potentially nonintegral initial state appears in the right-hand side, so it does not contradict that statement.
For the threshold row, multiplying an input popularity by an integer \(r\leq h\) requires \(O(L+\log H)\) bits. This also accommodates zero coefficients.
The denominator of \(2^{-h}\) has \(h+1\) binary digits. Consequently, representing the initial state requires \(O(h)\) bits, despite the exponential numerical value of \(N\).
With \(D=\tau(h+1)\), the dense encoding bound
\[ S=O\!\left(D^2+D(L+\log(h+1))+L+h\right) \]
is valid. It accounts for the dense matrix, threshold coefficients, input right-hand sides, and initial constant. Repeated occurrences of the initial constant are absorbed by the stated bound.
Because \(h\) is unary encoded, \(h\leq L\). Since \(D\geq1\), the simplification \(S=O(D^2+DL)\) is justified. Constructing this explicit system takes polynomial time in the stated bound.
The invoked theorem is correctly stated: feasibility of an explicitly encoded rational linear system is decidable deterministically in polynomial bit time, including systems whose feasible sets have lower dimension.
All relevant hypotheses hold here. The system is finite and explicit, all its data are rational, and its total encoding length is polynomial.
The cited lecture’s Section 3.12 establishes polynomial-time feasibility for integer data and explicitly discusses arbitrary polyhedra and polynomial precision. The prover invokes the standard rational-data version of this theorem; this is a valid application. [MIT ellipsoid-method lecture](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf)
Neither strict feasibility nor a numerical tolerance is required. Including the threshold directly as a non-strict inequality correctly handles equality with \(B\).
The stated running time
\[ \left((\tau(h+1))^2+\tau(h+1)L\right)^{O(1)} \]
follows from the encoding bound and the feasibility theorem. Substituting \(m=\tau\) gives the requested dependence on support size. Explicit listing implies \(\tau\leq L\), and unary height implies \(h\leq L\), so the bound is polynomial in \(L\).
The extension to explicitly listed binary-rational popularities is also justified: the formulation remains rational and polynomial in encoding length.
The final conditional statement about NP-hardness is correct under polynomial-time many-one reductions. The proof establishes membership in \(\mathrm{P}\); it does not claim an unconditional separation from NP-hardness.
Actionable feedback: none 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.