Answer: Polynomial-time solvable by rational linear programming; therefore not \(\mathsf{NP}\)-hard unless \(\mathsf{P}=\mathsf{NP}\).
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateEI is NP-hard, as well as W[2]-hard when parame- terised by the solution size, even if the input graph is bipartite and has bounded diameters.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational society masses \( \mu_t \), initial labels \(b_t \in \{0,1\}\), a rational row-stochastic interaction matrix \(A=(a_{ut})\), and a budget \(K\), decide whether there exist \(p_t \in [0,1]\) such that \( \sum_t a_{ut}p_t \le \frac{1}{2} \) for every \(u\), and \( \sum_t \mu_t |p_t-b_t| \le K \), with \( \sum_t \mu_t b_t < \frac{1}{2} \).
Definitions.
Let \(T\) be finite, \(\mu\in\mathbb{Q}_{\ge 0}^{T}\) satisfy \(\sum_{t\in T}\mu_t=1\), let \(f_t\in\{0,1\}\) satisfy \(\sum_{t\in T}\mu_t f_t<1/2\), and let \(W\in\mathbb{Q}_{\ge 0}^{T\times T}\) be symmetric. Choose \(y_{t,0},y_{t,1}\ge0\) with \(y_{t,0}+y_{t,1}=\mu_t\).
A choice is feasible when \(\sum_{u\in T}W_{tu}y_{u,1}\le\sum_{u\in T}W_{tu}y_{u,0}\) for every \(t\in T\), and has cost \(\sum_{t:f_t=0}y_{t,1}+\sum_{t:f_t=1}y_{t,0}\). Its decision form additionally asks whether cost is at most a rational bound \(B\).
Target.
Is this rational-mass Eliminating Majority Illusion problem NP-hard, or does it admit a polynomial-time algorithm?
Nearest known results.
The corresponding finite-agent problem with indivisible agents and an adjacency-matrix contact structure is NP-hard, and is \(W[2]\)-hard parameterized by the number of relabelled agents, even on bipartite graphs of bounded diameter.
That discrete hardness result does not address divisible type masses.
The rational-mass Eliminating Majority Illusion decision problem is polynomial-time solvable under the standard binary encoding of rational numbers. More precisely, it reduces directly to rational linear-program feasibility.
Consequently, it is not \(\mathsf{NP}\)-hard under polynomial-time many-one reductions unless \(\mathsf{P}=\mathsf{NP}\).
For every \(t\in T\), define
\[ x_t:=y_{t,1}. \]
The equality \(y_{t,0}+y_{t,1}=\mu_t\) then forces
\[ y_{t,0}=\mu_t-x_t. \]
Thus nonnegativity of \(y_{t,0}\) and \(y_{t,1}\) is equivalent to
\[ 0\leq x_t\leq \mu_t. \]
This correspondence between choices \((y_{t,0},y_{t,1})_{t\in T}\) and vectors \(x\) satisfying these box constraints is bijective.
For each \(t\in T\), the majority constraint becomes
\[ \sum_{u\in T}W_{tu}x_u \leq \sum_{u\in T}W_{tu}(\mu_u-x_u). \]
Moving the terms involving \(x\) to the left gives the equivalent inequality
\[ 2\sum_{u\in T}W_{tu}x_u \leq \sum_{u\in T}W_{tu}\mu_u. \]
Define the rational constant
\[ b_t:=\sum_{u\in T}W_{tu}\mu_u. \]
The feasibility conditions are therefore exactly
\[ 0\leq x_t\leq\mu_t \quad\text{for every }t\in T, \]
together with
\[ 2\sum_{u\in T}W_{tu}x_u\leq b_t \quad\text{for every }t\in T. \]
Let
\[ F:=\{t\in T:f_t=1\}, \qquad p:=\sum_{t\in F}\mu_t. \]
The hypothesis states that \(p<1/2\). For the vector \(x\), the cost is
\[ \begin{aligned} C(x) &= \sum_{t:f_t=0}x_t + \sum_{t:f_t=1}(\mu_t-x_t)\\ &= p+\sum_{t\in T}(1-2f_t)x_t. \end{aligned} \]
Hence the bound \(C(x)\leq B\) is precisely the linear inequality
\[ \sum_{t\in T}(1-2f_t)x_t\leq B-p. \]
The decision problem is thus equivalent to feasibility of the following rational linear system:
\[ 0\leq x_t\leq\mu_t \quad\text{for every }t\in T, \]
\[ 2\sum_{u\in T}W_{tu}x_u\leq b_t \quad\text{for every }t\in T, \]
and
\[ \sum_{t\in T}(1-2f_t)x_t\leq B-p. \]
Suppose the original instance admits a choice of cost at most \(B\). Setting \(x_t=y_{t,1}\) gives the box constraints, the transformed majority inequalities, and the transformed cost inequality. Hence the linear system is feasible.
Conversely, suppose \(x\) satisfies the displayed linear system. Define
\[ y_{t,1}:=x_t, \qquad y_{t,0}:=\mu_t-x_t. \]
The box constraints imply that these values are nonnegative and sum to \(\mu_t\). Reversing the algebra in Sections 2 and 3 shows that all original majority constraints hold and that the cost is at most \(B\). Thus the original instance is feasible.
Therefore the reduction is exact in both directions.
Let \(L\) denote the binary encoding length of the input. The constructed linear program has \(|T|\) variables and at most \(3|T|+1\) inequalities.
All coefficients are rational. Each \(b_t\) is a sum of \(|T|\) products of input rationals, while \(p\) is a sum of input rationals. Exact rational multiplication and addition produce numerators and denominators whose bit lengths are polynomial in \(L\). Thus the entire transformed linear program has encoding length polynomial in \(L\).
Feasibility of an explicitly encoded rational linear program can be decided in time polynomial in its number of variables, number of inequalities, and coefficient bit length, for example by the ellipsoid method. Applying that theorem to the constructed system gives a polynomial-time decision algorithm. It also yields an exact rational feasible solution whenever one exists.
Importantly, this runtime is polynomial in the binary encoding length of the masses and does not expand the masses into a population whose size is a common denominator.
Nonnegativity of \(W\) gives a more specific packing formulation. Given any feasible \(x\), define
\[ x'_t= \begin{cases} x_t,&f_t=1,\\ 0,&f_t=0. \end{cases} \]
Because \(W_{tu}\geq0\), replacing \(x\) by \(x'\) can only decrease every left-hand side \(2\sum_u W_{tu}x_u\). It therefore preserves feasibility. It also decreases the cost by exactly \(\sum_{t:f_t=0}x_t\).
Consequently, some optimal solution satisfies \(x_t=0\) whenever \(f_t=0\). The optimization problem can equivalently be written as
\[ \max \sum_{t\in F}x_t \]
subject to
\[ 0\leq x_t\leq\mu_t \quad\text{for }t\in F, \]
and
\[ 2\sum_{u\in F}W_{tu}x_u \leq \sum_{u\in T}W_{tu}\mu_u \quad\text{for every }t\in T. \]
If the optimum of this packing linear program is \(M\), then the minimum relabelling cost is exactly \(p-M\).
This also explains why the known indivisible-agent hardness does not transfer: the indivisible problem contains binary relabelling decisions, whereas the rational-mass formulation permits every \(x_t\) in the full interval \([0,\mu_t]\), leaving an ordinary linear program.
The rational-mass problem admits an exact polynomial-time algorithm. Symmetry of \(W\), normalization \(\sum_t\mu_t=1\), and the hypothesis \(p<1/2\) are not needed for polynomial-time solvability; they concern the intended majority-illusion interpretation. Nonnegativity of \(W\) is needed only for the additional packing simplification, not for the basic linear-program reduction.
⟨structured verdict parsed — rendered above⟩
The prover correctly resolves the target. The rational-mass decision problem is exactly representable as feasibility of a polynomial-size rational linear program, so it is solvable in polynomial time under binary encoding.
No unjustified nontrivial step, false assertion, missing hypothesis, or relevant edge-case failure was found.
Setting \(x_t=y_{t,1}\) forces \(y_{t,0}=\mu_t-x_t\). The original nonnegativity conditions are equivalent to \(0\le x_t\le\mu_t\). The claimed bijection is exact, including when \(\mu_t=0\).
Substitution gives
\[ \sum_u W_{tu}x_u\le \sum_u W_{tu}(\mu_u-x_u), \]
which is algebraically equivalent to
\[ 2\sum_u W_{tu}x_u\le\sum_u W_{tu}\mu_u. \]
This transformation is reversible and does not rely on dividing by possibly zero quantities.
With \(F=\{t:f_t=1\}\) and \(p=\sum_{t\in F}\mu_t\), the calculation
\[ C(x)=p+\sum_t(1-2f_t)x_t \]
is correct: the coefficient is \(1\) when \(f_t=0\) and \(-1\) when \(f_t=1\). Therefore \(C(x)\le B\) is exactly the stated linear inequality.
Both directions of the reduction follow directly from the bijective substitution. The box, majority, and cost constraints are all preserved exactly. Thus there is no relaxation or integrality assumption hidden in the LP formulation.
The LP has \(|T|\) variables and \(3|T|+1\) scalar inequalities when each two-sided box constraint is counted as two inequalities. Sums and products of explicitly encoded rationals have polynomially bounded output bit length relative to the total input length. Consequently, the constructed LP has polynomial encoding length and can be constructed in polynomial time.
Polynomial-time feasibility of explicitly encoded rational linear systems is a standard theorem. The presented system satisfies its hypotheses. Hence the claimed polynomial-time decision algorithm follows.
Setting \(x_t=0\) for \(f_t=0\) preserves the box constraints. Since \(W\ge0\), it weakly decreases every majority-constraint left-hand side. It decreases the cost by exactly \(\sum_{t:f_t=0}x_t\). Therefore an optimum can be chosen with those coordinates zero, and minimizing cost is equivalent to maximizing \(\sum_{t\in F}x_t\). The identity \(p-M\) for the minimum cost is correct.
Since the decision problem lies in \(\mathsf P\), it cannot be \(\mathsf{NP}\)-hard under polynomial-time many-one reductions unless \(\mathsf P=\mathsf{NP}\). The observations about which original assumptions are unnecessary for the basic LP reduction are also correct.
⟨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.