Answer: \(\mathrm{NP}\text{-hard}\); indeed, the budget decision version is weakly \(\mathrm{NP}\text{-complete}\).
Corollary 22 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateMIE and the 1 2-ILLUSION problem can be solved in polynomial time. Hardness In this section we present variants of the MIE, MIAE and MIRE problems. Problem 4. Let p ∈[0, 1], p ∈Q. We define the p-IA prob- lem as follows: Given a graph G = (V, E), f : V → {B, R}, and integer k, determine if the addition of at most k edges can ensure each node has at least a p-fraction of blue nodes in its neighbourhood.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \(\mu\), a blue/red partition with blue mass greater than \(1/2\), and a symmetric rational matrix \(a\) of link densities between finitely many exchangeable types, choose a symmetric post-edit density matrix \(z\) in \([0,1]\) to minimize one-half times the sum over \(t,u\) of \(\mu_t \mu_u |z_{tu}-a_{tu}|\), subject to sum over blue \(u\) of \(\mu_u z_{tu}\) being at least the sum over red \(u\) of \(\mu_u z_{tu}\) for every type \(t\); addition-only and removal-only variants impose \(z \ge a\) or \(z \le a\).
Fix rational \(p\in(0,\frac12)\setminus\{\frac13\}\). An instance has a finite type set \(T\), rational masses \(\mu_t\ge0\) with \(\sum_{t\in T}\mu_t=1\), colours \(\chi:T\to\{B,R\}\), and a symmetric \(0\)-\(1\) block-adjacency matrix \(A\).
A selectable absent type-pair is an unordered \(\{t,u\}\), possibly \(t=u\), with \(A_{tu}=0\). Selecting \(S\) sets the corresponding entries of \(A'\) to \(1\). Its cost is \(\rho_{tu}=\mu_t\mu_u\) for \(t\ne u\), and \(\rho_{tt}=\mu_t^2/2\).
Write \(D_t(A')=\sum_{u\in T}\mu_uA'_{tu}\). A solution is feasible when every \(t\) with \(D_t(A')>0\) satisfies \(\sum_{\chi(u)=B}\mu_uA'_{tu}\ge pD_t(A')\).
Is this continuous \(p\)-illusion addition problem solvable in polynomial time, or is it NP-hard?
For the discrete \(p\)-illusion addition problem, where vertices are individually coloured and each added edge has unit cost, NP-hardness is known for every rational \(p\in(0,\frac12)\setminus\{\frac13\}\).
Consider the standard budget decision version:
Given a rational budget \(C\), is there a feasible set of additions whose total cost is at most \(C\)?
A polynomial-time algorithm for the minimum-cost optimization problem would solve this decision problem.
Define \(\alpha=p/(1-p)\). If \(B_t\) and \(R_t\) denote the blue and red neighbor masses of type \(t\), respectively, then the feasibility condition is equivalent to
\[ B_t\ge p(B_t+R_t) \quad\Longleftrightarrow\quad B_t\ge \alpha R_t. \]
We prove that the budget decision problem is NP-complete by reduction from \(\textsc{Subset Sum}\).
Let \(a_1,\ldots,a_n\) be positive integers, let \(K\) be a positive integer, and assume \(K\le W:=\sum_{i=1}^n a_i\). The question is whether there exists \(I\subseteq\{1,\ldots,n\}\) such that \(\sum_{i\in I}a_i=K\).
Define
\[ L:=p(W-K)+K=pW+(1-p)K, \qquad c:=\frac{p}{2L}, \qquad s:=\frac p2. \]
Then \(cL=s\). Further define
\[ R:=1-s-cW, \qquad r:=\frac{1-p}{4}. \]
The following identities will be used:
\[ R=(1-p)\bigl(1-c(W-K)\bigr), \]
and therefore
\[ \alpha R =p\bigl(1-c(W-K)\bigr) =s+cK. \]
Indeed, the second identity follows from \(c[p(W-K)+K]=s=p/2\).
All the masses below are positive. In particular,
\[ cW=\frac{pW}{2[pW+(1-p)K]}<\frac12, \]
so
\[ R>1-\frac p2-\frac12=\frac{1-p}{2}>r. \]
Create the following types:
Their masses are
\[ \mu_z=r, \qquad \mu_y=R-r, \qquad \mu_b=s, \qquad \mu_{x_i}=ca_i. \]
The total blue mass is
\[ M:=s+cW, \]
and the total red mass is \(R\). Hence the masses sum to \(M+R=1\).
Set the initial adjacency matrix as follows:
Thus the only absent pairs are \(\{z,x_i\}\), \(\{y,x_i\}\), and \(\{y,y\}\).
Set the budget to
\[ C:=rcK. \]
The construction uses \(n+3\) types and rational numbers of polynomial encoding length.
For type \(z\), the initial blue and red neighbor masses are
\[ B_z=s, \qquad R_z=R. \]
Since \(\alpha R=s+cK>s\), type \(z\) is initially infeasible.
For type \(y\),
\[ B_y=s, \qquad R_y=r. \]
Moreover,
\[ \alpha r =\frac{p}{1-p}\cdot\frac{1-p}{4} =\frac p4<s, \]
so \(y\) is feasible.
For the shield \(b\),
\[ B_b=M, \qquad R_b=R. \]
Using \(\alpha R=s+cK\),
\[ M-\alpha R=(s+cW)-(s+cK)=c(W-K)\ge0. \]
Thus \(b\) is feasible. Every item type \(x_i\) initially has blue neighbor mass \(M\) and red neighbor mass \(0\), so it is feasible.
We claim that any feasible solution can be transformed, without increasing its cost, into one containing only pairs \(\{z,x_i\}\).
First remove \(\{y,y\}\), if selected. This only decreases the red neighbor mass of \(y\), so feasibility is preserved.
Next remove every selected pair \(\{y,x_i\}\). Removing such pairs decreases the red neighbor mass of each affected \(x_i\). After all these pairs have been removed, type \(y\) returns to its initial values \(B_y=s\) and \(R_y=r\), which satisfy \(s>\alpha r\). Hence the resulting solution remains feasible.
There are no other absent pairs. Therefore every feasible solution has a no-more-expensive canonical solution of the form
\[ S_I:=\bigl\{\{z,x_i\}:i\in I\bigr\} \]
for some \(I\subseteq\{1,\ldots,n\}\).
Under \(S_I\), the red type \(z\) has
\[ B_z=s+c\sum_{i\in I}a_i, \qquad R_z=R. \]
Consequently,
\[ z\text{ is feasible} \quad\Longleftrightarrow\quad s+c\sum_{i\in I}a_i\ge\alpha R=s+cK, \]
which, since \(c>0\), is equivalent to
\[ \sum_{i\in I}a_i\ge K. \]
If \(\{z,x_i\}\) is selected, then \(x_i\) gains red neighbor mass \(r\). Its blue neighbor mass remains \(M\), and
\[ M\ge s=\frac p2>\frac p4=\alpha r. \]
Thus every selected item type remains feasible. All other types remain feasible by the preceding calculations. Hence \(S_I\) is feasible exactly when \(\sum_{i\in I}a_i\ge K\).
Its cost is
\[ \operatorname{cost}(S_I) =\sum_{i\in I}\mu_z\mu_{x_i} =rc\sum_{i\in I}a_i. \]
Therefore
\[ \operatorname{cost}(S_I)\le C=rcK \quad\Longleftrightarrow\quad \sum_{i\in I}a_i\le K. \]
Combining feasibility and the budget constraint gives
\[ S_I\text{ is feasible and has cost at most }C \quad\Longleftrightarrow\quad \sum_{i\in I}a_i=K. \]
This proves the correctness of the reduction.
The budget decision problem belongs to \(\mathrm{NP}\): a selected set contains at most \(|T|(|T|+1)/2\) pairs, and all costs and feasibility inequalities can be checked exactly using polynomial-time rational arithmetic.
The reduction proves weak \(\mathrm{NP}\)-hardness for every fixed rational \(p\in(0,1/2)\). Thus the decision version is weakly \(\mathrm{NP}\)-complete, and computing a minimum-cost feasible addition set is \(\mathrm{NP}\)-hard.
The proof actually also works for \(p=1/3\); the exclusion of that value is unnecessary for this continuous formulation.
⟨structured verdict parsed — rendered above⟩
The reduction correctly establishes NP-hardness of the continuous \(p\)-illusion addition problem for every fixed rational \(p\in(0,\frac12)\), including the values required by the task. The construction, canonicalization argument, feasibility calculations, and budget equivalence are internally consistent.
No major mathematical gap was found. Two minor qualifications concern the source-problem restriction and the term “weakly NP-complete.”
With \(B_t\) and \(R_t\) denoting blue and red neighbor mass, respectively,
\[ B_t\ge p(B_t+R_t) \]
is equivalent to
\[ (1-p)B_t\ge pR_t, \]
and hence to \(B_t\ge \alpha R_t\), where \(\alpha=p/(1-p)\). This is correct because \(1-p>0\).
For a type with \(D_t=0\), both \(B_t\) and \(R_t\) are zero, so the reformulated inequality holds automatically and remains consistent with the original conditional definition.
The definitions
\[ L=p(W-K)+K=pW+(1-p)K,\qquad c=\frac{p}{2L},\qquad s=\frac p2 \]
give \(cL=s\), as claimed.
The identity
\[ R=(1-p)\bigl(1-c(W-K)\bigr) \]
follows from \(R=1-s-cW\) and \(c[pW+(1-p)K]=p/2\). Consequently,
\[ \alpha R=p\bigl(1-c(W-K)\bigr)=s+cK. \]
All these calculations are correct.
Because \(K>0\),
\[ cW=\frac{pW}{2[pW+(1-p)K]}<\frac12. \]
Thus \(R>(1-p)/2>(1-p)/4=r\), proving that every constructed mass, including \(\mu_y=R-r\), is positive.
The blue mass is \(M=s+cW\), while the red mass is \(R=1-s-cW\), so the total mass is exactly one.
The adjacency specification exhausts all unordered pairs among the constructed types. Therefore the claimed list of absent pairs,
\[ \{z,x_i\},\qquad \{y,x_i\},\qquad \{y,y\}, \]
is correct.
For \(z\), the values are \(B_z=s\) and \(R_z=R\). Since \(\alpha R=s+cK>s\), \(z\) is infeasible.
For \(y\), the values are \(B_y=s\) and \(R_y=r\). Since \(\alpha r=p/4<s=p/2\), \(y\) is feasible.
For \(b\),
\[ B_b-\alpha R=(s+cW)-(s+cK)=c(W-K)\ge0, \]
so \(b\) is feasible.
Each \(x_i\) is adjacent to every blue type and initially to no red type, giving \(B_{x_i}=M\) and \(R_{x_i}=0\). Hence every item type is feasible.
These calculations correctly account for the blue diagonal adjacencies.
Removing a selected \(\{y,y\}\) decreases only the red neighbor mass of \(y\), so it cannot destroy feasibility.
Removing all selected \(\{y,x_i\}\) pairs:
The resulting \(y\) is feasible because \(s>\alpha r\). Thus the final transformed solution is feasible and no more expensive. The canonicalization argument is valid.
The wording could more explicitly note that removing \(\{y,x_i\}\) decreases the blue neighbor mass of \(y\), but the final feasibility calculation correctly handles that effect.
For a canonical set \(S_I\),
\[ B_z=s+c\sum_{i\in I}a_i,\qquad R_z=R. \]
Using \(\alpha R=s+cK\), feasibility of \(z\) is equivalent to
\[ \sum_{i\in I}a_i\ge K. \]
A selected item \(x_i\) gains red neighbor mass \(r\), while retaining blue neighbor mass \(M\). Since
\[ M\ge s=\frac p2>\frac p4=\alpha r, \]
it remains feasible. All other types retain their previously verified feasibility.
The cost is
\[ \operatorname{cost}(S_I)=rc\sum_{i\in I}a_i. \]
Because \(r,c>0\), the budget constraint \(\operatorname{cost}(S_I)\le rcK\) is equivalent to
\[ \sum_{i\in I}a_i\le K. \]
Combining the two inequalities gives exact equality with \(K\). This proves the reduction’s correctness.
The construction has polynomial size and its rational parameters have polynomial binary encoding length. A selected-pair certificate has polynomial size, and exact rational feasibility and cost comparisons are polynomial-time operations. Thus the decision problem belongs to NP.
The reduction therefore proves NP-hardness and, together with membership in NP, NP-completeness of the budget decision version.
⟨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.