Answer: The problem is in \(\mathrm{P}\), with running time \(O(L)\). The answer is YES exactly when \(m=1\) and \(K\ge 0\); for every \(m\ge 2\), no componentwise inclusion-minimal sufficient support exists.
Theorem 3 — class: hardness
Given a finite candidate set \(C\), a finite set \(T\) of complete pairwise-judgment types, a rational distribution \(\nu\) over \(T\), a target \(w\) in the weighted uncovered set of the induced society, and a rational threshold \(K\), let \(p(a,b)=\sum_{t\in T}\nu_t\mathbf{1}[t\text{ ranks }a\text{ above }b]\). Decide whether there is a componentwise inclusion-minimal matrix \(x\) satisfying \(0\leq x(a,b)\leq p(a,b)\) and \(x(a,b)+x(b,a)\leq1\), such that \(w\) is in the weighted uncovered set of every completion \(q\) with \(q(a,b)\geq x(a,b)\) and \(q(a,b)+q(b,a)=1\), and \(\sum_{a\ne b}x(a,b)\leq K\).
Let \(C\) be a nonempty candidate set with \(m=|C|\). A type gives exactly one strict judgment for each unordered pair of distinct candidates; judgments need not be transitive.
A society is given by its support: the list \(T\) of its \(\tau\) positive-mass types, each mass \(\nu_t\) a binary rational, with \(\sum_{t\in T}\nu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Define \(p(a,b)=\sum_{t\in T}\nu_t\mathbf 1[t\text{ judges }a\text{ above }b]\) for distinct candidates, and \(p(a,a)=0\).
For any complete real matrix \(q\) with zero diagonal, nonnegative entries, and \(q(a,b)+q(b,a)=1\) for distinct candidates, define its weighted uncovered set \(\operatorname{wUC}(q)\) by: \(u\in\operatorname{wUC}(q)\) precisely when every \(v\ne u\) satisfies \(q(u,v)>q(v,u)\) or admits \(z\in C\setminus\{u,v\}\) with \(q(u,z)>q(v,z)\). These inequalities are strict; no tie-breaking is applied.
The input additionally contains \(w\in\operatorname{wUC}(p)\) and a binary-rational threshold \(K\). A support is a real matrix \(x\) with zero diagonal, \(0\le x(a,b)\le p(a,b)\), and \(x(a,b)+x(b,a)\le1\) for distinct candidates. Its completions are all complete real matrices \(q\ge x\) as above, without restrictions to the original types.
A support is sufficient if \(w\in\operatorname{wUC}(q)\) for every completion. It is componentwise inclusion-minimal if it is sufficient and no distinct support \(y\le x\) is sufficient. Decide whether such a minimal support exists with \(\sum_{a\ne b}x(a,b)\le K\).
Is this decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For complete integer-weighted tournaments with \(n\ge2\), a promised weighted-uncovered winner, and an integer threshold, existence of a minimal support within the threshold is NP-complete. [Verified discrete result](https://arxiv.org/html/2509.09312v4).
No complexity result for this exact continuous decision problem was identified in the sources checked.
The decision problem as stated is in \(\mathrm{P}\). More precisely, its answer is YES exactly when \(m=1\) and \(K\ge 0\).
For every \(m\ge 2\), sufficient supports exist under the winner promise, but none is componentwise inclusion-minimal. This follows from the strict inequalities and the ability to decrease real support weights arbitrarily slightly.
Lemma. A support \(x\) is sufficient if and only if, for every \(v\ne w\), at least one of the following holds:
Proof. First suppose these conditions hold. Let \(q\) be any completion of \(x\), and fix \(v\ne w\).
If the first condition holds, then \(q(w,v)\ge x(w,v)>\tfrac12\). Since \(q(v,w)=1-q(w,v)\), this gives \(q(w,v)>q(v,w)\).
If the second condition holds, choose its witness \(z\). Completeness and \(q\ge x\) give
\(q(v,z)=1-q(z,v)\le 1-x(z,v)\). Consequently,
\(q(w,z)\ge x(w,z)>1-x(z,v)\ge q(v,z)\).
Thus every rival satisfies one of the defining conditions for \(w\in\operatorname{wUC}(q)\). Since \(q\) was arbitrary, \(x\) is sufficient.
Conversely, suppose both conditions fail for some \(v\ne w\). Then
\(x(w,v)\le\tfrac12\), and \(x(w,z)+x(z,v)\le1\) for every \(z\in C\setminus\{w,v\}\).
Construct a completion by setting
These prescriptions concern distinct unordered pairs, so they are consistent. Assign the reverse entry on each prescribed pair by completeness. Every reverse entry respects its lower bound because \(x(a,b)+x(b,a)\le1\). Complete all remaining pairs in the same way: choose either orientation, set its entry to the corresponding entry of \(x\), and set the reverse entry to its complement.
The resulting matrix is a completion of \(x\). It satisfies \(q(w,v)\le q(v,w)\), and, for every eligible \(z\),
\(q(w,z)=x(w,z)\le1-x(z,v)=q(v,z)\).
Hence \(v\) defeats both alternatives in the definition of membership for \(w\), so \(w\notin\operatorname{wUC}(q)\). Therefore \(x\) is not sufficient. \(\square\)
Proposition. If \(m\ge2\) and \(x\) is sufficient, there exists a distinct sufficient support \(y\le x\).
Proof. For each \(v\ne w\), select one witness from the lemma. Write its inequality as \(A_v(x)>b_v\), where either
Each \(A_v\) is homogeneous: \(A_v(\lambda x)=\lambda A_v(x)\).
There are finitely many rivals, and each selected inequality is strict. Therefore the number
\(r=\max_{v\ne w} b_v/A_v(x)\)
is defined and satisfies \(0<r<1\).
Choose \(\lambda=(1+r)/2\), and set \(y=\lambda x\). Then \(0<\lambda<1\). In particular, \(y\) has zero diagonal, \(0\le y\le x\le p\), and
\(y(a,b)+y(b,a)=\lambda\bigl(x(a,b)+x(b,a)\bigr)\le1\).
Thus \(y\) is a support.
For every rival,
\(A_v(y)=\lambda A_v(x)>b_v\), because \(\lambda>r\ge b_v/A_v(x)\).
The lemma therefore shows that \(y\) is sufficient.
Finally, \(x\ne0\): with at least one rival, the lemma requires a positive witness value. Hence \(\lambda<1\) implies \(y\ne x\). \(\square\)
It follows immediately that no sufficient support is componentwise inclusion-minimal when \(m\ge2\).
This is not a failure of the winner promise to ensure sufficiency. Indeed, \(p\) itself is sufficient: any complete \(q\ge p\) must equal \(p\), since both entries on each unordered pair sum to one. The promise gives \(w\in\operatorname{wUC}(p)\).
If \(m=1\), the zero matrix is the only support and completion. Membership of \(w\) is vacuous, so this support is sufficient and componentwise minimal. Its total weight is zero. The answer is therefore YES exactly when \(K\ge0\).
If \(m\ge2\), the proposition gives NO for every threshold \(K\).
Thus the algorithm checks \(m\), and, only if \(m=1\), checks the sign of \(K\). Including reading the promised input, its running time is \(O(L)\). It requires no aggregation over the \(\tau\) types and no computation of the pairwise matrix.
The cited result uses integer weights for both partial tournaments and completions; see its definitions and [Theorem 9](https://arxiv.org/html/2509.09312v4#S4.SS2).
After normalization by the total integer weight \(n\), those supports remain restricted to a finite grid with spacing \(1/n\). Scaling a support slightly downward generally leaves that grid. In the present problem, real weights are allowed, and the scaling argument preserves all selected strict witnesses.
Already with two candidates and \(p(w,v)=1\), sufficient supports are exactly those with \(x(w,v)\in(\tfrac12,1]\). Their weights have infimum \(\tfrac12\), but no minimal support exists. The proposition proves the same absence of minimality for every \(m\ge2\), without changing the stated definitions.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the stated continuous decision problem. The answer is YES exactly when \(m=1\) and \(K\ge 0\). The claimed \(O(L)\) running time is valid. No major or minor mathematical issues were found.
Both proposed witness conditions correctly guarantee the required strict inequalities in every completion.
\[ q(w,z)\ge x(w,z)>1-x(z,v)\ge q(v,z). \]
The witness \(z\) belongs to the required domain \(C\setminus\{w,v\}\). Since the argument applies to every rival and every completion, the universal quantifiers in sufficiency are satisfied.
Finding: Correct.
Failure of both witness conditions for a fixed rival \(v\) means precisely
\[
x(w,v)\le\tfrac12
\]
and
\[
x(w,z)+x(z,v)\le1
\]
for every eligible \(z\). Equality is correctly included because membership uses strict inequalities.
The prescribed unordered pairs are all distinct:
Thus the construction imposes no conflicting assignments.
Every assigned entry respects its lower bound. For an entry assigned as a complement, the inequality
\[
x(a,b)+x(b,a)\le1
\]
ensures that complement is at least the opposite lower bound. All entries lie in \([0,1]\), and the remaining pairs can be completed exactly as described.
In the resulting completion,
\[
q(w,v)\le q(v,w)
\]
and
\[
q(w,z)\le q(v,z)
\]
for every eligible \(z\). Consequently, this particular rival violates both alternatives required for membership of \(w\).
The construction does not need to satisfy \(q\le p\): the task places that restriction on supports, not on completions.
Finding: Correct. The lemma establishes an exact equivalence.
For \(m\ge2\), the rival set is finite and nonempty. Sufficiency supplies at least one witness for each rival, so the stated selection is legitimate.
Each selected inequality satisfies \(A_v(x)>b_v>0\). Therefore every denominator is positive and
\[
0<\frac{b_v}{A_v(x)}<1.
\]
The maximum over finitely many rivals consequently satisfies \(0<r<1\). The chosen factor \(\lambda=(1+r)/2\) satisfies \(r<\lambda<1\).
Finding: Correct. No limiting or attainment assumption is missing.
Scaling by \(0<\lambda<1\) preserves the zero diagonal, nonnegativity, the upper bounds \(y\le x\le p\), and every pair-sum constraint.
Homogeneity gives
\[
A_v(y)=\lambda A_v(x)>b_v
\]
for every selected witness. Applying the already proved lemma therefore establishes sufficiency of \(y\).
Finally, the nonempty rival set forces at least one positive witness value, hence \(x\ne0\). Thus \(y=\lambda x\ne x\).
This directly contradicts componentwise inclusion-minimality for every sufficient support when \(m\ge2\).
Finding: Correct. The proposition proves the claimed absence of minimal supports.
The claim that \(p\) itself is sufficient is valid. For each unordered pair, a complete \(q\ge p\) has the same pair sum as \(p\), namely one. Neither entry can increase without violating that sum, so \(q=p\).
The supplied promise \(w\in\operatorname{wUC}(p)\) therefore establishes sufficiency of \(p\). This is consistent with the absence of inclusion-minimal sufficient supports.
Finding: Correct.
When \(m=1\), the zero diagonal forces the unique support and completion to be the zero matrix. Membership is vacuous, minimality holds because no distinct support exists, and the empty weight sum equals zero. The threshold condition is therefore exactly \(K\ge0\).
When \(m\ge2\), no minimal support exists, regardless of the threshold, including negative thresholds.
The algorithm uses only the candidate count and, when necessary, the sign of the binary-rational threshold. Reading the explicit input costs \(O(L)\), so the stated bound is valid in \(m,\tau,L\). No computation involving the support types or pairwise probabilities is needed under the input promises.
Finding: Correct.
The cited paper defines integer-valued partial weighted tournaments and completions, and its Theorem 9 states the discrete NP-completeness result under the winner promise. Thus the prover accurately identifies the discrete domain restriction. [Definitions and Theorem 9](https://arxiv.org/html/2509.09312v4)
Normalization leaves those weights on a finite grid, whereas the present task permits arbitrary real supports. The scaling argument is therefore applicable to the present problem without establishing the corresponding discrete conclusion.
The two-candidate example is also correct: \(p(w,v)=1\) forces \(p(v,w)=0\), so sufficient supports have precisely \(x(w,v)\in(\tfrac12,1]\). The stated infimum and absence of a minimal support follow from the characterization and scaling proposition already proved.
Finding: Correct. The cited theorem is contextual; the continuous proof does not depend on it.
No additional lemma, clarification, or mathematical 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.