Answer: Polynomial-time solvable, in \(\mathrm{P}\); an exact feasible completion can also be constructed in polynomial time.
Proposition 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateVEI-INCOMPLETE detects in polynomial (in 𝑚× 𝑛) time whether a profile of dichotomous preferences possibly satisfies VEI. If it does, VEI-INCOMPLETE also finds an appropriate order of the voters that we can easily complete in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given alternatives \(A=\{a_1,\ldots,a_m\}\) and a rational distribution \(\mu\) over a support \(\mathcal{P}\subseteq\{0,1,?\}^m\) of partial approval reports, with \(\tau=|\mathcal{P}|\), decide whether every unit of mass can receive a complete ballot extending its report, with the completed population ordered so each alternative’s approving set is a prefix or suffix. Equivalently, decide whether there are ballots \(b_p\in\{0,1\}^m\) extending each \(p\in\mathcal{P}\) and a permutation \(\sigma\) of \(\mathcal{P}\) such that, for every \(a_i\), the sequence \(b_{\sigma(1)}(a_i),\ldots,b_{\sigma(\tau)}(a_i)\) has form \(1^*0^*\) or \(0^*1^*\); assign each type a consecutive interval of length \(\mu_p\).
Given alternatives \(A=\{a_1,\ldots,a_m\}\), with \(m\geq2\), a society is given by its support: a list \(\mathcal P\subseteq\{0,1,?\}^m\) of \(\tau\geq1\) distinct types with positive binary rational masses \(\mu_p\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible reports; \(L\) is the total input bit length.
A report entry \(1\) means approval, \(0\) disapproval, and \(?\) an unrestricted unknown entry. A complete ballot \(b_p\in\{0,1\}^m\) extends \(p\) when it preserves every known entry.
A feasible completion chooses one ballot \(b_p\) for each type and a permutation \(\sigma\) of the support. Type \(\sigma(j)\) occupies a consecutive interval of length \(\mu_{\sigma(j)}\) in \([0,1)\), with its entire mass receiving its chosen ballot. For each alternative, its approving intervals must form a prefix or suffix of \([0,1)\); empty and full approving sets are permitted, and the choice of prefix or suffix may differ between alternatives.
Is deciding whether such a feasible completion exists solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite lists of voters, deciding whether partial approval reports admit a completion whose approving sets are prefixes or suffixes of a common voter order is polynomial-time solvable, and an order and completion can also be constructed in polynomial time ([Terzopoulou, Karpov, and Obraztsova](https://www.ifaamas.org/Proceedings/aamas2020/pdfs/p2023.pdf)).
The [full version](https://ojs.aaai.org/index.php/AAAI/article/download/16718/16525) retains this discrete result. No prior result explicitly treating the exact rational-mass formulation above was located.
Proven result. The decision problem is polynomial-time solvable in \(m,\tau,L\). An order, one completed ballot per type, and exact rational interval endpoints can also be constructed in polynomial time.
Reduction to a discrete profile. Enumerate the support as \(\mathcal P=\{p^1,\ldots,p^\tau\}\). Construct the incomplete matrix \(X\in\{0,1,?\}^{m\times\tau}\) by setting \(X_{i,k}=p^k_i\). Thus, each support type becomes exactly one discrete voter.
A completion of column \(k\) is precisely a single ballot extending \(p^k\). Consequently, this construction preserves the requirement that an entire type receives one completed ballot, including when different types receive identical ballots.
We prove that \(X\) admits a completion with the discrete prefix-or-suffix property if and only if the given rational-mass society admits a feasible completion.
Proof of equivalence. Fix any permutation \(\sigma\) of the support indices and any completed ballots \(b_{p^k}\) extending the reports. Define \(s_0=0\) and, for \(1\leq j\leq\tau\),
\(s_j=\sum_{h=1}^{j}\mu_{p^{\sigma(h)}}.\)
Positivity and normalization of the masses imply \(0=s_0<s_1<\cdots<s_\tau=1\). The interval occupied by the type at position \(j\) is \(I_j=[s_{j-1},s_j)\).
For alternative \(a_i\), let \(S_i=\{j:b_{p^{\sigma(j)},i}=1\}\). Its approving set in the society is exactly \(U_i=\bigcup_{j\in S_i}I_j\).
First suppose the discrete completion has the required property. If \(S_i=\{1,\ldots,r\}\), then the adjacent intervals give \(U_i=[0,s_r)\), a prefix. If \(S_i=\{r+1,\ldots,\tau\}\), then \(U_i=[s_r,1)\), a suffix. Taking \(r=0\) or \(r=\tau\) also covers empty and full approving sets. Hence a discrete feasible completion yields a rational-mass feasible completion.
Conversely, suppose the rational-mass completion is feasible. If \(U_i\) is a prefix, we show that \(S_i\) is an initial segment. Take \(j\in S_i\) and \(k<j\). Both \(I_k\) and \(I_j\) are nonempty, so choose \(x\in I_k\) and \(y\in I_j\). Then \(x<y\) and \(y\in U_i\). A prefix contains every earlier point, so \(x\in U_i\). Because the intervals partition \([0,1)\) and each entire interval has one ballot, this implies \(k\in S_i\). Thus \(S_i\) is an initial segment.
If \(U_i\) is a suffix, the same argument with \(k>j\) shows that \(j\in S_i\) implies \(k\in S_i\); therefore \(S_i\) is a final segment. Empty and full sets satisfy both conditions. This proves the equivalence for every alternative, allowing its orientation to be chosen independently.
Application of the discrete theorem. Proposition 7 of Terzopoulou, Karpov, and Obraztsova’s [full version](https://ojs.aaai.org/index.php/AAAI/article/download/16718/16525) states that, for an incomplete dichotomous profile, deciding whether a completion satisfies Voter External Interval is polynomial-time solvable; an appropriate voter order and completion can also be constructed. Their Definition 1 defines this property by requiring each alternative’s approvers to form a prefix or suffix of one common voter order.
The constructed matrix satisfies these hypotheses: it has \(m\) alternatives, \(\tau\) voters, unrestricted unknown cells, and exactly the required ordering property. Apply that algorithm with its voter parameter equal to \(\tau\). By the proved equivalence, its answer is also the answer to the rational-mass problem.
Bit complexity and exact construction. Constructing \(X\) takes \(O(m\tau)\) time. The discrete algorithm takes polynomial time in \(m,\tau\); deciding feasibility requires no arithmetic on the masses.
For an exact interval witness, write each input mass as \(\mu_{p^k}=u_k/v_k\), with positive integer denominator \(v_k\), and use the common denominator \(Q=\prod_{k=1}^{\tau}v_k\). Its binary length is \(O(L)\), because the sum of the input denominators’ binary lengths is at most \(L\). Every endpoint \(s_j\) can be represented as \(N_j/Q\), where \(0\leq N_j\leq Q\). Computing these numerators uses polynomially many integer operations on \(O(L)\)-bit integers, hence polynomial bit complexity.
Therefore both decision and exact witness construction are polynomial-time solvable in \(m,\tau,L\).
⟨structured verdict parsed — rendered above⟩
The argument is sound in substance and establishes polynomial-time solvability, subject to one minor omission: the cited theorem assumes at least two voters, whereas the task permits a support of size one. No major issue was found.
The matrix \(X\) has exactly \(m\) rows and \(\tau\) columns, with \(X_{i,k}=p_i^k\). Completing a column assigns precisely one complete ballot to that type while preserving its known entries.
This preserves the requirement that the entire mass of a type receives a single ballot. Distinct types may receive identical completed ballots without affecting the construction. No expansion proportional to mass denominators occurs.
For any fixed order and completed ballots, positivity of every mass gives strictly increasing cumulative sums, and normalization gives \(s_\tau=1\). Thus the intervals \(I_j=[s_{j-1},s_j)\) are nonempty, pairwise disjoint, and partition \([0,1)\).
Consequently, the approving set for an alternative is exactly the union of the intervals corresponding to its approving columns.
An initial segment of approving columns yields \([0,s_r)\), and a final segment yields \([s_r,1)\). The stated endpoint choices cover both empty and full approving sets.
The proof applies separately to each alternative, so it preserves the permitted independent choice of orientation.
If an approving interval occurs at position \(j\), every point of an earlier interval precedes every point of that interval. Downward closure of a prefix therefore forces each earlier interval to approve. Since intervals are disjoint and ballots are constant throughout each interval, membership of the selected point in the approving union implies that its interval is an approving interval.
The suffix argument uses the corresponding upward closure. Nonemptiness, needed to select the points, follows from strict positivity. Empty and full sets are explicitly covered. The equivalence is established for the same order and ballots in both directions.
The cited source’s Definition 1 gives exactly the common-order prefix-or-suffix property. Proposition 7 provides polynomial-time recognition, an appropriate voter order, and a suitable completion for incomplete dichotomous profiles. Its incomplete entries are unrestricted, and its model imposes no distinctness requirement on completed columns. These match the reduction. However, the source’s preliminary model assumes \(n\geq2\). [Full version, Sections 2 and 4](https://ojs.aaai.org/index.php/AAAI/article/download/16718/16525).
Minor issue: The statement “The constructed matrix satisfies these hypotheses” overlooks the allowed case \(\tau=1\).
Minimum clarification required: Explicitly handle \(\tau=1\) for both decision and witness construction, and restrict the invocation of Proposition 7 to \(\tau\geq2\). This is a routine boundary-case clarification requiring no new mathematics.
Constructing \(X\) requires \(O(m\tau)\) work. For valid inputs, feasibility depends only on this matrix, so the decision stage need not perform arithmetic on the masses.
The binary length of \(Q=\prod_k v_k\) is bounded by the sum of the denominator lengths, hence is \(O(L)\). Every endpoint numerator lies between \(0\) and \(Q\), so its binary length is also \(O(L)\). The stated construction uses polynomially many integer operations on integers of polynomial bit length. Reduced fractions are unnecessary for exact representation.
The prover resolves the intended complexity question in substance. The equivalence and arithmetic bounds are rigorous; the sole repair needed is an explicit treatment of the one-type case.
⟨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.