Answer: Polynomial-time solvable (\(\mathrm{P}\)).
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet q be a query in the class C2W. • If the WINNER atoms of q are pairwise disconnected, then Necessity(q) is decidable in polynomial time. • Otherwise, Necessity(q) is coNP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), issue relations \(\mathrm{SUPPORTS}\) and \(\mathrm{OPPOSES}\), and partial-ballot types \(t\) with rational masses \(\mu_t\) summing to \(1\), let \(y_{t,c}\ge 0\) be mass of type \(t\) completed with \(c\) first, for \(c\in\operatorname{Max}(t)\), with \(\sum_{c\in\operatorname{Max}(t)}y_{t,c}=\mu_t\). Define \(W_y=\arg\max_{c\in C}\sum_t y_{t,c}\). Is it true for every feasible \(y\) that some issue \(i\) has a candidate \(c\in W_y\) with \(\mathrm{SUPPORTS}(c,i)\) and a candidate \(d\in W_y\) with \(\mathrm{OPPOSES}(d,i)\)?
Let \(C\) be a candidate set with \(m\ge 2\), and let \(I\) be a finite issue set. The input includes arbitrary explicitly listed relations \(\mathrm{SUPPORTS},\mathrm{OPPOSES}\subseteq C\times I\); they need not be disjoint or exhaustive.
A society is given by its support: a list of \(\tau\) distinct partial-order ballot types on \(C\), each with positive binary-rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Each partial order is explicitly represented; \(\operatorname{Max}(t)\) consists of candidates with no other candidate ranked above them.
A completion may split each type's mass arbitrarily: \(y_{t,c}\in\mathbb R_{\ge0}\), with \(y_{t,c}=0\) for \(c\notin\operatorname{Max}(t)\) and \(\sum_{c\in C}y_{t,c}=\mu_t\). Its plurality winners are \(W_y=\operatorname*{arg\,max}_{c\in C}\sum_t y_{t,c}\); all tied maximizers win.
Decide whether every feasible completion satisfies \(\exists i\in I\;\exists c,d\in W_y:\ \mathrm{SUPPORTS}(c,i)\land\mathrm{OPPOSES}(d,i)\). The witnesses \(c,d\) need not be distinct.
Let \(L\) be the total binary input length. State running times in \(m,\tau,|I|,L\).
Is this continuous necessity problem solvable in polynomial time, or is it \(\mathrm{NP}\)-hard?
For finite lists of voters whose partial ballots are completed individually, this same necessity question is \(\mathrm{coNP}\)-complete; the corresponding question asking whether every completion has a winner in a designated candidate subset is polynomial-time solvable. [Discrete results](https://www.ijcai.org/proceedings/2018/0044.pdf)
No result settling this exact continuous problem was identified in the literature search.
The continuous necessity problem is polynomial-time solvable. The algorithm uses at most \(m+1\) exact maximum-flow computations.
The key fact is that any completion falsifying the query can be perturbed into another falsifying completion whose winners are either a single candidate or the entire highest-scoring group of candidates whose scores are fixed.
The discrete hardness result in the [cited paper, Example 3 and Theorem 3](https://www.ijcai.org/proceedings/2018/0044.pdf) concerns individually completed ballots. The proof below uses arbitrary continuous splitting.
Write \(A_t=\operatorname{Max}(t)\). Each \(A_t\) is nonempty because it is the maximal-element set of a partial order on a finite, nonempty set.
Write the input masses as \(\mu_t=p_t/q_t\), and let \(D=\prod_t q_t\). Define \(a_t=D\mu_t\). Then every \(a_t\) is a positive integer and \(\sum_t a_t=D\). The binary length of \(D\) is at most the total denominator encoding length, hence is \(O(L)\).
We work with scaled allocations \(x_{t,c}=Dy_{t,c}\). Their feasible set \(P\) is defined by
\(x_{t,c}\geq 0,\qquad x_{t,c}=0\text{ for }c\notin A_t,\qquad \sum_{c\in A_t}x_{t,c}=a_t.\)
The score of candidate \(c\) is \(s_c(x)=\sum_t x_{t,c}\). Scaling preserves all winner sets.
Call a candidate set \(U\subseteq C\) conflict-free if it contains no witnesses to the query: for every issue \(i\), either no member of \(U\) supports \(i\), or no member of \(U\) opposes \(i\). Thus the necessity question has answer NO exactly when some completion has a conflict-free winner set.
Conflict-freeness is hereditary: every subset of a conflict-free set is conflict-free. In particular, \(\{c\}\) is conflict-free exactly when there is no issue that \(c\) both supports and opposes. This accounts for the permitted equality \(c=d\).
Define the flexible candidates by
\(F=\bigcup_{t:\,|A_t|\geq 2}A_t,\)
and put \(B=C\setminus F\). For each \(c\in B\), its score is fixed at
\(b_c=\sum_{t:\,A_t=\{c\}}a_t.\)
If \(B\neq\varnothing\), define
\(q=\max_{c\in B}b_c,\qquad R=\{c\in B:b_c=q\}.\)
Lemma 1. For distinct candidates \(c,d\), the identity \(s_c(x)=s_d(x)\) holds for every \(x\in P\) exactly when \(c,d\in B\) and \(b_c=b_d\).
Proof. The assertion for two fixed candidates follows from their constant scores.
Suppose instead that \(c\in F\). Choose a type \(t\) with \(c,e\in A_t\), where \(e\neq c\). Compare two completions that agree on every other type and allocate all of type \(t\)'s mass respectively to \(c\) and to \(e\). The difference \(s_c-s_d\) changes by \(2a_t\) if \(e=d\), and by \(a_t\) otherwise. Both quantities are positive. Consequently, \(s_c-s_d\) cannot be identically zero. If only \(d\) is flexible, exchange their roles. \(\square\)
Lemma 2. If some completion has a conflict-free winner set, then some completion has a conflict-free winner set of one of these forms:
Proof. First choose a completion \(g\in P\) such that two candidates tie at \(g\) only when their score functions are identical on \(P\).
Such a completion exists. Indeed, \(P\) is a product of simplices and has nonempty relative interior in its affine hull. For each pair whose score functions are not identical, their difference is a nonzero affine polynomial on that affine hull. The product of these finitely many differences is a nonzero polynomial, so it cannot vanish throughout a relatively open set. Here we use the elementary fact that a nonzero real polynomial cannot vanish on an open set, obtained by induction on dimension from the univariate root bound.
Now let \(x\) have conflict-free winner set \(W\), with common winning score \(h\). Consider the feasible completion
\(z_\varepsilon=(1-\varepsilon)x+\varepsilon g.\)
For sufficiently small positive \(\varepsilon\), every member of \(W\) still beats every candidate outside \(W\). Explicitly, if \(W\neq C\), let
\(\gamma=\min_{d\notin W}(h-s_d(x))>0.\)
All scaled scores lie between \(0\) and \(D\). Thus, for \(w\in W\) and \(d\notin W\),
\(s_w(z_\varepsilon)-s_d(z_\varepsilon)\geq(1-\varepsilon)\gamma-\varepsilon D>0\)
whenever \(0<\varepsilon<\gamma/(\gamma+D)\). If \(W=C\), there are no outside candidates to exclude.
Within \(W\), the winners at \(z_\varepsilon\) are precisely the candidates maximizing \(s_c(g)\), because their scores at \(x\) were equal. By the choice of \(g\) and Lemma 1, these winners form either a singleton flexible candidate or a group of fixed candidates with identical scores.
In the latter case, that fixed score must be \(q\): a fixed candidate with a higher score would already have defeated this group at \(x\). Moreover, every member of \(R\) ties with the selected fixed winner in every completion. Hence the resulting winner set is exactly \(R\).
The resulting winner set is a subset of \(W\), so it remains conflict-free. \(\square\)
This lemma leaves at most \(|F|+1\) winner sets to test.
The tests require allocating integer supplies while keeping every recipient strictly below a common integer threshold.
Lemma 3. Consider a recipient set \(T\) with \(1\leq |T|\leq m\), integer supplies \(a_t\), and nonempty allowed sets \(A_t\subseteq T\). Let \(K\) be a positive integer.
There exists a real allocation whose recipient scores are all strictly less than \(K\) if and only if there exists one whose recipient scores are all at most \(K-1/m\).
Proof. The reverse implication is immediate.
For the forward implication, suppose a strictly feasible allocation exists. For \(S\subseteq T\), define the supply forced into \(S\) by
\(H(S)=\sum_{t:\,A_t\subseteq S}a_t.\)
For every nonempty \(S\), strict feasibility gives
\(H(S)\leq\sum_{c\in S}s_c<|S|K.\)
Since \(H(S)\) and \(|S|K\) are integers,
\(H(S)\leq |S|K-1\leq |S|(K-1/m),\)
where the second inequality uses \(|S|\leq m\). Also \(H(\varnothing)=0\).
These inequalities imply feasibility with recipient capacities \(K-1/m\) by the maximum-flow minimum-cut theorem. To verify this application, use a network with source-to-type capacities \(a_t\), type-to-allowed-recipient capacities larger than the total supply, and recipient-to-sink capacities \(K-1/m\).
For a cut containing recipient subset \(S\) on its source side and cutting no large-capacity arc, the minimum capacity is
\(\sum_t a_t-H(S)+|S|(K-1/m).\)
It is at least the total supply by the inequalities above. Cuts containing a large-capacity arc also exceed the total supply. Therefore a flow delivering every supply exists. \(\square\)
This test uses an integer-capacity network: give source-to-type arcs capacities \(ma_t\), recipient-to-sink arcs capacities \(mK-1\), and allowed type-to-recipient arcs capacities \(m\sum_t a_t+1\). A full flow, divided by \(m\), gives the required allocation.
Two boundary cases are handled directly:
For each \(c\in F\) whose singleton is conflict-free, compute its maximum attainable score
\(U_c=\sum_{t:\,c\in A_t}a_t.\)
Candidate \(c\) can be the unique winner if and only if the types with \(c\notin A_t\) can be allocated among \(C\setminus\{c\}\) so that every resulting score is strictly below \(U_c\).
To justify this equivalence, suppose \(c\) is already a unique winner. Reallocate every type containing \(c\) entirely to \(c\). This raises or preserves \(c\)'s score and lowers or preserves every other score, so \(c\) remains the unique winner and reaches \(U_c\). The remaining types therefore satisfy the stated strict inequalities.
Conversely, any allocation satisfying those inequalities becomes a completion with unique winner \(c\) when every type containing \(c\) is assigned entirely to \(c\).
Apply Lemma 3 with threshold \(K=U_c\). If this test succeeds for any conflict-free singleton, return NO.
If \(B\neq\varnothing\) and \(R\) is conflict-free, test whether \(R\) can be exactly the winner set.
Because its members are fixed candidates, the only types containing a member \(r\in R\) have maximal set \(\{r\}\). Remove those types; their forced allocations give every member of \(R\) score \(q\). Every remaining allowed set lies in \(C\setminus R\).
Thus \(R\) is exactly the winner set if and only if the remaining supplies can be allocated so that every candidate outside \(R\) has score strictly below \(q\). Test this using Lemma 3 and its boundary cases. If it succeeds, return NO.
If no test succeeds, return YES.
Correctness. Every successful test constructs a feasible completion with a conflict-free winner set, so returning NO is sound. Conversely, if necessity fails, Lemma 2 supplies a conflict-free winner set of one of the tested forms. Its corresponding feasibility test must succeed. Therefore returning YES is also sound.
Computing maximal sets, fixed scores, and integer-scaled masses takes polynomial time in the explicitly encoded input. Conflict-freeness checks take \(O(m|I|)\) Boolean operations.
There are at most \(m+1\) flow computations. Each network has at most
\(V=m+\tau+2\)
vertices and
\(E=m\tau+m+\tau+1\)
arcs. Its capacities have \(O(L+\log(m+1))\) bits: the scaled supplies and thresholds are at most \(D\), and network capacities are at most \(mD+1\).
Using Edmonds–Karp, each computation takes \(O(VE^2)\) arithmetic operations. Allowing conservative preprocessing and bit-operation costs gives the bound
\(O\!\left(L^3+\left[m|I|+(m+1)(m+\tau+2)(m\tau+m+\tau+1)^2\right](L+\log(m+1))\right).\)
This is polynomial in \(m,\tau,|I|,L\). The algorithm uses the listed support size \(\tau\); it never enumerates unlisted ballot types or individual voters.
⟨structured verdict parsed — rendered above⟩
The prover’s polynomial-time claim is established. The structural reduction, strict-inequality flow test, and running-time analysis are correct for the stated continuous input model. I found no major or minor issues requiring repair.
Every maximal set \(A_t\) is nonempty under the stated finite partial-order assumptions. The denominator product \(D\) makes each \(a_t=D\mu_t\) a positive integer, and the normalization gives \(\sum_t a_t=D\).
The encoding-length claim is valid: multiplying the denominators adds their logarithmic sizes, so \(D\) has \(O(L)\) bits. Its potentially large numerical value does not invalidate polynomial-time computation.
Scaling allocations by the positive factor \(D\) gives a bijection between the original feasible completions and \(P\), preserving all score comparisons and winner sets.
The definition of conflict-freeness is exactly the negation of the existential query for a specified winner set. It does not require the relations to be disjoint or exhaustive.
Heredity is correct: removing candidates cannot introduce supporting and opposing witnesses. The singleton criterion correctly accounts for the permission that \(c=d\); a candidate supporting and opposing the same issue cannot form a conflict-free singleton.
Thus the necessity question is correctly reduced to whether any feasible completion has a conflict-free winner set.
For \(c\in B\), any type whose maximal set contains \(c\) must have maximal set \(\{c\}\). Consequently, the displayed formula for \(b_c\) includes all contributions to \(c\), and its score is fixed.
The proof for a flexible candidate correctly uses two independently feasible allocations of one type while preserving every other type’s allocation. The change in \(s_c-s_d\) is:
Both are nonzero because \(a_t>0\). This excludes an identical score function involving a flexible candidate. For two fixed candidates, equality throughout \(P\) is equivalent to equality of their fixed scores. Lemma 1 is proved.
The existence argument for \(g\) is valid. The feasible set is a nonempty product of simplices with nonempty relative interior in its affine hull. Every score difference being excluded is a nonzero affine polynomial on that hull.
The finite product of these nonzero polynomials remains nonzero. The stated polynomial nonvanishing fact therefore supplies a feasible point avoiding every unwanted tie. This argument also accommodates a zero-dimensional affine hull.
The algorithm does not need to compute \(g\); it is used only to establish the structural reduction.
The perturbation \(z_\varepsilon\) is feasible by convexity. When there are candidates outside \(W\), the gap \(\gamma\) is positive because \(W\) contains all maximizers.
The numerical estimate is correct: all scaled scores lie in \([0,D]\), so the displayed lower bound is positive for the stated range of \(\varepsilon\). It simultaneously preserves every comparison between a member of \(W\) and an outside candidate. The case \(W=C\) is explicitly handled.
Within \(W\), the equal original scores mean that the perturbed winners are exactly those maximizing their scores at \(g\). The defining property of \(g\), together with Lemma 1, leaves precisely the two stated possibilities: a flexible singleton or a class of fixed candidates with equal scores.
In the fixed case, the common score must be \(q\). Every member of \(R\) ties with the selected fixed winner in every completion, so the resulting winner set is the entire set \(R\). Heredity preserves conflict-freeness.
Lemma 2 therefore establishes the claimed exhaustive list of at most \(|F|+1\) sets to test.
The forced-supply inequality is correct for every nonempty recipient subset \(S\). Integrality gives the full unit of slack asserted in the proof, and the subsequent inequality uses exactly the hypothesis \(|S|\leq m\).
The maximum-flow minimum-cut application is justified by the network and cut calculation supplied in the write-up. For a fixed source-side recipient set \(S\), the minimum cut avoiding large-capacity arcs has the stated capacity. The established inequalities make it at least the total supply. Any cut crossing a large-capacity arc exceeds the total supply.
Thus every cut has sufficient capacity, which is the required hypothesis for a flow delivering all supplies. Conversely, the capacity bound \(K-1/m\) immediately implies strict inequality below \(K\).
The integer network correctly multiplies every relevant capacity by \(m\). Its allowed arcs have capacity strictly greater than the scaled total supply. Dividing a full flow by \(m\) produces the required allocation.
Both boundary rules are correct: nonnegative scores cannot be strictly below a nonpositive threshold when recipients exist, and an empty recipient set can accommodate exactly zero remaining supply.
The formula for \(U_c\) is the maximum attainable score of \(c\), since each type containing \(c\) may allocate its entire mass to \(c\).
The equivalence used by the test is proved in both directions. Starting from a unique-winning completion, the specified reallocation weakly increases \(c\)’s score and weakly decreases all competing scores, preserving uniqueness. Conversely, the tested residual allocation combined with the forced allocation to \(c\) gives exactly the required strict score comparisons.
All residual allowed sets are nonempty subsets of \(C\setminus\{c\}\), so Lemma 3 applies. Filtering candidates by singleton conflict-freeness is necessary and correctly implemented.
Types containing a member of \(R\) are precisely the corresponding singleton types, so their removal leaves every remaining allowed set outside \(R\). The test for all outside scores to be strictly below \(q\) is exactly the condition that \(R\) be the complete winner set.
The boundary handling covers \(q=0\), zero remaining supply, and an empty outside candidate set. The definitions also cover \(B=\varnothing\) and \(F=\varnothing\).
Every successful test certifies a conflict-free winner set. Conversely, Lemma 2 ensures that every failure of necessity yields a winner set covered by a test. Both answer directions are therefore established. An empty issue set causes no difficulty: conflict-freeness is then vacuous.
There are at most \(m+1\) flow computations. The stated vertex and arc counts are valid upper bounds for every test network.
Each test uses at most the original total supply \(D\), and every threshold is at most \(D\). Hence all integer capacities have \(O(L+\log(m+1))\) bits. This prevents the denominator scaling from creating a hidden dependence on its numerical magnitude.
Edmonds–Karp’s \(O(VE^2)\) arithmetic-operation bound applies to these finite integer-capacity networks. The stated bit-cost factor accommodates the required comparisons, additions, and subtractions. The conservative preprocessing term and conflict-checking term are also consistent with the explicit input representation.
The displayed running-time bound is polynomial in \(m,\tau,|I|,L\), and the algorithm uses only the listed support types.
The contextual discrete citation is accurate: Example 3 states the relevant query, and Theorem 3 gives the applicable hardness classification for two connected winner atoms with distinct ordinary relation symbols. The paper’s completions are individual ballot completions. [Cited paper](https://www.ijcai.org/proceedings/2018/0044.pdf)
That discrete result is not used to establish the continuous algorithm. No additional lemma, clarification, or repair is needed.
⟨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.