Manipulating Opinion Diffusion in Social Networks (d4-conf-ijcai-2017-0835)

Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), initial opinions \(o_t\in\{0,1\}\), rational block-exposure coefficients \(a_{tu}\), a quota \(Q\), and a budget \(K\), can one choose bribe masses \(b_t\in[0,\mu_t]\) with \(\sum_t b_t\le K\) so that every stable endpoint reachable by finitely many asynchronous moves of positive eligible mass and maximizing \(\sum_t x_t\) has \(\sum_t x_t\ge Q\), where a type may move mass toward black exactly when \(B_t(x)>W_t(x)\) and toward white when \(W_t(x)>B_t(x)\)?

A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Each type has initial opinion \(o_t\in\{0,1\}\). Input exposures satisfy \(a_{tu}=a_{ut}\in\mathbb{Q}\cap[0,1]\); diagonal entries describe interaction within a type. Input quota and budget satisfy \(Q\in\mathbb{Q}\cap(0,1]\) and \(K\in\mathbb{Q}_{>0}\).
Let \(m\) count unordered type pairs with positive exposure, including diagonal pairs, and let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
A state records black masses \(x_t\in[0,\mu_t]\), with exposures \(B_t(x)=\sum_{u\in T}a_{tu}x_u\) and \(W_t(x)=\sum_{u\in T}a_{tu}(\mu_u-x_u)\).
A bribe chooses real masses \(b_t\in[0,\mu_t]\) with \(\sum_t b_t\le K\), flips their initial opinions once, and produces \(x_t^0=\mu_to_t+(1-2o_t)b_t\); bribed mass subsequently follows the same update rules.
An asynchronous move changes one coordinate: increase \(x_t\) by any real \(0<\delta\le\mu_t-x_t\) if \(B_t(x)>W_t(x)\), or decrease it by any real \(0<\delta\le x_t\) if \(W_t(x)>B_t(x)\). Eligibility is evaluated before the move; ties permit no move.
A state is stable if no move is eligible. Let \(R(b)\) contain stable states reachable from \(x^0\) by finitely many moves, including zero moves; an optimistic endpoint is an element of \(R(b)\) attaining its maximum total black mass.
The decision problem asks whether a feasible bribe has at least one optimistic endpoint and every optimistic endpoint satisfies \(\sum_t x_t\ge Q\).

Is this continuous optimistic opinion-diffusion bribery problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?

