| paper | d4-conf-aaai-2026-4206 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: \(\mathsf{P}\), with bit running time \((L+Nm\tau)^{O(1)}=(L+N\tau^2)^{O(1)}\), uniformly in \(\lambda\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a balanced bracket with \(N=2^h\) leaves, a finite set of entrant types with a complete deterministic match-outcome relation, rational masses \(\mu_t\) summing to \(1\), and a target type \(f\) with \(\mu_f\ge 1/N\), decide whether the masses can be assigned to leaf slots of size \(1/N\) and paired at each match so that the entire root mass has type \(f\). Parameterize by \(\lambda=|\{t\ne f:\ f\text{ beats }t\}|\), the number of supported opponent types the target type beats.
A nonatomic population distributed over entrant types; assign type mass to bracket slots and choose a coupling of the two child distributions at each match. Each paired mass advances as the winner’s type, and the feasibility condition is that the root distribution is entirely \(f\).
This mirror covers the out-degree lower-bound question in Theorem 2; it does not address Theorems 1 or 3.
The strongest mirror I would defend is a continuous type tournament fixing problem for large competitions with many interchangeable entrants. For example, an arena might contain many bots generated from a small set of strategy templates. A type records the entrant’s deterministic result against every type, and the focal type \(f\) is the cohort of entrants with the favorite’s complete match profile. With \(N\) bracket positions and \(\tau\) supported types, the regime of interest has large \(N\) and moderate \(\tau\). Type mass is the fraction of entrants in that cohort.
My anchor is Theorem 2, proved in this paper using a reduction for TFP from Aziz et al. (2014). It says: under ETH, for every constant \(c>1\), no algorithm solves TFP in time \(2^{2^{\ell/c}}\cdot n^{O(1)}\), where \(n\) is the number of players and \(\ell\) is the favorite’s out-degree. In other words, the paper rules out that running-time bound even when parameterizing by how many players the favorite can beat.
Here is the continuous question I would put to a prover. Continuous Type Tournament Fixing, parameterized by \(\lambda\): an instance gives an explicit balanced bracket with \(N=2^h\) leaves; a finite set \(\mathcal T\) of entrant types with a complete match-outcome relation; binary-rational masses \(\mu_t\geq 0\) summing to \(1\); and a target type \(f\) with \(\mu_f\geq 1/N\). Each type is a nonatomic population of interchangeable entrants. A mass of \(1/N\) is assigned to each leaf, with total mass \(\mu_t\) assigned across all leaves for every type \(t\). At each match, equal masses from the two child populations are paired; each pair advances the type that wins their matchup. Entrants of the same type produce an advancing entrant of that type. The question is whether there is a leaf assignment and a set of such pairings for which the root’s entire mass \(1/N\) has type \(f\). The parameter is
\[
\lambda=\bigl|\{t\in\operatorname{supp}(\mu)\setminus\{f\}: f\text{ beats }t\}\bigr|,
\]
the number of distinct supported types the favorite type can beat.
I expect this mirror to be tractable. For every leaf \(\ell\) and type \(t\), let \(p_{\ell,t}\) be the assigned mass. At an internal node \(v\), let \(z_{v,a,b}\) be the mass pairing type \(a\) from the left child with type \(b\) from the right child. Its row and column sums must equal the child distributions, and its output distribution is the sum of \(z_{v,a,b}\) over pairs with each possible winner type. These are linear constraints. The leaf masses must sum to \(\mu\), each leaf has mass \(1/N\), and the root constraint is \(p_{\mathrm{root},f}=1/N\). This LP has polynomial size in \(N\), \(\tau\), and the input bit length \(L\). The continuous problem therefore has a polynomial-time solution; the ETH lower bound in Theorem 2 does not carry over to this model.
This case covers Theorem 2’s out-degree lower-bound question only. The tournament mechanics, seeding decision, and target-winner condition remain central. The continuous analogue changes the population into type mass, so bracket positions can receive fractional amounts of a type and matches can pair those amounts. That is the source of the LP and the potential tractability gain.
The weakest point is the target: the paper asks whether one named player can win, while this mirror asks whether a homogeneous cohort can occupy the champion mass. I think authors could recognize it as their problem in a repeated-entry or archetype-based competition, where entrants of one type are interchangeable in every matchup. They could also reasonably reject it if preserving the identity of the single favorite is essential. The discrete ETH reduction uses individual players as separate combinatorial objects, and a nonatomic cohort cannot represent that indivisibility. A useful next question is how much integrality is needed to recover the discrete problem: for example, whether an atomic favorite with nonatomic opponents has a meaningful mass-flow mirror, and where its relaxation first develops an integrality gap.
The best objection is that Theorem 2’s parameter counts *individual players* whom one named favorite can beat. The proposed mirror counts opponent types and asks whether a whole target type can supply the champion. That changes the central object: in the paper, a particular player must win; in the mirror, an interchangeable cohort must produce a winner of its type. Requiring the target type to have mass at least \(1/N\) does not restore the favorite’s identity. The LP can split that mass among leaves and pairings, while a player in one knockout bracket occupies a single leaf and follows one path.
One could preserve the named favorite as an atom and make the opponents nonatomic. But then the favorite’s single path has to be tracked separately from the population flow. That is a hybrid model, and the atom cannot simply be absorbed into a nonatomic society: if its mass vanishes, its exact win condition vanishes with it; if it retains positive mass, it represents more than one player. This makes the anchor a poor *direct* mirror of Theorem 2.
That objection does not defeat the stronger cohort version. A competition among many interchangeable entrants, with the goal that the desired archetype wins, is a plausible high-multiplicity problem. Its mass-flow formulation asks a concrete computational question, and whether it becomes tractable is a potential result, not a reason to dismiss it. The paper’s tournament mechanics still matter, even though the cohort objective and fractional bracket assignments need the authors’ endorsement as a natural variant.
So the honest negative case is weak. The identity change marks a real modeling choice, but it does not show that the cohort problem is unworthy or that no scenario makes it sensible. I would not use it to support the universal claim that there is no worthwhile continuous mirror.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.