Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe campaigner can learn the underlying graph 𝐺 of any social network (𝑁,𝐺) by spending O(𝑛2) on observation and O(𝑛3) on intervention. We derive these upper bounds by evaluating the number of queries done in Algorithm 1. It queries at most𝑛−1 one-step opinion diffusion to find the pivot agent 𝑝∗that makes agent 𝑖∈𝑁 change opinion for the first time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational population masses \(\mu\), initial type-opinion masses \(\lambda^0_{t,\ell}\), a known hypothesis class \(\mathcal H\subseteq\{0,1\}^{T\times T}\), and budgets \(q,B\), an unknown \(h\in\mathcal H\) drives synchronous majority updates: \(h_{st}=1\) means source type \(s\) influences target type \(t\), and a query chooses rational \(\eta\) with \(\sum_{\ell}\eta_{t,\ell}=\mu_t\). The intervention cost is \(c(\lambda,\eta)=\frac12\sum_{t,\ell}|\eta_{t,\ell}-\lambda_{t,\ell}|\), and the campaigner observes the complete successor mass vector after each update. Does there exist an adaptive policy that identifies \(h\) exactly for every \(h\in\mathcal H\) using at most \(q\) observations and total cost at most \(B\)?
A society is given by its support: the list of \(\tau=|T|\geq1\) types with positive binary rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. There are \(m=2\) opinions, \(\{0,1\}\).
The input includes nonnegative binary rational initial masses \(\lambda^0_{t,\ell}\) satisfying \(\lambda^0_{t,0}+\lambda^0_{t,1}=\mu_t\), a nonempty explicitly listed set \(\mathcal H\subseteq\{0,1\}^{T\times T}\) of distinct matrices with \(h_{tt}=0\), a nonnegative binary integer \(q\), and a nonnegative binary rational \(B\). Let \(K=|\mathcal H|\) and let \(L\) be the total input bit length.
An unknown fixed \(h\in\mathcal H\) governs influence: \(h_{st}=1\) means that all source mass of type \(s\) influences type \(t\). For a query \(\eta\), put \(d_t=\sum_s h_{st}(\eta_{s,1}-\eta_{s,0})\). Synchronously, the successor at type \(t\) is \((0,\mu_t)\) if \(d_t>0\), \((\mu_t,0)\) if \(d_t<0\), and \((\eta_{t,0},\eta_{t,1})\) if \(d_t=0\).
Starting at \(\lambda^0\), a query replaces the current state \(\lambda\) by any nonnegative rational \(\eta\) satisfying \(\eta_{t,0}+\eta_{t,1}=\mu_t\), at cost \(c(\lambda,\eta)=\frac12\sum_{t,\ell}|\eta_{t,\ell}-\lambda_{t,\ell}|\). One update then occurs, its complete successor vector is observed exactly, and that successor becomes the current state. Choosing \(\eta=\lambda\) permits observation without intervention.
A deterministic adaptive policy may stop after any observation history, including the empty history; it succeeds if the matrices consistent with that history form a singleton. On every branch generated by any \(h\in\mathcal H\), it must use at most \(q\) observations and incur total intervention cost at most \(B\).
Is deciding whether such a policy exists solvable in polynomial time in \(m,\tau,K,L\), or is it NP-hard?
For discrete loop-free networks on \(n\) agents, exact identification is achievable using \(O(n^2)\) observations and \(O(n^3)\) individual opinion changes; this is a sufficient-budget algorithm, not a classification of arbitrary-budget feasibility ([source](https://www.ifaamas.org/Proceedings/aamas2024/pdfs/p363.pdf)).
No result settling this continuous budget-feasibility problem was located in the literature search.
Proven result. The problem is \(\mathrm{NP}\text{-hard}\), even when \(q=1\), all type masses are equal dyadic rationals, and every candidate network has edges only from source types to sink types.
The proof is a polynomial-time reduction from \(3\)-CNF satisfiability. Its key feature is a tight budget: distinguishing the candidates associated with each variable requires a minimum intervention cost, and attaining all these minima forces a Boolean assignment.
For any state \(\eta\), define its signed coordinate by
\(x_t=\eta_{t,1}-\eta_{t,0}\).
Then
\[
\]
\( -\mu_t\leq x_t\leq\mu_t,\qquad
\eta_{t,0}=(\mu_t-x_t)/2,\qquad
\eta_{t,1}=(\mu_t+x_t)/2. \)
Write \(x_t^0=\lambda^0_{t,1}-\lambda^0_{t,0}\). Direct substitution into the intervention-cost definition gives
\( c(\lambda^0,\eta)=\frac12\sum_{t\in T}|x_t-x_t^0|. \)
For a matrix \(h\), the signed successor at type \(t\) is
\( F_h(x)_t=\mu_t \) if \( \sum_s h_{st}x_s>0 \),
\( F_h(x)_t=-\mu_t \) if \( \sum_s h_{st}x_s<0 \),
and \( F_h(x)_t=x_t \) if \( \sum_s h_{st}x_s=0 \).
Consequently, signed successors determine the observed mass vectors exactly.
If \(K>1\) and \(q=1\), a successful policy must make one query at the empty history. This query is the same for every unknown matrix. The policy succeeds precisely when its successor vectors are pairwise distinct. Thus, for this restriction, feasibility is equivalent to the existence of a rational query \(x\) such that
\( c(\lambda^0,\eta)\leq B \)
and the map \(h\mapsto F_h(x)\) is injective on \(\mathcal H\).
Let \(\Phi\) be a \(3\)-CNF formula with variables \(X_1,\ldots,X_n\) and clauses \(C_1,\ldots,C_r\). We assume \(n,r\geq1\); this restriction preserves the standard \(\mathrm{NP}\)-completeness of \(3\)-CNF satisfiability.
For each variable, introduce three source types \(a_i,p_i,n_i\) and one variable-observation type \(v_i\). For each clause, introduce one clause-observation type \(w_j\). All these types are distinct.
There are \(N=4n+r\) types so far. Let \(P\) be the smallest power of two satisfying \(P\geq N\), and add \(P-N\) padding types. Set
\( \tau=P,\qquad A=1/P,\qquad \mu_t=A\quad\text{for every }t. \)
Thus every type has positive dyadic mass, and the masses sum to one.
The initial signed coordinates are
\( x^0_{a_i}=A \)
and \(x_t^0=0\) for every other type. Equivalently, each \(a_i\) initially supports opinion \(1\) entirely, while every other type initially splits its mass equally.
Set
\( q=1,\qquad B=nA/2. \)
For a literal \(\ell\), define its source type by
\( s(X_i)=p_i,\qquad s(\neg X_i)=n_i. \)
We construct the following explicitly listed candidate matrices.
Baseline matrix \(h^0\). Its edges are exactly
\( a_i\longrightarrow v_i,\qquad p_i\longrightarrow v_i \quad (1\leq i\leq n). \)
Variable alternative \(h^i\). Starting from \(h^0\), replace the edge \(p_i\longrightarrow v_i\) by \(n_i\longrightarrow v_i\). Every other edge remains as in \(h^0\).
Clause alternative \(g^j\). Starting from \(h^0\), add the edges
\( s(\ell)\longrightarrow w_j \quad\text{for every literal }\ell\text{ in }C_j. \)
Repeated literals contribute only one edge. Each clause has at least one literal, so at least one edge is added.
Finally, let
\( \mathcal H=\{h^0,h^1,\ldots,h^n,g^1,\ldots,g^r\}. \)
All matrices are distinct: each alternative changes a different target column of the baseline. Every edge joins a source type to a distinct observation type, so all diagonal entries are zero.
The construction has polynomial size. Indeed, \(P<2N\), there are \(K=1+n+r\) matrices, and their explicit listings contain \(KP^2\) binary entries. All rational parameters have polynomial encoding length.
Each alternative differs from \(h^0\) only in the incoming edges of its dedicated observation type:
Therefore, for a fixed query, its successor can differ from the baseline successor only at that dedicated coordinate.
Suppose every alternative has a successor different from the baseline successor. Consider two different alternatives, with dedicated targets \(t\) and \(t'\). At coordinate \(t\), the first alternative differs from the baseline, whereas the second agrees with the baseline. Hence their successors are different.
It follows that the query identifies all matrices exactly if and only if it distinguishes every alternative from \(h^0\).
Assume the constructed instance has a successful policy. By Section 1, its query \(x\) distinguishes every alternative from \(h^0\) and costs at most \(B\).
For each variable, put
\( z_i=x_{a_i},\qquad u_i=x_{p_i},\qquad b_i=x_{n_i}, \)
and define its contribution to twice the intervention cost by
\( \Delta_i=|z_i-A|+|u_i|+|b_i|. \)
At target \(v_i\), the influence sums under \(h^0\) and \(h^i\) are respectively
\( f_i=z_i+u_i,\qquad e_i=z_i+b_i. \)
If both sums were positive, both successors would be \(A\) at this target. Since the matrices agree at every other target, they would be indistinguishable. Thus at least one of \(f_i,e_i\) is nonpositive.
If \(f_i\leq0\), the triangle inequality gives
\( \Delta_i \geq |z_i+u_i-A|+|b_i| =A-(z_i+u_i)+|b_i| \geq A. \)
If \(e_i\leq0\), the symmetric calculation gives
\( \Delta_i \geq |z_i+b_i-A|+|u_i| =A-(z_i+b_i)+|u_i| \geq A. \)
Therefore \(\Delta_i\geq A\) for every variable.
All remaining types initially have signed coordinate zero. Write their total contribution as
\( R=\sum_{t\notin\{a_i,p_i,n_i:1\leq i\leq n\}}|x_t|. \)
The budget now implies
\( nA\leq\sum_{i=1}^n\Delta_i \leq\sum_{i=1}^n\Delta_i+R =2c(\lambda^0,\eta) \leq2B=nA. \)
Every inequality is consequently an equality. In particular,
\( \Delta_i=A\quad\text{for every }i,\qquad R=0. \)
Thus every observation type and every padding type retains signed coordinate zero.
Suppose \(f_i=z_i+u_i\leq0\). Equality in the preceding bound forces
\( z_i+u_i=0,\qquad b_i=0. \)
Consequently,
\( A=\Delta_i=|z_i-A|+|z_i|. \)
Because \(z_i\leq A\), this equality becomes
\( A=A-z_i+|z_i|, \)
which implies \(z_i\geq0\). If \(z_i=0\), then both influence sums \(f_i,e_i\) are zero, and both matrices retain exactly the same query coordinate at \(v_i\). That contradicts distinguishability. Hence
\( 0<z_i\leq A,\qquad u_i=-z_i,\qquad b_i=0. \)
Symmetrically, if \(e_i\leq0\), we obtain
\( 0<z_i\leq A,\qquad b_i=-z_i,\qquad u_i=0. \)
Therefore, for each variable, exactly one literal-source coordinate is strictly negative, and the other is zero. Define the assignment by
\( X_i=\text{true}\quad\text{if }u_i<0, \)
and
\( X_i=\text{false}\quad\text{if }b_i<0. \)
Under this assignment, a literal is true exactly when its source coordinate is strictly negative.
The query coordinate at \(w_j\) is zero because \(R=0\). Under \(h^0\), this type has no incoming edges, so its successor remains zero.
Under \(g^j\), its influence sum is
\( D_j=\sum_{t\in S_j}x_t,\qquad S_j=\{s(\ell):\ell\text{ occurs in }C_j\}. \)
Every summand is nonpositive. If the clause had no true literal, every summand would be zero. Then \(D_j=0\), and \(g^j\) would give the same successor as \(h^0\), contradicting successful identification.
Thus every clause contains a true literal. The extracted assignment satisfies \(\Phi\).
Conversely, suppose \(\Phi\) has a satisfying assignment. Choose the following rational query:
\( x_{a_i}=A \)
for every variable, and
\( (x_{p_i},x_{n_i})=(-A,0) \)
when \(X_i\) is true, while
\( (x_{p_i},x_{n_i})=(0,-A) \)
when \(X_i\) is false. Set every observation and padding coordinate to zero.
All coordinates lie within their permitted intervals. Exactly one literal-source coordinate per variable moves from zero to \(-A\). Hence
\( c(\lambda^0,\eta)=\frac12 nA=B. \)
At each variable target \(v_i\), the two influence sums under \(h^0\) and \(h^i\) are zero and \(A\), in some order. Their successors are therefore zero and \(A\), respectively, so these matrices are distinguished.
At each clause target \(w_j\), the baseline successor is zero. Since the clause is satisfied, at least one of its literal-source coordinates is \(-A\), while all others are nonpositive. Its influence sum under \(g^j\) is strictly negative, so that successor is \(-A\). Thus \(g^j\) is distinguished from the baseline.
Section 3 now shows that all candidate successors are pairwise distinct. The policy makes this query, observes the successor, and stops. It uses one observation and cost exactly \(B\).
The construction proves the equivalence
\( \Phi\text{ is satisfiable} \quad\Longleftrightarrow\quad \text{the constructed budget-feasibility instance admits a successful policy}. \)
It is a polynomial-time many-one reduction, so the requested decision problem is \(\mathrm{NP}\text{-hard}\). This holds already for one observation; adaptivity is unnecessary for the hardness.
Consequently, a polynomial-time algorithm in \(m,\tau,K,L\) would imply \(\mathrm{P}=\mathrm{NP}\). The result is compatible with the [sufficient-budget identification theorem cited in the question](https://www.ifaamas.org/Proceedings/aamas2024/pdfs/p363.pdf): here the intervention budget is fixed at a tight threshold.
⟨structured verdict parsed — rendered above⟩
The proof resolves the assigned problem. The reduction is correct, the tight-budget argument is rigorous, and no mathematical gaps were found. It establishes \(\mathrm{NP}\)-hardness even with one observation.
The signed-coordinate parametrization is valid: nonnegative opinion masses summing to \(\mu_t\) correspond exactly to rational coordinates satisfying \(-\mu_t\leq x_t\leq\mu_t\).
The cost identity is correct. For each type, both opinion masses change in absolute value by \(|x_t-x_t^0|/2\), so its contribution to the intervention cost is \(|x_t-x_t^0|/2\).
The successor rule correctly handles all three influence cases, including retention of the query coordinate when the influence sum is zero. Signed successors uniquely determine the complete observed mass vectors.
For \(K>1\) and \(q=1\), stopping at the empty history cannot succeed. A deterministic policy therefore makes a single common query, and identification succeeds exactly when all candidate successors are pairwise distinct. This correctly reduces the policy problem to query existence.
The construction satisfies the input requirements:
Repeated clause literals are handled correctly by including each corresponding edge once. This does not change whether a clause contains a true literal.
The source problem is standard \(3\)-CNF satisfiability. Its restriction to instances with at least one variable and one clause does not introduce a substantive issue.
Section 3 is correct.
For a fixed query, an alternative can change the successor only at its dedicated target. If two alternatives are each distinguished from the baseline, then at the first alternative’s dedicated target, its successor differs from the baseline while the second alternative’s successor agrees with the baseline.
Thus distinguishing every alternative from the baseline is both necessary and sufficient for identifying all candidates. This argument remains valid when some influence sums are zero.
The lower bound \(\Delta_i\geq A\) is valid.
Distinguishability implies that the two sums \(f_i\) and \(e_i\) cannot both be positive, since both would then produce successor coordinate \(A\). Consequently at least one is nonpositive.
When \(f_i\leq0\), the displayed triangle inequality and sign evaluation are correct:
\(\Delta_i\geq |f_i-A|+|b_i|=A-f_i+|b_i|\geq A\).
The corresponding calculation for \(e_i\leq0\) is also correct.
The argument uses this condition only as a necessary condition for distinguishability; it does not incorrectly assert that nonpositivity alone suffices.
The budget chain is correct. The variable-source triples are disjoint, and \(R\) accounts for every remaining coordinate. Thus \(\sum_i\Delta_i+R\) is exactly twice the query cost.
Since each \(\Delta_i\geq A\), \(R\geq0\), and the total is at most \(nA\), equality follows throughout. In particular:
\(\Delta_i=A\) for every variable, and \(R=0\).
Because \(R\) is a sum of absolute values, every observation and padding coordinate is zero.
The equality analysis is sound.
In the case \(f_i\leq0\), equality in the established bound forces \(f_i=0\) and \(b_i=0\). Hence \(u_i=-z_i\). Substitution into \(\Delta_i=A\), together with \(z_i\leq A\), correctly implies \(z_i\geq0\).
The case \(z_i=0\) is correctly excluded: both influence sums would be zero, both networks would retain the same query coordinate at \(v_i\), and they agree at every other target.
The symmetric case is equally valid. Therefore exactly one of \(u_i,b_i\) is strictly negative and the other is zero. The extracted assignment is well-defined for every variable, and a literal is true exactly when its source coordinate is strictly negative.
The soundness argument for clauses correctly uses \(R=0\). The baseline successor at each clause target is zero. All literal-source coordinates are nonpositive; if a clause had no true literal, its entire influence sum would be zero, making its alternative indistinguishable from the baseline.
The completeness query is rational and respects every coordinate bound. Its cost is exactly \(nA/2=B\).
For every variable, the baseline and its alternative have influence sums zero and \(A\), producing distinct successors because the query coordinate at the target is zero.
For every satisfied clause, the alternative’s influence sum is strictly negative, producing successor \(-A\), distinct from the baseline’s zero. Section 3 then correctly establishes pairwise distinctness of all candidate successors.
The resulting policy obeys both branchwise constraints: one observation and cost \(B\).
Both directions of the reduction are established, and the construction is polynomial in the formula’s encoding length. The claimed \(\mathrm{NP}\)-hardness follows.
The proof does not claim membership in \(\mathrm{NP}\), and none is needed for the assigned hardness conclusion. The sufficient-budget result mentioned in the task is not used as a premise.
No mathematical repair or additional clarification is required.
⟨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.