For finite agents on simple undirected graphs, unit-cost initial-opinion bribery with optimistic stable updates is \(\mathrm{NP}\)-complete; it is polynomial-time solvable on forests. [Source](https://www.ijcai.org/proceedings/2017/0124.pdf)
No result settling exactly the mass-based problem above was located in the literature search.

Result

The problem is \(\mathrm{NP}\)-complete, hence \(\mathrm{NP}\)-hard.

The proof handles arbitrary real-valued bribes. It also establishes that every initial state has a unique optimistic endpoint, reachable in at most \(2\tau\) moves. Hardness holds even with dyadic masses and \(m<3\tau\).

1. A greatest reachable stable state always exists

Write the exposure difference as
\[ h_t(x)=B_t(x)-W_t(x)=\sum_{u\in T}a_{tu}(2x_u-\mu_u). \]
Because all exposures are nonnegative, \(x\le y\) coordinatewise implies \(h_t(x)\le h_t(y)\) for every \(t\).

Lemma. From any initial state \(x^0\), the following procedure reaches a stable state \(D\) that coordinatewise dominates every reachable stable state.

• Whenever \(x_t<\mu_t\) and \(h_t(x)>0\), set \(x_t=\mu_t\). Continue until no such move remains; call the resulting state \(U\).
• Starting from \(U\), whenever \(x_t>0\) and \(h_t(x)<0\), set \(x_t=0\). Continue until no such move remains; call the resulting state \(D\).

Each phase makes at most \(\tau\) moves.

Proof. Every move is permitted by the specified rules. In the first phase, each changed coordinate becomes full and never changes again during that phase. Thus the phase terminates after at most \(\tau\) moves, and
\[ U_t<\mu_t\quad\Longrightarrow\quad h_t(U)\le0. \]

First, \(U\) bounds every state reachable from \(x^0\), including states reached using partial moves. Initially \(x^0\le U\). Suppose a reachable state \(x\) satisfies \(x\le U\). A decrease preserves this inequality. An increase also preserves it when \(U_t=\mu_t\). When \(U_t<\mu_t\), however,
\[ h_t(x)\le h_t(U)\le0, \]
so an increase of coordinate \(t\) is impossible. Induction on the number of moves proves the bound.

The second phase also terminates after at most \(\tau\) moves. Throughout this phase all exposure differences weakly decrease. A coordinate set to zero therefore retains a strictly negative exposure difference. A coordinate left below its maximum already had a nonpositive exposure difference at \(U\), and retains one. Consequently no increase is eligible at \(D\); termination of the second phase ensures that no decrease is eligible either. Thus \(D\) is stable.

Finally, let \(y\le U\) be any stable state. We show that \(y\) remains below every state in the second phase. Suppose the current state is \(z\ge y\), and coordinate \(t\) is about to be set to zero. Then
\[ h_t(y)\le h_t(z)<0. \]
Stability forces \(y_t=0\), since otherwise a decrease would be eligible at \(y\). Hence \(y\) remains below the next state. Induction gives \(y\le D\).

Every reachable stable state lies below \(U\), and hence below \(D\). Since \(D\) itself is reachable, it is the greatest reachable stable state. \(\square\)

In particular, the maximum defining an optimistic endpoint is always attained. Moreover, the optimistic endpoint is unique: if a reachable stable state \(y\le D\) has the same total black mass as \(D\), every coordinate difference \(D_t-y_t\) must be zero.

Thus the decision question is equivalent to asking whether some feasible bribe produces \(D\) with total black mass at least \(Q\).

2. Reduction parameters

We reduce from Vertex Cover, using its standard \(\mathrm{NP}\)-completeness ([Karp, 1972](https://people.seas.harvard.edu/~madhusudan/courses/Fall2020/Lectures/L19-after.pdf)).

Let the input be a simple undirected graph \(G=(V,E)\), with \(n=|V|\), \(r=|E|\), and cover bound \(k\). We may restrict to
\[ n\ge2,\qquad r\ge1,\qquad 1\le k<n. \]
The excluded cases are decidable immediately and can be mapped to fixed restricted yes- or no-instances.

Let \(N\) be the smallest power of two satisfying \(N\ge n\), and define
\[ M=n+1,\qquad c=\frac1{16N},\qquad \eta=\frac1{128N^2}=\frac{c}{8N},\qquad \varepsilon=\frac{2\eta}{rM},\qquad \kappa=k(c+2\eta). \]

The following bounds will be used:
\[ 0<\eta<c,\qquad c+2\eta<1, \]
\[ \kappa\le N(c+2\eta)=\frac1{16}+\frac1{64N}<\frac12, \]
and
\[ (k+1)(c-\eta)-\kappa =c-(3k+1)\eta =c\left(1-\frac{3k+1}{8N}\right)>0. \]
The last inequality follows from \(k\le N\).

Choose the smallest power of two \(H\) satisfying
\[ H\ge n+(r+1)M, \]
and put
\[ B=H-n-rM. \]
Then \(B\ge M=n+1\).

3. Construction

There is one type for each vertex, one type for each edge, and one additional anchor type \(z\). Their masses are
\[ \mu_v=\frac1H,\qquad \mu_e=\frac MH,\qquad \mu_z=\frac BH. \]
They are positive dyadic rationals summing to one.

Initially all vertex and edge types are white, while the anchor is black.

The positive exposures are:

• \(a_{vv}=1\) for every vertex \(v\), and \(a_{zz}=1\).
• \(a_{vz}=a_{zv}=(1-2c)/B\) for every vertex \(v\).
• For every edge \(e=\{u,v\}\), \(a_{eu}=a_{ue}=a_{ev}=a_{ve}=\varepsilon\).
• \(a_{ez}=a_{ze}=\varepsilon/B\) for every edge \(e\).

All other exposures are zero. These exposures are symmetric and belong to \([0,1]\): \(1-2c>0\), \(B\ge3\), and \(0<\varepsilon<1\).

Set
\[ K=\frac{\kappa}{H}, \qquad Q=\frac{B+rM}{H}. \]
Thus \(K>0\) and \(0<Q<1\).

The support size and positive-pair count are
\[ \tau=n+r+1,\qquad m=2n+3r+1<3\tau. \]
Every nonzero numerical entry has \(O(\log(n+r))\) bits. The construction therefore has polynomial encoding length and can be generated in polynomial time, including under a dense exposure-matrix encoding.

Exposure calculations

It is convenient to use unnormalized black masses \(y_t=Hx_t\). Their capacities are \(1\), \(M\), and \(B\), respectively. Define
\[ \widehat h_t(y)=Hh_t(y/H). \]
Multiplication by \(H>0\) preserves eligibility signs.

For a vertex \(v\),
\[ \widehat h_v(y) =2y_v-1+\frac{1-2c}{B}(2y_z-B) +\varepsilon\sum_{e\ni v}(2y_e-M). \]
Since \(y_z\le B\), \(y_e\le M\), and the degree \(d(v)\le r\),
\[ \widehat h_v(y) \le2y_v-2c+\varepsilon d(v)M \le2y_v-2c+2\eta. \tag{1} \]
When \(y_z=B\), the corresponding lower bound is
\[ \widehat h_v(y)\ge2y_v-2c-2\eta. \tag{2} \]

For an edge \(e=\{u,v\}\),
\[ \widehat h_e(y) =\varepsilon\bigl(2(y_u+y_v)-2\bigr) +\frac{\varepsilon}{B}(2y_z-B) \le\varepsilon\bigl(2(y_u+y_v)-1\bigr). \tag{3} \]
Equality holds in (3) whenever \(y_z=B\).

4. Completeness: a vertex cover gives a successful bribe

Suppose \(C\subseteq V\) is a vertex cover with \(|C|\le k\). Bribe unnormalized mass
\[ \beta_v=Hb_v=c+2\eta \]
at each vertex \(v\in C\), and bribe nothing elsewhere. The total normalized cost is at most
\[ \frac{k(c+2\eta)}H=K. \]

The anchor remains at \(y_z=B\). By (2), each chosen vertex initially satisfies
\[ \widehat h_v(y)\ge2(c+2\eta)-2c-2\eta=2\eta>0. \]
Set every chosen vertex to its full black mass \(1\). These increases cannot reduce any exposure difference, so all these moves remain eligible.

Every edge has a chosen endpoint. Consequently, after these moves, each edge satisfies
\[ \widehat h_e(y)=\varepsilon\bigl(2(y_u+y_v)-1\bigr)\ge\varepsilon>0. \]
Set every edge type to its full black mass \(M\).

We verify stability of the resulting state.

• An unchosen vertex has black mass zero and, by (1),

\[ \widehat h_v(y)\le-2c+2\eta<0. \]

• A chosen vertex is full and, by (2),

\[ \widehat h_v(y)\ge2-2c-2\eta>0. \]

• Every edge is full and has positive exposure difference, as above.
• The anchor is full. Its exposure difference satisfies

\[ \widehat h_z(y) =B+\frac{1-2c}{B}\sum_{v\in V}(2y_v-1) +\frac{\varepsilon}{B}\sum_{e\in E}(2y_e-M) \ge B-\frac{n+2\eta}{B}>0. \]
Here \(\varepsilon rM=2\eta\), and \(B\ge n+1\) implies \(B^2>n+2\eta\).

Thus the state is stable and finitely reachable. Its total black mass is
\[ \frac{B+rM+|C|}{H}\ge Q. \]
By the lemma, an optimistic endpoint exists and has at least this much black mass. The constructed instance is therefore a yes-instance.

5. Soundness: arbitrary fractional bribes give a vertex cover

Consider any feasible bribe, allowing bribes to every type. Write \(\beta_t=Hb_t\), so
\[ \sum_t\beta_t\le\kappa. \]
Initially \(y_v=\beta_v\) and \(y_e=\beta_e\), while \(y_z=B-\beta_z\).

Apply the increasing phase of the lemma, using unnormalized coordinates, and call its endpoint \(U\). Define
\[ S=\{v\in V:U_v=1\}. \]

At most \(k\) vertex types become full

We claim that every \(v\in S\) satisfies
\[ \beta_v>c-\eta. \tag{4} \]

If \(v\) was initially full, then \(\beta_v=1>c-\eta\). Otherwise, immediately before its increasing-phase move, its black mass is still \(\beta_v\): that phase changes a coordinate only by setting it directly to its maximum. Eligibility and (1) give
\[ 0<\widehat h_v(y)\le2\beta_v-2c+2\eta, \]
which proves (4).

If \(|S|\ge k+1\), the budget would therefore satisfy
\[ \kappa\ge\sum_{v\in S}\beta_v >(k+1)(c-\eta)>\kappa, \]
a contradiction. Hence \(|S|\le k\).

An uncovered edge must be white at every reachable stable state

Suppose \(S\) is not a vertex cover, and choose an edge \(e=\{u,v\}\) with neither endpoint in \(S\).

Neither endpoint was changed during the increasing phase, so
\[ U_u=\beta_u,\qquad U_v=\beta_v,\qquad U_u+U_v\le\kappa<\frac12. \]
By (3),
\[ \widehat h_e(U)\le\varepsilon(2\kappa-1)<0. \]

Every reachable state lies coordinatewise below \(U\), by the lemma. Therefore any reachable stable state \(y\) satisfies
\[ \widehat h_e(y)\le\widehat h_e(U)<0. \]
Stability forces \(y_e=0\).

Such a stable state has total black mass at most
\[ \frac{B+(r-1)M+n}{H} =\frac{B+rM}{H}-\frac{M-n}{H} =Q-\frac1H<Q. \]
Thus no feasible successful bribe can leave an uncovered edge.

Every successful bribe consequently yields a vertex cover \(S\) with \(|S|\le k\). This proves the reduction and establishes \(\mathrm{NP}\)-hardness.

6. Membership in \(\mathrm{NP}\) and running times

The remaining issue is that bribes may be arbitrary real numbers. We prove that every yes-instance admits a polynomial-size rational bribe.

Take a successful real bribe and its canonical execution from the lemma. Record:

• the ordered list of full increases;
• the ordered list of full decreases;
• whether each final coordinate is zero, strictly interior, or full.

There are at most \(\tau\) moves in each phase. For this fixed execution pattern, every intermediate coordinate is either an affine function of the bribe variables, zero, or its capacity.

Consequently, the following requirements are rational linear equalities or inequalities:

• bribe bounds and budget;
• strict exposure-sign and positive-move-size conditions at every move;
• the final quota;
• final stability, expressed according to the recorded status as

\[ w_t=0,\ h_t(w)\le0; \qquad 0<w_t<\mu_t,\ h_t(w)=0; \qquad w_t=\mu_t,\ h_t(w)\ge0. \]

The number of constraints and their coefficient encoding lengths are polynomial in \(L\).

Introduce a variable \(s\in[0,1]\), and replace every strict inequality \(f(b)>0\) by \(f(b)\ge s\). The original real witness satisfies all finitely many strict inequalities, so this bounded rational polytope has a feasible point with \(s>0\).

Maximize \(s\). The optimum is positive and is attained at a vertex. Such a vertex is determined by linearly independent active constraints in at most \(\tau+1\) variables. Clearing denominators and applying Cramer’s rule shows that its coordinates have polynomial encoding length: the relevant determinants have polynomial dimension and polynomial-bit integer entries. Thus a successful rational bribe of total encoding length \(C=\operatorname{poly}(L)\) exists.

A verifier receives this rational bribe, checks its cost, runs the canonical procedure, and checks its endpoint quota.

After constructing adjacency lists, each phase can maintain exposure differences and eligible coordinates in \(O(m+\tau)\) rational arithmetic operations. Each coordinate changes at most once per phase, and each incident exposure is updated only a constant number of times. For a rational bribe of encoding length \(C\), the resulting bit running time is
\[ O\bigl((m+\tau)\operatorname{poly}(L+C)\bigr). \]
For the polynomial-size certificates just proved, this is polynomial in the input length. Therefore the problem belongs to \(\mathrm{NP}\).

For completeness, a deterministic exact algorithm can enumerate the two ordered move lists and the final coordinate statuses, and solve the corresponding slack-maximization linear programs. There are at most
\[ 9\cdot3^\tau(\tau!)^2 \]
patterns, giving running time
\[ 2^{O(\tau\log(\tau+1))}\operatorname{poly}(m,\tau,L). \]

Together with the reduction, this proves \(\mathrm{NP}\)-completeness.

⟨structured verdict parsed — rendered above⟩

The claimed result is correct: the write-up establishes \(\mathrm{NP}\)-completeness for the continuous problem as stated. I found no major or minor mathematical issues. The argument handles arbitrary real bribes, strict eligibility, diagonal exposures, and finite reachability.

• Greatest reachable stable state

The identity \(h_t(x)=\sum_u a_{tu}(2x_u-\mu_u)\) is correct. Since every exposure is nonnegative, coordinatewise monotonicity holds, including when diagonal exposures are positive.

Every first-phase update is a legal move: its eligibility condition is \(h_t(x)>0\), and its size is \(\mu_t-x_t>0\). Each updated coordinate becomes full and remains full during this phase, so there are at most \(\tau\) moves.

At termination, \(U_t<\mu_t\) implies \(h_t(U)\le0\). The induction establishing that \(U\) bounds every finitely reachable state is valid:

• Decreases preserve the bound.
• Increases cannot exceed a coordinate already full in \(U\).
• If \(U_t<\mu_t\), monotonicity gives \(h_t(x)\le h_t(U)\le0\) whenever \(x\le U\), preventing any increase of that coordinate.

This reasoning covers partial moves as well as full-coordinate moves.

Every second-phase update is also legal. Exposure differences weakly decrease throughout that phase. A coordinate set to zero therefore retains a negative exposure difference; a coordinate that was below capacity at \(U\) retains a nonpositive exposure difference. These observations exclude all increases at the final state. Termination excludes all decreases, so \(D\) is stable.

The domination argument for stable states is sound. If \(y\le z\), \(y\) is stable, and \(h_t(z)<0\), then \(h_t(y)<0\), forcing \(y_t=0\). Thus every second-phase update preserves domination of \(y\).

Consequently, \(D\) is reachable in at most \(2\tau\) moves and dominates every reachable stable state. The argument also covers zero moves, ties, and zero exposures.

• Optimistic endpoint and decision quantifiers

The existence conclusion follows because \(D\) itself is finitely reachable and stable.

Uniqueness follows from coordinatewise domination: if \(y\le D\) and their total black masses agree, every nonnegative difference \(D_t-y_t\) must vanish.

Therefore the original requirement—an optimistic endpoint exists and every optimistic endpoint meets the quota—is equivalent to the stated condition that the unique endpoint \(D\) meets the quota. No attainment or universal-quantifier issue remains.

• Source problem and parameter bounds

The invoked source theorem is the standard \(\mathrm{NP}\)-completeness of Vertex Cover: given a finite simple undirected graph and an integer bound \(k\), decide whether some set of at most \(k\) vertices meets every edge. Karp’s cited paper identifies Node Cover among its complete problems. [Karp, 1972](https://people.seas.harvard.edu/~madhusudan/courses/Fall2020/Lectures/L19-after.pdf)

The restriction to \(n\ge2\), \(r\ge1\), and \(1\le k<n\) is legitimate: excluded instances have immediately decidable answers and can be replaced by fixed instances satisfying the restrictions.

The parameter calculations check out:

• \(\eta/c=1/(8N)\), so \(0<\eta<c\).
• \(N(c+2\eta)=1/16+1/(64N)<1/2\), giving \(\kappa<1/2\).
• The budget separation is exactly \((k+1)(c-\eta)-\kappa=c-(3k+1)\eta\).
• Since \(k\le N\) and \(N\ge2\), the displayed separation is strictly positive.
• The definition of \(H\) gives \(B=H-n-rM\ge M=n+1\).

All quantities have polynomial encoding length.

• Validity and size of the constructed instance

The masses are positive dyadic rationals, and their sum is \((n+rM+B)/H=1\). The construction uses exactly \(\tau=n+r+1\) supported types.

Every listed exposure is positive, symmetric, and at most one. In particular, \(B\ge3\), \(0<1-2c<1\), and \(0<\varepsilon<1\). Only the masses are claimed to be dyadic; the possibly nondyadic exposures are allowed by the task.

The budget satisfies \(K>0\). The quota satisfies \(0<Q<1\), since \(B+rM=H-n\) and \(n>0\).

Counting unordered positive pairs, including diagonals, gives:

• \(n+1\) diagonal pairs;
• \(n\) vertex–anchor pairs;
• \(2r\) edge–vertex pairs;
• \(r\) edge–anchor pairs.

Hence \(m=2n+3r+1\), and \(3\tau-m=n+2>0\). The claimed sparsity and polynomial construction size are correct.

• Exposure calculations

Rescaling by \(y_t=Hx_t\) preserves eligibility signs.

The vertex formula correctly includes its diagonal contribution, anchor contribution, and incident edge contributions. Bounding the anchor by capacity and each incident edge contribution by \(\varepsilon M\) yields inequality (1), because \(\varepsilon rM=2\eta\).

With the anchor full, bounding incident edge contributions below by \(-\varepsilon M\) yields inequality (2).

The edge formula correctly has no diagonal term. Its anchor contribution is at most \(\varepsilon\), yielding inequality (3); equality holds when the anchor is full.

These bounds hold over the entire state box, including fractional states.

• Completeness

The proposed bribe respects every coordinate bound and costs at most \(K\).

Each chosen vertex initially has exposure difference at least \(2\eta>0\), so its full increase is legal. Subsequent increases cannot invalidate another chosen vertex’s eligibility.

After the chosen vertices are full, every edge has endpoint black mass totaling at least one. With the anchor full, its exposure difference is therefore at least \(\varepsilon>0\), making every proposed edge increase legal.

The final stability checks are correct:

• Unchosen vertices are zero with strictly negative exposure difference.
• Chosen vertices are full with strictly positive exposure difference.
• Edge types are full with strictly positive exposure difference.
• The anchor is full, and its stated lower bound is positive because \(B\ge n+1\) and \(B^2>n+2\eta\).

These signs exclude all eligible moves at the relevant boundaries.

The resulting stable state has total black mass \((B+rM+|C|)/H\ge Q\). The greatest-endpoint lemma then establishes success under the task’s optimistic semantics.

• Soundness for arbitrary real bribes

The proof correctly allows bribing vertices, edges, and the initially black anchor. The initial unnormalized coordinates and the bound \(\sum_t\beta_t\le\kappa\) are correct.

For every vertex becoming full in the increasing phase, inequality (1) and strict eligibility imply \(\beta_v>c-\eta\). Before its update, its coordinate is still its initial value, because that phase only performs full increases. The separately handled initially full case is also valid.

The strict budget separation therefore gives \(|S|\le k\).

If an edge has neither endpoint in \(S\), both endpoint coordinates remain their initial bribe masses throughout the increasing phase. Thus \(U_u+U_v\le\kappa<1/2\), and inequality (3) gives a strictly negative edge exposure difference at \(U\).

Every reachable state lies below \(U\). Hence every reachable stable state has strictly negative exposure difference at that edge and must have zero black mass there.

The resulting upper bound on total black mass is correct: allowing the anchor and every vertex to be full, and all other edges to be full, gives \((B+(r-1)M+n)/H=Q-1/H<Q\).

Consequently, every successful bribe yields a vertex cover of size at most \(k\). Neither fractional bribes nor bribes to auxiliary types evade this argument.

• Polynomial-size rational certificates

For a recorded execution, every intermediate coordinate is either its initial affine expression in the bribe variables, zero, or its capacity. Therefore move eligibility, positive move size, budget, quota, and the recorded final stability conditions are rational linear constraints.

The three final-coordinate cases express stability correctly:

• At zero, only increases need exclusion, requiring \(h_t(w)\le0\).
• At capacity, only decreases need exclusion, requiring \(h_t(w)\ge0\).
• Strictly inside the interval, both directions need exclusion, requiring \(h_t(w)=0\).

Replacing all strict conditions by a common positive slack is valid because a real witness satisfies finitely many strict inequalities.

The resulting polytope is bounded by the bribe bounds and \(0\le s\le1\). A linear objective on a nonempty bounded polytope attains its maximum at an extreme point, including when the polytope is lower dimensional. Thus the positive optimum has an extreme-point witness.

The determinant argument applies: the dimension, number of constraints, and rational coefficient lengths are polynomially bounded. Clearing denominators and applying Cramer’s rule gives polynomial-size rational coordinates.

The rational witness retains a legal finite execution ending in a stable state meeting the quota. That suffices for success by the endpoint lemma. It does not require an additional assertion that this recorded execution remains the canonical execution after rationalization.

The membership-in-\(\mathrm{NP}\) argument is therefore sound.

• Verification and deterministic running times

For a rational certificate, monotonicity during each phase permits maintaining exposure differences and eligible coordinates with the claimed arithmetic-operation bound. Each coordinate changes at most once per phase, and each positive pair causes only constantly many exposure updates.

Exact arithmetic has polynomial bit cost in \(L+C\), so \(O((m+\tau)\operatorname{poly}(L+C))\) is a valid polynomial verification bound. Reading a dense encoding and constructing adjacency lists is also covered by the polynomial dependence on \(L\).

Each ordered move list is an ordered subset of the \(\tau\) coordinates. Its count is at most \(3\tau!\); combining two such lists with \(3^\tau\) final statuses gives the stated bound \(9\cdot3^\tau(\tau!)^2\).

The associated rational linear programs have polynomial size. Enumeration therefore gives the claimed running time \(2^{O(\tau\log(\tau+1))}\operatorname{poly}(m,\tau,L)\). Any accepted pattern describes a legal reachable stable state meeting the quota, while a successful canonical execution supplies an enumerated pattern.

The output resolves the assigned continuous problem and establishes its stronger \(\mathrm{NP}\)-completeness claim. No repair or additional clarification is needed.

⟨structured verdict parsed — rendered above⟩