Answer: \(\mathsf{NP}\text{-complete}\), already with \(m=1\) and unrestricted \(d\); polynomial-time decision and rational-position construction for fixed \(d\).
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateOCP-D(ν2) is NP-complete, when restricted to m = 1, and when all voter coordinates are {−1, +1}-valued.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a dimension \(d\), distinct types \(x^1,\ldots,x^\tau\in\{-1,+1\}^d\), positive rational masses \(\mu_i\) summing to \(1\), and a rational threshold \(q\in[0,1]\), place the incumbent at the origin and decide whether there is a position \(y\in\mathbb{R}^d\) for which \(\sum_{i=1}^{\tau}\mu_i\mathbf{1}[\|x^i-y\|_2<\|x^i\|_2]\ge q\); return such a position when one exists.
Let \(d\ge1\). A society is given by its support: distinct types \(x^1,\ldots,x^\tau\in\{-1,+1\}^d\), with \(\tau\ge1\), and positive binary rational masses \(\mu_i\) satisfying \(\sum_i\mu_i=1\). Here \(\tau\) is the support size, not the number of possible types.
There is \(m=1\) incumbent, positioned at the origin. A newcomer may choose any \(y\in\mathbb R^d\). Each type supports the closer candidate under Euclidean distance; distance ties favor the incumbent.
Given a binary rational threshold \(q\in[0,1]\), decide whether some \(y\) satisfies \(\sum_{i=1}^{\tau}\mu_i\mathbf1[\|x^i-y\|_2<\|x^i\|_2]\ge q\), and return such a position with binary rational coordinates when one exists.
Let \(L\) be the total binary input length. State running times in \(d\), \(\tau\), \(L\), and \(m=1\), with \(d\) unrestricted.
Is this rational-mass candidate-positioning decision problem in P, or is it NP-hard?
For finite lists of unit-weight voters, the decision problem is NP-complete even with one incumbent at the origin and bipolar voter coordinates; it is polynomial-time solvable for fixed \(d\). [Source](https://arxiv.org/html/2508.13841v1).
No separate published classification of this exact rational-mass formulation was identified.
The decision problem is \(\mathsf{NP}\)-complete when \(d\) is unrestricted, already with \(m=1\). Every yes-instance has a winning position with binary rational coordinates of polynomial bit length.
Thus a polynomial-time algorithm for decision and position construction exists if and only if \(\mathsf{P}=\mathsf{NP}\). For fixed \(d\), both tasks are polynomial-time solvable.
Here, binary rationals mean rationals whose numerators and denominators are encoded in binary. The case \(q=0\) is immediate: return \(y=0\).
We use the supplied unit-weight hardness result: deciding whether a newcomer can obtain at least \(k\) votes from an explicitly listed electorate is \(\mathsf{NP}\)-complete, even under Euclidean distance, with one incumbent at the origin, bipolar voter coordinates, and distance ties favoring the incumbent. These restrictions are verified in Definition 3.1, the tie convention, and Theorem 1 of [Cleveland, de Keijzer, and Polukarov](https://arxiv.org/html/2508.13841v1#S4.SS1).
Take such an instance with a nonempty voter list \(v^1,\ldots,v^n\in\{-1,+1\}^d\) and \(1\le k\le n\). Let \(x^1,\ldots,x^\tau\) be its distinct voter types, and define their multiplicities by
\[ c_i=\bigl|\{j:v^j=x^i\}\bigr|. \]
Construct the rational-mass instance with the same dimension and incumbent, and with
\[ \mu_i=\frac{c_i}{n}, \qquad q=\frac{k}{n}. \]
Every mass is positive, the types are distinct, and \(\sum_i\mu_i=1\). For every position \(y\), consolidation gives the exact identity
\[ \sum_{i=1}^{\tau}\mu_i \mathbf 1[\|x^i-y\|_2<\|x^i\|_2] = \frac1n\sum_{j=1}^{n} \mathbf 1[\|v^j-y\|_2<\|v^j\|_2]. \]
Consequently, the constructed instance reaches mass at least \(q\) if and only if the original instance obtains at least \(k\) votes.
Grouping identical vectors takes polynomial time in the explicitly listed input length. Each constructed mass and threshold uses \(O(\log(n+1))\) bits, and the constructed instance has length
\[ O\!\left(\tau d+(\tau+1)\log(n+1)+\log(d+1)\right). \]
This is a polynomial-time many-one reduction. Therefore the distinct-support rational-mass problem is \(\mathsf{NP}\)-hard. Crucially, \(\tau\) is the number of distinct types; no enumeration of all possible bipolar types occurs.
For any type \(x^i\), expanding squared distances gives
\[ \|x^i-y\|_2<\|x^i\|_2 \quad\Longleftrightarrow\quad 2x^i\cdot y>\|y\|_2^2. \]
In particular, winning type \(i\) implies \(x^i\cdot y>0\).
Suppose \(q>0\) and a real position wins a set \(S\) of types with \(\sum_{i\in S}\mu_i\ge q\). Then \(S\) is nonempty, and the strict homogeneous system
\[ x^i\cdot u>0 \qquad(i\in S) \]
is feasible.
Consider the bounded rational polytope in \(d+1\) variables
\[ P_S= \left\{ (u,t): -1\le u_j\le1\ (1\le j\le d),\ 0\le t\le d,\ x^i\cdot u\ge t\ (i\in S) \right\}. \]
A strictly feasible direction can be scaled into the cube while preserving all positive dot products. Their minimum is positive, so \(P_S\) contains a point with \(t>0\).
Maximize \(t\) over \(P_S\). The polytope is nonempty and compact, so the maximum exists and is positive. A linear objective on a nonempty bounded polytope attains its maximum at a vertex. Choose such a maximizing vertex \((u^*,t^*)\).
At this vertex, select \(d+1\) linearly independent active constraints. Their coefficient matrix \(B\) has integer entries of absolute value at most one. Writing \(D=|\det B|\), Hadamard’s inequality gives
\[ 1\le D\le(d+1)^{(d+1)/2}. \]
Cramer’s rule supplies integers \(N_j,N_t\) such that
\[ u_j^*=\frac{N_j}{D}, \qquad t^*=\frac{N_t}{D}. \]
The cube and margin bounds imply \(|N_j|\le D\) and \(0<N_t\le dD\).
Define the rational candidate position
\[ y^*=\frac{t^*}{d}u^*. \]
For every \(i\in S\), using \(x^i\cdot u^*\ge t^*\) and \(\|u^*\|_2^2\le d\), we obtain
\[ 2x^i\cdot y^*-\|y^*\|_2^2 \ge \frac{2(t^*)^2}{d} -\frac{(t^*)^2}{d^2}\|u^*\|_2^2 \ge \frac{(t^*)^2}{d} >0. \]
Hence \(y^*\) wins every type in \(S\), including under the prescribed strict tie convention.
Moreover,
\[ y_j^*=\frac{N_tN_j}{dD^2}. \]
The numerator and denominator have \(O(d\log(d+1))\) bits per coordinate. Thus the complete position uses \(O(d^2\log(d+1))\) bits.
Use the rational position from Section 2 as the certificate. A verifier computes, using exact rational arithmetic, whether
\[ 2x^i\cdot y>\sum_{j=1}^{d}y_j^2 \]
for each of the \(\tau\) types. It then sums precisely the masses of those satisfying this strict inequality and compares the sum with \(q\).
The certificate length is polynomial in \(d\), hence in the explicit input length \(L\). Arithmetic intermediates also have polynomial bit length: in particular, a common denominator for the input masses has bit length at most the sum of their denominator bit lengths. Verification therefore takes \(\operatorname{poly}(d,\tau,L)\) bit operations, with \(m=1\).
Together with Section 1, this proves \(\mathsf{NP}\)-completeness.
The rational-certificate proof also yields an explicit algorithm that returns a position whenever one exists.
In variables \((u,t)\in\mathbb R^{d+1}\), form the following \(\tau+2d+2\) hyperplanes:
\[ x^i\cdot u=t\quad(1\le i\le\tau),\qquad u_j=1,\ u_j=-1\quad(1\le j\le d),\qquad t=0,\ t=d. \]
Enumerate every choice of \(d+1\) hyperplanes. For each choice:
If no choice succeeds, answer no.
Every returned position passes the original voting test, so the algorithm is sound. For completeness, any yes-instance with \(q>0\) has the maximizing vertex constructed in Section 2. Its independent active constraints belong to the enumerated collection, and its associated position wins enough mass. Therefore some enumerated choice succeeds.
Each linear system and vote evaluation takes \(\operatorname{poly}(d,\tau,L)\) bit operations. The resulting bound, explicitly with \(m=1\), is
\[ \binom{\tau+2d+2}{d+1}\operatorname{poly}(d,\tau,L). \]
For fixed \(d\), this is
\[ O_d\!\left((\tau+1)^{d+1}\operatorname{poly}(L)\right), \]
and is polynomial in the support-based input length. For unrestricted \(d\), the dimension-dependent exponent does not give a polynomial-time algorithm.
⟨structured verdict parsed — rendered above⟩
The classification is correct in substance: the rational-mass problem is \(\mathsf{NP}\)-complete for unrestricted \(d\), with \(m=1\). The reduction, rational-certificate bound, and constructive enumeration algorithm all check out. There is one minor expositional omission in the claim about polynomial-time position construction under \(\mathsf{P}=\mathsf{NP}\).
The cited result matches the required source problem:
Thus the prover applies the supplied hardness theorem with the required hypotheses. No translation of the incumbent is needed that might alter the bipolar coordinates. These details are confirmed in the [cited paper](https://arxiv.org/html/2508.13841v1#S4.SS1).
The reduction is valid.
Each multiplicity \(c_i\) is a positive integer, and the multiplicities sum to \(n\). Consequently, the constructed masses \(\mu_i=c_i/n\) are positive rationals summing to one. The threshold \(q=k/n\) belongs to the permitted interval.
The displayed consolidation identity holds for every real position \(y\): all voters having the same position satisfy exactly the same strict distance inequality. Dividing the original vote count by \(n\) therefore preserves the threshold comparison in both directions.
The encoding and running-time claims also hold:
This establishes hardness for the exact support-based formulation in USER_TASK.
The distance expansion is correct:
\[ \|x^i-y\|_2<\|x^i\|_2 \quad\Longleftrightarrow\quad 2x^i\cdot y>\|y\|_2^2. \]
In particular, a won type has positive dot product with \(y\).
For \(q>0\), a winning set \(S\) must be nonempty. Its positive homogeneous inequalities are feasible, and scaling a feasible direction into the cube preserves their strict positivity. Because \(S\) is finite, the minimum of those positive dot products is positive.
The upper bound \(t\le d\) is compatible with this argument: inside the cube, every bipolar dot product is at most \(d\).
The resulting \(P_S\) is nonempty, closed, and bounded. The stated theorem that a linear objective on a nonempty bounded polytope attains its maximum at a vertex therefore applies. The maximum margin is strictly positive.
The vertex calculation is valid.
At a vertex in \(d+1\) variables, the active constraint normals span the ambient space, so selecting \(d+1\) independent active constraints is justified. Their coefficients are integers with absolute value at most one; their right-hand sides are also integers.
For their nonsingular coefficient matrix \(B\), the determinant is a nonzero integer. Hadamard’s inequality yields precisely the stated bound:
\[ 1\le |\det B|\le(d+1)^{(d+1)/2}. \]
Cramer’s rule gives common-denominator representations using \(D=|\det B|\); any determinant sign is absorbed into the numerators. The bounds on \(N_j\) and \(N_t\) follow directly from the cube and margin bounds.
For the proposed position \(y^*=(t^*/d)u^*\), both inequalities in the displayed margin calculation have the correct direction. The final lower bound is strictly positive because \(d\ge1\) and \(t^*>0\). Thus every type in \(S\) is strictly won, respecting the incumbent-favoring tie convention.
Finally, the expression
\[ y_j^*=\frac{N_tN_j}{dD^2} \]
has numerator and denominator bit lengths bounded by \(O(d\log(d+1))\). The total certificate bound \(O(d^2\log(d+1))\) is correct. Reducing the fractions is unnecessary for this bound.
The proposed verifier correctly tests the original voting condition using exact rational arithmetic. It then sums precisely the masses of the won types and compares that sum with \(q\).
Both the coordinate arithmetic and the mass arithmetic have polynomial bit complexity. The stated common-denominator bound for the input masses is valid even if their denominators are mutually coprime.
Because the input explicitly contains at least one vector with \(d\) coordinates, \(d\) is bounded by the explicit input length. Hence the certificate bound is polynomial in \(L\).
The case \(q=0\) is handled correctly by returning the origin. Together with the reduction, this proves the claimed \(\mathsf{NP}\)-completeness.
The enumeration algorithm is sound and complete.
Every returned position is checked against the original strict distance test, so passing the auxiliary cube and margin checks cannot create a false positive.
For completeness, the maximizing vertex associated with any winning set has an independent active constraint set among the enumerated hyperplanes. Solving that selection recovers the vertex used in the certificate argument. Its associated position therefore passes the mass threshold.
The algorithm does not need to identify the winning set beforehand or impose all of its inequalities on every enumerated solution: the final exact voting test provides soundness.
Singular selections can be discarded without losing the independent selection needed for completeness. Degenerate vertices and repeated hyperplanes likewise cause no failure.
The number of selections and the stated running-time bound are correct:
\[ \binom{\tau+2d+2}{d+1}\operatorname{poly}(d,\tau,L). \]
For fixed \(d\), the stated polynomial bound follows. The initial \(q=0\) branch applies before this enumeration.
Minor — Classification paragraph, “Thus a polynomial-time algorithm for decision and position construction exists if and only if…”
The implication from \(\mathsf{P}=\mathsf{NP}\) to polynomial-time position construction is asserted without stating the search-to-decision principle being used. Decision membership alone is not an explicit construction procedure.
This is an expositional omission, not a substantive obstacle: the write-up already establishes polynomially bounded certificates and polynomial-time verification.
Minimum clarification: State or cite the standard polynomial-witness search consequence of \(\mathsf{P}=\mathsf{NP}\), and identify the rational-position certificate as satisfying its hypotheses.
No major issue was found. The unrestricted-dimension hardness classification and the explicit fixed-dimension construction stand.
⟨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.