Answer: \(\mathrm{NP\text{-}hard}\), indeed \(\mathrm{NP\text{-}complete}\), when \(d\) is part of the input
Theorem 8 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateby a reduction from 3-SAT; the proof is provided in the full version of the paper. Just like for hypercubes, Euc-SCORE is fixed-parameter tractable with respect to the number of agents.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational types \(v^1,\ldots,v^\tau\in\mathbb{Q}^d\), rational masses \(\mu_j>0\) with \(\sum_j\mu_j=1\), and a rational threshold \(\eta\in[0,1]\), with status quo \(0\), decide whether there exists \(x\in\mathbb{R}^d\setminus\{0\}\) such that \(\sum_{j:\,\lVert v^j-x\rVert_2<\lVert v^j\rVert_2}\mu_j\ge\eta\).
Given \(d\in\mathbb{N}\), rational type vectors \(v^1,\ldots,v^\tau\in\mathbb{Q}^d\), rational masses \(\mu_j>0\) with \(\sum_{j=1}^{\tau}\mu_j=1\), and \(\eta\in\mathbb{Q}\cap[0,1]\), the status quo is \(0\). A type \(v^j\) approves \(x\in\mathbb{R}^d\setminus\{0\}\) iff \(\lVert v^j-x\rVert_2<\lVert v^j\rVert_2\). Its support is the total mass of approving types.
Target. Is deciding whether some \(x\in\mathbb{R}^d\setminus\{0\}\) has support at least \(\eta\) solvable in polynomial time, or is it NP-hard?
Nearest known results. For a finite list of rational Euclidean agents and an integer threshold, deciding whether a non-status-quo proposal is approved by at least that many agents is NP-complete (Euc-SCORE, Theorem 8 of Elkind, Ghosh, and Goldberg, 2022).
Under the standard interpretation that \(d\) is part of the input, the problem is \(\mathrm{NP}\)-complete, and therefore \(\mathrm{NP}\)-hard.
An Euc-SCORE instance consists of rational points \(a^1,\ldots,a^n\in\mathbb{Q}^d\) and a positive integer \(k\). It asks whether some \(x\in\mathbb{R}^d\setminus\{0\}\) satisfies
\[ \lVert a^i-x\rVert_2<\lVert a^i\rVert_2 \]
for at least \(k\) agents. This problem is \(\mathrm{NP}\)-complete by [Elkind, Ghosh, and Goldberg, Theorem 8](https://ojs.aaai.org/index.php/AAAI/article/download/20428/20187).
For an instance with \(1\leq k\leq n\), construct the weighted instance
\[ \tau=n,\qquad v^i=a^i,\qquad \mu_i=\frac1n,\qquad \eta=\frac{k}{n}. \]
These data satisfy \(\mu_i>0\) and
\[ \sum_{i=1}^n\mu_i=1. \]
For every nonzero proposal \(x\), let
\[ A(x)=\left\{i\in[n]: \lVert a^i-x\rVert_2<\lVert a^i\rVert_2 \right\}. \]
Its support in the constructed instance is exactly
\[ \sum_{i\in A(x)}\mu_i =\frac{|A(x)|}{n}. \]
Consequently,
\[ \operatorname{support}(x)\geq\eta \quad\Longleftrightarrow\quad \frac{|A(x)|}{n}\geq\frac{k}{n} \quad\Longleftrightarrow\quad |A(x)|\geq k. \]
Thus the Euc-SCORE instance is a yes-instance if and only if the constructed weighted instance is a yes-instance.
The construction is polynomial-time: the fractions \(1/n\) and \(k/n\) require only \(O(\log n+\log k)\) bits. If \(k>n\), the source instance is automatically a no-instance and can be mapped to the fixed no-instance \(d=1\), \(v^1=0\), \(\mu_1=1\), and \(\eta=1\).
This proves \(\mathrm{NP}\)-hardness, already for uniform masses.
We prove the stronger upper bound. For \(v,x\in\mathbb{R}^d\),
\[ \lVert v-x\rVert_2^2<\lVert v\rVert_2^2 \quad\Longleftrightarrow\quad 2\langle v,x\rangle>\lVert x\rVert_2^2. \]
For nonzero \(x\), define
\[ y=\frac{2x}{\lVert x\rVert_2^2}. \]
Then
\[ \lVert v-x\rVert_2<\lVert v\rVert_2 \quad\Longleftrightarrow\quad \langle v,y\rangle>1. \]
Conversely, for every nonzero \(y\), setting
\[ x=\frac{2y}{\lVert y\rVert_2^2} \]
gives the same equivalence.
Assume \(\eta>0\). The instance is therefore a yes-instance if and only if there is a nonempty subset \(S\subseteq[\tau]\) such that
\[ \sum_{j\in S}\mu_j\geq\eta \]
and the rational linear system
\[ \langle v^j,y\rangle\geq1 \qquad\text{for every }j\in S \]
is feasible.
Indeed, strict feasibility implies weak feasibility. Conversely, if \(y\) satisfies the weak system, then \(2y\) satisfies
\[ \langle v^j,2y\rangle\geq2>1 \]
for every \(j\in S\), and hence determines a nonzero proposal approved by every type in \(S\).
An \(\mathrm{NP}\) verifier guesses \(S\), computes its rational mass exactly, and tests the displayed rational linear system by polynomial-time linear programming. The case \(\eta=0\) is trivially a yes-instance when \(d\geq1\).
Hence the problem belongs to \(\mathrm{NP}\).
The reduction and the upper bound together prove that the problem is \(\mathrm{NP}\)-complete when \(d\) is part of the input. Thus no polynomial-time algorithm exists unless \(\mathrm{P}=\mathrm{NP}\).
This does not assert hardness for a fixed constant \(d\). For fixed \(d\), the hyperplanes
\[ \left\{y:\langle v^j,y\rangle=1\right\} \]
have only polynomially many arrangement faces, on each of which the approval set is constant. Enumerating these faces and maximizing their total rational mass gives a polynomial-time algorithm, consistently with Proposition 10 of the cited paper.
⟨structured verdict parsed — rendered above⟩
The prover correctly establishes \(\mathrm{NP}\)-hardness, and the \(\mathrm{NP}\)-membership argument is sound. The cited source defines Euclidean deliberation with rational agent coordinates, status quo \(0\), and unrestricted proposal space \(\mathbb R^d\), and states that Euc-SCORE is \(\mathrm{NP}\)-complete in Theorem 8 ([official paper](https://ojs.aaai.org/index.php/AAAI/article/download/20428/20187)).
There is only a minor edge-case ambiguity concerning whether \(\mathbb N\) includes \(0\).
The description of Euc-SCORE matches the cited result:
Thus using Euc-SCORE as the reduction source is justified.
For \(1\leq k\leq n\), the assignment
\[ \tau=n,\qquad v^i=a^i,\qquad \mu_i=\frac1n,\qquad \eta=\frac{k}{n} \]
produces a valid target instance:
For every proposal \(x\), its support is exactly
\[ \sum_{i\in A(x)}\frac1n=\frac{|A(x)|}{n}. \]
Because \(n>0\),
\[ \frac{|A(x)|}{n}\geq\frac{k}{n} \]
is equivalent to \(|A(x)|\geq k\). Hence the reduction preserves yes- and no-instances exactly.
The stated encoding bound is adequate. Although there are \(n\) copies of \(1/n\), the total output length remains polynomial.
Such a source instance is necessarily negative. The proposed fixed target instance with \(d=1\), \(v^1=0\), \(\mu_1=1\), and \(\eta=1\) is also negative: no nonzero \(x\) can satisfy
\[ \lVert -x\rVert_2<0. \]
The fact that a zero type may fail the ancillary convention in the cited deliberation model is irrelevant: zero types are explicitly permitted by the target problem.
Therefore the \(\mathrm{NP}\)-hardness reduction is correct.
Squaring the nonnegative norms gives
\[ \lVert v-x\rVert_2^2<\lVert v\rVert_2^2 \]
if and only if
\[ \lVert x\rVert_2^2-2\langle v,x\rangle<0, \]
equivalently,
\[ 2\langle v,x\rangle>\lVert x\rVert_2^2. \]
For nonzero \(x\), defining
\[ y=\frac{2x}{\lVert x\rVert_2^2} \]
therefore yields precisely
\[ \langle v,y\rangle>1. \]
The inverse formula
\[ x=\frac{2y}{\lVert y\rVert_2^2} \]
is valid for every nonzero \(y\), and substituting it recovers the same equivalence. No irrational certificate is required.
For \(\eta>0\), any subset \(S\) whose mass is at least \(\eta\) is nonempty because every mass is positive.
If a proposal exists, its transformed vector \(y\) satisfies the strict system and hence the weak system
\[ \langle v^j,y\rangle\geq1 \qquad(j\in S). \]
Conversely, if the weak system is feasible, nonemptiness of \(S\) ensures \(y\neq0\). Scaling to \(2y\) gives
\[ \langle v^j,2y\rangle\geq2>1, \]
so the inverse transformation produces a nonzero proposal approved by all types in \(S\). Thus the claimed equivalence is correct.
A subset \(S\subseteq[\tau]\) has polynomial description length. Its rational mass can be added and compared with \(\eta\) in polynomial time, with polynomially bounded intermediate bit length.
Feasibility of the displayed rational weak linear system is decidable by polynomial-time linear programming. Since deterministic polynomial-time computation is permitted after guessing the certificate, this establishes membership in \(\mathrm{NP}\).
For \(d\geq1\), the assertion is correct: a nonzero proposal exists and every support value is nonnegative, so threshold \(0\) is always attained.
There is a minor convention-dependent omission. If \(\mathbb N\) includes \(0\), then \(d=0\) gives
\[ \mathbb R^0\setminus\{0\}=\varnothing, \]
so even an instance with \(\eta=0\) is negative. The write-up should either state that dimensions are positive integers or explicitly handle \(d=0\). This does not affect the complexity classification.
The aside is consistent with Proposition 10 of the cited paper. For fixed \(d\), the arrangement of the rational hyperplanes
\[ \langle v^j,y\rangle=1 \]
has polynomially many faces, and the truth value of each strict inequality is constant on every relatively open face. Computing the total rational mass of each resulting approval pattern therefore extends the unweighted fixed-dimensional algorithm to weighted types.
The reduction and upper bound substantively prove \(\mathrm{NP}\)-completeness when the dimension is part of the input. Only the \(d=0\) convention requires clarification.
⟨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.