Answer: \(\mathrm{NP}\text{-complete}\), already for fixed \(q=3/4\)
Theorem 1 — class: hardness
Given \(\tau\) exposure roles with positive rational masses \(\mu_i\) summing to \(1\), a symmetric nonnegative rational interaction matrix \(a_{ij}\), and rational \(q\in(1/2,1]\), does there exist a red mass \(x_i\in[0,\mu_i]\) for each role such that \(\sum_i(\mu_i-2x_i)>0\) and \(\sum_{i:\,\sum_j a_{ij}(2x_j-\mu_j)>0}\mu_i\ge q\)?
A society is given by its support: a list of \(\tau\ge1\) exposure types with positive binary-rational masses \(\mu_i\), where \(\sum_i\mu_i=1\); \(\tau\) is the support size, not the number of possible types. There are \(m=2\) labels, red and blue.
The input also contains a symmetric matrix \(A=(a_{ij})\in\mathbb{Q}_{\ge0}^{\tau\times\tau}\) and a binary-rational threshold \(q\in(1/2,1]\). Let \(L\) be the total input bit length. Coefficients are exposure weights: \(a_{ij}\mu_j\) is the exposure of type \(i\) to type \(j\). Diagonal entries allow exposure to other members of the same atomless type.
A labeling selects real red masses \(x_i\in[0,\mu_i]\), with blue masses \(\mu_i-x_i\). Blue must be the strict global majority: \(\sum_i(\mu_i-2x_i)>0\).
Every member of type \(i\), regardless of its own label, is under illusion exactly when \(\sum_j a_{ij}(2x_j-\mu_j)>0\). Ties and zero exposure do not count as illusion. The decision problem asks whether a labeling exists with \(\sum_{i:\,\sum_j a_{ij}(2x_j-\mu_j)>0}\mu_i\ge q\).
Is this continuous majority-illusion decision problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite agents on simple undirected graphs, existence of a binary labeling inducing illusion in at least a \(q\)-fraction is NP-complete for every fixed rational \(q\in(1/2,1]\), even on bipartite graphs ([source](https://doi.org/10.1613/jair.1.17741)). Later discrete work establishes W[1]-hardness parameterized by treewidth ([source](https://arxiv.org/html/2606.04260v1)).
No result settling the exact continuous decision problem above was located in the literature search.
Result. The decision problem is \(\mathrm{NP}\)-complete, already for the fixed threshold \(q=3/4\). This holds with positive dyadic masses and a symmetric rational matrix whose entries all lie in \([1,3]\).
The endpoint \(q=1\), however, is polynomial-time solvable. Thus the continuous problem has a different endpoint behavior from the discrete problem cited in the question.
1. Homogeneity removes the mass bounds.
Define \(y_i=2x_i-\mu_i\). Then a valid labeling satisfies
\(\displaystyle -\mu_i\le y_i\le\mu_i,\qquad \mathbf1^{\mathsf T}y<0,\)
and type \(i\) is under illusion exactly when \((Ay)_i>0\).
For any subset \(S\) of types, the following are equivalent:
Only the reverse implication needs proof. Given such an unrestricted vector, set
\(\displaystyle \lambda=\min_i\frac{\mu_i}{1+|y_i|}>0.\)
Then \(|\lambda y_i|<\mu_i\) for every \(i\). Positive scaling preserves all the strict inequalities, so
\(\displaystyle x_i=\frac{\mu_i+\lambda y_i}{2}\)
is a valid labeling with the required illusion types and strict blue majority.
Consequently, masses determine the objective weights but do not restrict which subsets can simultaneously be illuded.
2. Membership in \(\mathrm{NP}\), and the endpoint \(q=1\).
A certificate is a subset \(S\) with \(\sum_{i\in S}\mu_i\ge q\). By the preceding observation, its feasibility is equivalent to feasibility of the rational linear system
\(\displaystyle (Ay)_i\ge1\quad(i\in S),\qquad \mathbf1^{\mathsf T}y\le-1.\)
Indeed, a vector satisfying the strict inequalities can be scaled upward until every required positive margin, including \(-\mathbf1^{\mathsf T}y\), is at least \(1\). Conversely, this linear system gives the strict inequalities, and the preceding scaling argument supplies a valid labeling.
Rational linear feasibility is decidable in time polynomial in the number of variables, constraints, and coefficient bit lengths. Thus a deterministic polynomial-time verifier can check the certificate \(S\), proving membership in \(\mathrm{NP}\).
When \(q=1\), positivity of every mass forces every type to be illuded. Hence one simply tests
\(\displaystyle Ay\ge\mathbf1,\qquad \mathbf1^{\mathsf T}y\le-1.\)
This proves polynomial-time solvability at that endpoint.
3. Source problem and matrix construction.
We reduce from Independent Set: given a simple undirected graph \(G=(V,E)\) and an integer \(k\), decide whether an independent set of size at least \(k\) exists. Its \(\mathrm{NP}\)-completeness follows from the classical Clique theorem by graph complementation. [Karp’s original theorem](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
Write \(n=|V|\) and \(r=|E|\). We may restrict to \(r\ge1\) and \(1\le k\le n\): excluded instances are decidable immediately and can be replaced by fixed yes or no instances consisting of a single edge.
Create \(N=n+r+2\) types:
Let \(e_v\) denote the standard basis vector in \(\mathbb R^n\). Construct an integer matrix \(F\in\mathbb Z^{N\times n}\) with rows
\(\displaystyle F_v=e_v^{\mathsf T},\qquad F_{\{v,w\}}=-e_v^{\mathsf T}-e_w^{\mathsf T}.\)
Set \(F_b\) equal to the negative sum of all vertex and edge rows, and set \(F_z=0\). Therefore
\(\displaystyle F^{\mathsf T}\mathbf1=0.\)
The vertex rows form an identity matrix, so \(F\) has full column rank. In particular, \(H=F^{\mathsf T}F\) is positive definite. Define
\(\displaystyle P=FH^{-1}F^{\mathsf T},\qquad J=\mathbf1\mathbf1^{\mathsf T},\qquad A=2J+P.\)
Here \(\mathbf1\in\mathbb R^N\). Direct multiplication gives
\(\displaystyle P^{\mathsf T}=P,\qquad P^2=P,\qquad PF=F,\qquad P\mathbf1=0.\)
Thus \(P\) is the orthogonal projection onto the column space of \(F\). For standard basis vectors in \(\mathbb R^N\),
\(\displaystyle |P_{ij}|=|\langle Pe_i,Pe_j\rangle|\le\|Pe_i\|\,\|Pe_j\|\le1.\)
Consequently, \(A\) is symmetric and rational, with
\(\displaystyle 1\le a_{ij}\le3,\qquad A\mathbf1=2N\mathbf1.\)
This checks the required symmetry and nonnegativity, including the diagonal entries.
For any vector \(y\) with strict blue majority, define
\(\displaystyle t=-2\mathbf1^{\mathsf T}y>0,\qquad u=H^{-1}F^{\mathsf T}y.\)
Then
\(\displaystyle Ay=Fu-t\mathbf1.\)
In particular,
\(\displaystyle (Ay)_v=u_v-t,\qquad (Ay)_{\{v,w\}}=-u_v-u_w-t,\qquad (Ay)_z=-t<0.\)
The dummy type can therefore never be illuded under a strict blue majority.
4. Dyadic masses and the fixed threshold.
Enumerate the edges as \(e_1,\ldots,e_r\). Let \(d\) be the smallest power of two with \(d\ge r\). Choose
\(\displaystyle h=\left\lceil\log_2\bigl(8d(n+1)\bigr)\right\rceil,\qquad \varepsilon=2^{-h},\qquad \beta=\frac34-k\varepsilon.\)
Assign masses
\(\displaystyle \mu_v=\varepsilon\quad(v\in V),\)
\(\displaystyle \mu_{e_1}=\frac{(d-r+1)\beta}{d},\qquad \mu_{e_j}=\frac{\beta}{d}\quad(2\le j\le r),\)
\(\displaystyle \mu_b=\frac{\varepsilon}{2},\qquad \mu_z=1-\beta-\left(n+\frac12\right)\varepsilon.\)
Set \(q=3/4\).
Every mass is dyadic. The edge masses sum to \(\beta\), so all masses together sum to \(1\). To check positivity and the necessary weight separation, observe that
\(\displaystyle \left(n+\frac12\right)\varepsilon<\frac1{8d}\le\frac18,\qquad \beta\ge\frac34-n\varepsilon>\frac58.\)
Thus \(\mu_z>1/8\), and every other mass is positive. Moreover, every edge mass satisfies
\(\displaystyle \mu_e\ge\frac{\beta}{d}>\frac5{8d}>\left(n+\frac12\right)\varepsilon.\)
The rightmost quantity is the total mass of all vertex types and the balancing type.
5. Soundness: a successful labeling yields an independent set.
Suppose a valid labeling attains illusion mass at least \(3/4\).
First, every edge type must be illuded. Otherwise, since the dummy type is never illuded, the total illusion mass would be at most
\(\displaystyle \beta-\frac{\beta}{d}+\left(n+\frac12\right)\varepsilon<\beta<\frac34,\)
a contradiction.
Let \(I\) be the set of illuded vertex types. Using the representation \(Ay=Fu-t\mathbf1\), each \(v\in I\) satisfies \(u_v>t\). Every edge \(\{v,w\}\) satisfies
\(\displaystyle u_v+u_w<-t.\)
If both endpoints belonged to \(I\), their sum would exceed \(2t>0\), contradicting this edge inequality. Therefore \(I\) is an independent set.
Finally, if \(|I|\le k-1\), even counting the balancing type as illuded would give total illusion mass at most
\(\displaystyle \beta+(k-1)\varepsilon+\frac{\varepsilon}{2}=\frac34-\frac{\varepsilon}{2}<\frac34.\)
Hence \(|I|\ge k\).
6. Completeness: an independent set yields a successful labeling.
Conversely, suppose \(I\subseteq V\) is an independent set with \(|I|\ge k\). Define
\(\displaystyle u_v=\begin{cases}1,&v\in I,\\-2,&v\notin I.\end{cases}\)
Every edge has at most one endpoint in \(I\), so its coordinate in \(Fu\) is either \(1\) or \(4\). Every vertex coordinate belonging to \(I\) equals \(1\).
Set
\(\displaystyle y^{(0)}=Fu-\frac1{4N}\mathbf1.\)
Because \(F^{\mathsf T}\mathbf1=0\), \(PF=F\), and \(P\mathbf1=0\), we obtain
\(\displaystyle \mathbf1^{\mathsf T}y^{(0)}=-\frac14,\qquad Ay^{(0)}=Fu-\frac12\mathbf1.\)
Thus every edge coordinate and every vertex coordinate in \(I\) is strictly positive in \(Ay^{(0)}\). By Section 1, positive scaling converts \(y^{(0)}\) into a valid labeling while preserving these inequalities and the strict blue majority.
Its illusion mass is at least
\(\displaystyle \beta+|I|\varepsilon\ge\beta+k\varepsilon=\frac34.\)
This proves the reverse implication.
7. Encoding size and conclusion.
The construction has \(\tau=N=n+r+2\) types. All masses have polynomial bit length because \(d\) is a power of two with \(d<2r\), and \(h\) is logarithmic in \(d(n+1)\).
For the matrix, the balancing row has coordinate \(\deg_G(v)-1\), so the integer entries of \(F\), and hence of \(H=F^{\mathsf T}F\), have polynomially bounded magnitude. Hadamard’s determinant bound shows that the determinant and cofactors of \(H\) have polynomial bit length. Therefore \(H^{-1}\), \(P\), and \(A\) have polynomial bit length and can be computed by exact rational linear algebra in polynomial time.
We have established a polynomial-time many-one reduction satisfying
\(\displaystyle G\text{ has an independent set of size at least }k\quad\Longleftrightarrow\quad\text{the constructed society admits illusion mass at least }3/4.\)
Together with membership in \(\mathrm{NP}\), this resolves the stated decision problem as \(\mathrm{NP}\)-complete. A polynomial-time algorithm in \(m,\tau,L\) would therefore imply \(\mathrm P=\mathrm{NP}\), already with \(m=2\).
⟨structured verdict parsed — rendered above⟩
The reduction is sound in substance and establishes \(\mathrm{NP}\)-completeness at the fixed threshold \(q=3/4\). The separate polynomial-time result for \(q=1\) is also correct. I found no false step or substantive gap. There is one minor omission under the requested standard that cited theorems be stated precisely: the encoding argument invokes Hadamard’s bound without stating it.
The substitution \(y_i=2x_i-\mu_i\) correctly converts the labeling constraints into \(-\mu_i\le y_i\le\mu_i\), the strict blue majority into \(\mathbf1^{\mathsf T}y<0\), and illusion into \((Ay)_i>0\).
The equivalence for any subset \(S\) is valid. In the reverse direction, positivity of all masses and finiteness of the support ensure that the proposed \(\lambda\) is positive. For every coordinate,
\(\lambda|y_i|\le\mu_i|y_i|/(1+|y_i|)<\mu_i\).
Thus the scaled vector satisfies the box constraints, and positive scaling preserves every required strict inequality.
This argument establishes exactly the claimed separation: the masses affect which illusion subsets meet the objective threshold, but they do not affect simultaneous feasibility of a specified subset.
The certificate \(S\) requires only polynomially many bits. Its mass can be summed and compared with \(q\) using exact rational arithmetic in polynomial time.
The passage from strict inequalities to margins of at least \(1\) is valid. There are finitely many required positive margins, including the strict majority margin; their minimum is positive. Consequently, a common positive scaling suffices.
The resulting rational linear feasibility problem has \(\tau\) variables, at most \(\tau+1\) constraints, and coefficient bit length polynomial in the input length. The stated polynomial-time rational linear feasibility theorem therefore applies. A verifier may solve that feasibility problem directly; a numerical labeling need not be included in the certificate.
Conversely, an accepted subset yields a valid labeling by Section 1, and additional illuded types cannot decrease its illusion mass. Membership in \(\mathrm{NP}\) follows.
Because every mass is positive and the masses sum to \(1\), achieving illusion mass at least \(1\) requires every type to be illuded. The all-types linear system given in the output is therefore equivalent to the endpoint decision problem.
The argument preserves strictness through the margin normalization. It also covers support size \(\tau=1\) and matrices with zero entries: the feasibility test handles these cases without an additional assumption.
Independent Set on simple undirected graphs is an appropriate \(\mathrm{NP}\)-complete source problem. Complementation preserves the vertex set and converts cliques into independent sets with the same cardinality. The cited [Karp paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf) supplies the classical Clique completeness result.
Restricting to \(r\ge1\) and \(1\le k\le n\) is legitimate. The excluded cases can be decided immediately, and a single-edge graph supplies both a fixed yes-instance and a fixed no-instance through the choice of threshold \(k\). No hardness assumption is lost.
All the asserted identities check out:
Therefore \(A=2J+P\) is rational, symmetric, and entrywise in \([1,3]\). Its diagonal entries satisfy the input conditions as well.
For every strict-majority vector, the definitions of \(t\) and \(u\) yield exactly \(Ay=Fu-t\mathbf1\), with \(t>0\). The vertex and edge coordinates consequently have the stated signs and expressions. The dummy row is zero in \(F\), so its exposure expression is always \(-t<0\). The dummy type cannot be illuded.
The choice of \(h\) ensures \(\varepsilon\le1/(8d(n+1))\). This verifies the displayed strict bound on the total vertex and balancing mass.
Since \(1\le k\le n\), the bounds \(\beta>5/8\) and \(\beta<3/4\) are valid. All masses are positive. In particular, the claimed lower bound for \(\mu_z\) follows from the stated bounds.
The edge coefficients sum to \(d\), so their masses sum to \(\beta\). The total mass is exactly \(1\). Every mass is dyadic because all denominators introduced are powers of two.
Every edge mass exceeds the combined mass of all vertex types and the balancing type. This is the precise separation needed in soundness; neither equality nor a zero-mass case has been overlooked.
If an edge type is not illuded, the dummy’s unavoidable failure and the edge-mass lower bound give the displayed upper bound strictly below \(\beta<3/4\). Thus every edge must be illuded.
For an illuded vertex, \(u_v>t\). For an illuded edge, \(u_v+u_w<-t\). Two illuded endpoints would instead have sum greater than \(2t\), a contradiction. Hence the set of illuded vertices is independent.
If this set has at most \(k-1\) vertices, even including the balancing type gives illusion mass at most \(3/4-\varepsilon/2\). Therefore a successful labeling yields an independent set of size at least \(k\). This direction is fully justified.
The proposed vector \(u\) assigns every edge coordinate of \(Fu\) either \(1\) or \(4\), because an independent set contains at most one endpoint of each edge. Every selected vertex coordinate equals \(1\).
The proposed \(y^{(0)}\) has coordinate sum \(-1/4\), and multiplication by \(A\) gives \(Fu-\mathbf1/2\), exactly as claimed. All required edge and selected-vertex coordinates remain strictly positive.
Section 1 then supplies a valid labeling. The edge mass and selected-vertex mass total at least \(\beta+k\varepsilon=3/4\). No condition on the balancing type is needed. This direction is fully justified.
The number of types and the mass bit lengths are polynomially bounded. The balancing-row coordinates \(\deg_G(v)-1\) are correct, and the entries of \(F\) and \(H\) have polynomially bounded magnitude.
Minor issue: Section 7 names Hadamard’s determinant bound but does not state its precise inequality or explicitly describe its application to the cofactors. The resulting polynomial-bit-length claim is sound in substance, and this omission requires only routine exposition.
Minimum clarification: State the version of Hadamard’s bound being used and identify its application to \(H\) and its cofactor submatrices. No new lemma or change to the construction is required.
The exact rational linear algebra claim then establishes polynomial construction time, as asserted.
The prover resolves the requested complexity classification: the general continuous problem is \(\mathrm{NP}\)-complete, already for \(q=3/4\), while the endpoint \(q=1\) is polynomial-time solvable. The proof does not claim hardness for every fixed threshold below \(1\), and that stronger assertion is unnecessary for the assigned task.
⟨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.