Answer: Polynomial-time solvable: the outcome function belongs to \(\mathrm{FP}\), with a conservative running-time bound of \(O(L^3+m\tau L^2)\) bit operations.
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm \ref{algorithm:SRAA} satisfies the Conservative Reality-Aware $\delta$-Supermajority Condorcet criterion.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite agenda \(A\) with status quo \(r\), a rational \(\delta\), and a support of \(\tau\) complete rankings with positive rational masses summing to one, compute the outcome of Algorithm 1 on the weighted pairwise tallies, using the paper's \(\delta\)-supermajority and tie conventions.
Let \(A\) be a finite set of \(m\geq 1\) alternatives with distinguished status quo \(r\in A\), and let \(\delta\in[0,\tfrac12]\) be a binary rational. The input includes a fixed ordering of \(A\setminus\{r\}\).
A society is given by its support: the list of its \(\tau\) distinct strict complete rankings, each with positive binary-rational mass; masses sum to \(1\). Here \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
For distinct alternatives, define \(p(a,b)=\sum_{i:a\succ_i b}\mu_i\). Alternative \(a\) beats \(b\) by a \(\delta\)-supermajority exactly when \(p(a,b)>\tfrac12+\delta\); equality does not suffice. Define the viable set \(B=\{a\in A\setminus\{r\}:p(a,r)>\tfrac12+\delta\}\).
The conservative supermajority amendment procedure returns \(r\) if \(B\) is empty. Otherwise start with incumbent \(r\) and process \(B\) in the input ordering, replacing the incumbent by the challenger exactly when the challenger beats it by a \(\delta\)-supermajority; otherwise retain the incumbent.
Let \(w\) be the final incumbent. Return \(w\) exactly when it beats every member of \(B\setminus\{w\}\) by a \(\delta\)-supermajority, using recorded comparisons and testing any remaining pairs; otherwise return \(r\). An inconclusive comparison provides no certified victory to either side.
Is computing the outcome of this procedure polynomial-time solvable in \(m,\tau,L\), or is it NP-hard?
For finite electorates, an efficient amendment procedure is given and proved to satisfy the conservative supermajority Condorcet criterion: elect the supermajority Condorcet winner among viable alternatives if one exists, and otherwise retain reality. [Primary source](https://www.ijcai.org/proceedings/2019/0081.pdf).
Neither that source nor its [full preprint](https://weizmann.elsevierpure.com/ws/files/112742980/1807.11105v5.pdf) states a complexity result for the binary-rational support representation specified here.
Computing the outcome is polynomial-time solvable in \(m,\tau,L\). A conservative bound is \(O(L^3+m\tau L^2)\) bit operations. The algorithm uses only \(O(m)\) pairwise supermajority tests, each evaluated exactly from the listed support.
The cited paper gives the amendment procedure and its Condorcet guarantee in Algorithm 1 and Theorem 3. The proof below establishes the complexity bound for the representation in this question, using its strict threshold and explicit treatment of inconclusive comparisons. [Primary source](https://www.ijcai.org/proceedings/2019/0081.pdf).
Write the input masses as \(\mu_i=u_i/v_i\), for \(1\leq i\leq\tau\), and write \(\delta=d/e\), where all denominators are positive integers encoded in binary. Reduced fractions are unnecessary.
Define the integers
\(D=2e\prod_{i=1}^{\tau}v_i\),
\(W_i=u_i(D/v_i)\), and
\(H=(e+2d)(D/(2e))\).
Every indicated division is exact. Furthermore,
\(W_i=D\mu_i\) and \(H=D(\tfrac12+\delta)\).
For each ranking, store \(\operatorname{pos}_i(a)\), the position of alternative \(a\), with smaller positions indicating greater preference. For distinct alternatives define
\(S(a,b)=\sum_{i:\operatorname{pos}_i(a)<\operatorname{pos}_i(b)}W_i\).
Then \(S(a,b)=Dp(a,b)\). Since \(D>0\), the required test is exactly
\(p(a,b)>\tfrac12+\delta\ \Longleftrightarrow\ S(a,b)>H\).
In particular, equality fails the test. No numerical approximation is involved.
Bit lengths. The binary length of \(D\) is at most
\(2+\operatorname{bits}(e)+\sum_i\operatorname{bits}(v_i)=O(L)\).
Since the masses are positive and sum to \(1\), we have
\(\sum_iW_i=D\). Thus every partial sum used to compute \(S(a,b)\) lies between \(0\) and \(D\). Also \(0\leq H\leq D\), because \(0\leq\delta\leq\tfrac12\). Consequently all these integers have \(O(L)\) bits.
Using schoolbook integer arithmetic, preprocessing \(D\), the weights, and \(H\) costs \(O((\tau+1)L^2)\) bit operations. Given the position tables, one pairwise test requires scanning \(\tau\) rankings and adding selected \(O(L)\)-bit weights, costing \(O(\tau L)\) arithmetic bit operations.
Execute the following steps.
The equivalence proved in Section 1 shows that every test has exactly the outcome specified in the question. Induction over the ordered challengers therefore shows that Step 2 produces exactly the prescribed incumbent. Step 3 implements exactly the prescribed certification condition.
For a recorded comparison, a failed test in one direction does not certify victory in the reverse direction. One may instead record the exact sum: strict complete rankings imply \(S(b,a)=D-S(a,b)\), so either direction can subsequently be tested exactly.
If \(B\neq\varnothing\), its first challenger defeats \(r\) by the definition of viability. All subsequent incumbents belong to \(B\), so the final \(w\) belongs to \(B\).
For distinct \(a,b\), strict complete rankings and normalized masses imply \(p(a,b)+p(b,a)=1\). Because \(\delta\geq0\), both directions cannot satisfy the supermajority threshold: that would imply
\(1=p(a,b)+p(b,a)>1+2\delta\), a contradiction.
Suppose \(c\in B\) beats every member of \(B\setminus\{c\}\) by a \(\delta\)-supermajority. When \(c\) is processed, the incumbent is either \(r\) or an earlier member of \(B\). In the former case, \(c\) defeats it by viability; in the latter, by the assumed property of \(c\). Thus \(c\) becomes incumbent.
Every later challenger loses its supermajority test against \(c\), by the impossibility of victories in both directions. Hence \(c\) remains the final incumbent and passes every certification test.
Conversely, if no such \(c\) exists, the final incumbent \(w\in B\) fails at least one certification test, so the procedure returns \(r\). This also proves uniqueness whenever such a winner exists.
Let \(k=|B|\). Viability requires \(m-1\) pairwise tests, the amendment stage at most \(k\), and certification at most \(k-1\). Thus there are fewer than \(3m\) tests altogether. Their total arithmetic cost is \(O(m\tau L)\).
Building position tables and managing indices also takes polynomial time. With schoolbook arithmetic and a conservative allowance for input parsing and table access, the entire algorithm runs in \(O(L^3+m\tau L^2)\) bit operations. Here \(\tau\leq L\), since every support entry is explicitly listed. The algorithm neither enumerates unlisted rankings nor expands masses into individual voters.
When \(m=1\), the viable set is empty and the outcome is \(r\). When \(\delta=\tfrac12\), the threshold is \(1\), so no alternative is viable and the outcome is again \(r\). The proof covers all intermediate thresholds, including equality cases and inconclusive comparisons.
Therefore the outcome function belongs to \(\mathrm{FP}\); the associated decision problem of whether a specified alternative is returned belongs to \(\mathrm{P}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned task correctly. Computing the specified outcome is polynomial-time solvable in \(m,\tau,L\). The exact arithmetic, simulation, certification step, and conservative runtime bound are valid. No substantive or minor repair is required.
The definitions
\[
D=2e\prod_{i=1}^{\tau}v_i,\qquad
W_i=u_i(D/v_i),\qquad
H=(e+2d)(D/(2e))
\]
are valid: every denominator is positive, and both indicated divisions are exact.
The identities \(W_i=D\mu_i\) and \(H=D(\tfrac12+\delta)\) follow directly. Thus \(S(a,b)=Dp(a,b)\), and multiplication by the positive integer \(D\) preserves the strict comparison.
In particular, \(S(a,b)=H\) does not certify a victory. This correctly implements the task’s strict threshold.
The bound on the binary length of \(D\) is valid. Although its numerical value may be large, its binary length is bounded by the sum of the input denominator lengths, hence by \(O(L)\).
Normalization gives \(\sum_iW_i=D\). Positivity then ensures that each weight and every partial sum lie between \(0\) and \(D\). The stated range of \(\delta\) also gives \(0\leq H\leq D\). Consequently, the weights, threshold, sums, and arithmetic intermediates have \(O(L)\) bits.
The preprocessing bound \(O((\tau+1)L^2)\) is valid with schoolbook multiplication and division. Computing a pairwise sum requires at most \(\tau\) additions of \(O(L)\)-bit integers, so \(O(\tau L)\) arithmetic bit operations per test is justified. The prover appropriately treats table access separately in its final bound.
Step 1 computes exactly the viable set in the supplied ordering.
Step 2 uses precisely the prescribed replacement condition. The stated induction is sufficient: the initial incumbent agrees with the task, and each challenger causes the same replacement or retention in both executions.
When \(B\) is nonempty, its first challenger defeats \(r\). Each subsequent incumbent is retained from, or replaced by, a member of \(B\). Therefore the final incumbent belongs to \(B\), as claimed.
Step 3 checks every required directed victory of the final incumbent. It therefore implements the task’s certification condition exactly.
The treatment of recorded comparisons is correct. A failed directed test is not used as evidence of a reverse victory.
Strict complete rankings imply that each ranking contributes to exactly one direction of a distinct pair. Hence
\[
S(b,a)=D-S(a,b).
\]
Recording the exact sum consequently permits either direction to be tested later, including cases where neither direction meets the threshold. No unjustified inference from an inconclusive comparison occurs.
The identity \(p(a,b)+p(b,a)=1\) uses precisely the given completeness, strictness, and normalization assumptions.
The impossibility of simultaneous victories is correctly established: two victories would imply \(1>1+2\delta\), contradicting \(\delta\geq0\).
For a supermajority Condorcet winner \(c\) in \(B\), the incumbent encountered when \(c\) is processed is either \(r\) or an earlier viable alternative. The stated assumptions certify \(c\)’s victory in either case. No later challenger can defeat \(c\), and \(c\) passes certification.
Conversely, if no such winner exists and \(B\) is nonempty, the final incumbent in \(B\) necessarily fails a required certification test. The uniqueness claim follows from the already established impossibility of victories in both directions.
The bibliographic attribution is accurate: Algorithm 1 and Theorem 3 concern the conservative supermajority amendment procedure and its Condorcet criterion. The prover supplies its own correctness and complexity arguments rather than relying on that theorem for the rational-support representation. [Primary source](https://www.ijcai.org/proceedings/2019/0081.pdf).
In the nonempty branch, the comparison counts \(m-1\), at most \(k\), and at most \(k-1\) are correct. In the empty branch, execution ends after viability testing. Both branches use fewer than \(3m\) tests.
The arithmetic total \(O(m\tau L)\) follows. Explicitly listed support entries give \(\tau\leq L\), so the arithmetic preprocessing is covered by \(O(L^3)\). The final bound \(O(L^3+m\tau L^2)\) conservatively accommodates parsing, position tables, indexing, and comparison bookkeeping.
The cases \(m=1\), \(\delta=\tfrac12\), threshold equality, and inconclusive comparisons are handled correctly. A singleton viable set also passes the empty certification condition, as required.
The conclusions about \(\mathrm{FP}\) and the associated decision problem in \(\mathrm{P}\) follow. The proof establishes the requested polynomial-time classification without expanding rational masses into individual voters.
None. The write-up establishes the claimed result under the input assumptions.
⟨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.