Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 6 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateCAUTIOUS-OM is Σp 2-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Input a finite set of exposure types \(T\), rational masses \(\mu_t>0\) summing to \(1\), a symmetric rational contact matrix \(A\), thresholds \(\theta_t\), initial black, white, and gray masses \(z_t^b,z_t^w,z_t^g\) summing to \(\mu_t\), per-turn mass capacities \(r_b,r_w\), and target \(\alpha\). Assume every type has positive total exposure. Type \(t\) is eligible for opinion \(p\in\{b,w\}\) when \(\sum_u A_{tu}z_u^p\ge\theta_t\sum_u A_{tu}\mu_u\). On each turn, a polynomial-size rational-circuit policy chooses transfers from currently eligible gray types, bounded by their available gray mass and totaling the lesser of the player's capacity and the total eligible gray mass; apply the transfers, then alternate turns starting with black until no player can move. Decide whether there exists a black policy such that, for every white policy, terminal black mass is at least \(\alpha\).
A society is given by its support: a list of \(\tau\) exposure types \(T\) with positive binary-rational masses \(\mu_t\), summing to \(1\). The support size counts listed types, not all possible types. Let \(m=\tau\) be the contact-matrix dimension and \(L\) the total input bit length.
Input a symmetric nonnegative rational matrix \(A\), rational thresholds \(\theta_t\in[0,1]\), nonnegative rational initial masses \(z_t^b,z_t^w,z_t^g\) with \(z_t^b+z_t^w+z_t^g=\mu_t\), positive rational capacities \(r_b,r_w\), rational target \(\alpha\in[0,1]\), and a unary policy-description bound \(s\). Require \(\sum_u A_{tu}\mu_u>0\) for every \(t\); diagonal contacts are allowed.
At state \(z\), let \(E_p(z)=\{t\in T:z_t^g>0,\ \sum_u A_{tu}z_u^p\ge\theta_t\sum_u A_{tu}\mu_u\}\), for \(p\in\{b,w\}\).
Players alternate turns, starting with black. A turn starts with remaining capacity \(c=r_p\). The player's policy outputs rational transfers \(x_t\), with \(0\le x_t\le z_t^g\), \(x_t=0\) outside \(E_p(z)\), and \(\sum_t x_t=\min\{c,\sum_{t\in E_p(z)}z_t^g\}\). Simultaneously set \(z_t^p\leftarrow z_t^p+x_t\), \(z_t^g\leftarrow z_t^g-x_t\), and \(c\leftarrow c-\sum_t x_t\).
Recompute eligibility and repeat within that turn until capacity is exhausted or no eligible gray mass remains. Empty turns pass; play ends when neither player has eligible gray mass. Adopted opinions never change.
A policy is a deterministic circuit depending only on the current masses and remaining turn capacity, with total binary description length at most \(s\). Gates perform exact rational arithmetic, comparisons, and conditional selection; division must be defined, and outputs must satisfy the transfer constraints at every admissible rational state. Both players have the same bound.
Is deciding whether some black policy guarantees terminal black mass \(\sum_t z_t^b\ge\alpha\) against every white policy solvable in polynomial time, or is it NP-hard? State running times in \(m,\tau,L,s\) and any numerical capacity dependence.
The discrete cautious opinion-maximization problem with compact, configuration-dependent strategies is \(\Sigma_2^p\)-complete, hence NP-hard ([source](https://doi.org/10.3233/FAIA230248)). No complexity result for this precise mass game was located in the literature search.
The decision problem is \(\mathrm{NP}\text{-hard}\), even when:
Consequently, a decision algorithm polynomial in \(m,\tau,L,s,1/r_b,1/r_w\) would imply \(\mathrm{P}=\mathrm{NP}\). The proof explicitly constructs policies valid at every admissible rational state.
We use the classical \(\mathrm{NP}\)-complete CLIQUE problem: given a simple undirected graph \(G=(V,E)\) and an integer \(k\), decide whether \(G\) contains a clique of size \(k\). See [Karp, *Reducibility among Combinatorial Problems*](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
Write \(n=|V|\), \(\ell=|E|\), and \(q=\binom{k}{2}\). We may restrict to instances satisfying
\(\displaystyle 2\le k\le n,\qquad \ell\ge q.\)
Indeed, the excluded cases are immediately decidable. An excluded NO instance can be replaced by the four-vertex star with \(k=3\), which satisfies these restrictions and contains no such clique; an excluded YES instance can be replaced by a triangle with \(k=3\). Thus this restriction preserves hardness.
Create the following listed types:
Set
\(\displaystyle m=\tau=n+\ell+1,\qquad h=\lceil\log_2m\rceil,\qquad \delta=2^{-h}.\)
Every vertex and edge type has mass \(\delta\). The anchor has mass
\(\displaystyle \mu_a=1-(n+\ell)\delta=1-(m-1)\delta.\)
Since \(2^h\ge m\), we have \(\mu_a\ge\delta>0\). These masses sum to one.
Initially, the anchor is entirely black; every other type is entirely gray. All initial white masses are zero.
Define the symmetric contact matrix by
\(\displaystyle A_{aa}=1,\qquad A_{vv}=1\quad(v\in V),\)
and, for each edge \(\{u,v\}\in E\),
\(\displaystyle A_{e_{uv},a}=A_{a,e_{uv}}=A_{e_{uv},u}=A_{u,e_{uv}}=A_{e_{uv},v}=A_{v,e_{uv}}=1.\)
All other entries are zero. Set
\(\displaystyle \theta_a=\theta_v=0,\qquad \theta_{e_{uv}}=1.\)
Every contact row has positive mass: the anchor and vertex rows have positive diagonal contributions, while every edge row has total contact mass \(\mu_a+2\delta>0\).
Finally, set
\(\displaystyle r_b=k\delta,\qquad r_w=1,\qquad \alpha=\mu_a+(k+q)\delta.\)
The target is admissible because
\(\displaystyle 1-\alpha=(n-k+\ell-q)\delta\ge0.\)
The policy bound will be fixed in Section 3.
The anchor stays entirely black throughout play because adopted opinions never change.
For an edge type \(e_{uv}\), its black exposure is therefore
\(\displaystyle \sum_t A_{e_{uv},t}z_t^b=\mu_a+z_u^b+z_v^b.\)
Its threshold is \(\mu_a+2\delta\). Since \(z_u^b,z_v^b\le\delta\), a gray edge type is black-eligible exactly when
\(\displaystyle z_u^b=z_v^b=\delta.\)
Thus both endpoint types must be entirely black.
Conversely, its white exposure always satisfies
\(\displaystyle \sum_t A_{e_{uv},t}z_t^w=z_u^w+z_v^w\le2\delta<\mu_a+2\delta.\)
No edge type is ever white-eligible.
Every vertex type with positive gray mass is eligible for both players because its threshold is zero.
Initially, black’s eligible types are exactly the vertex types. Their total gray mass is \(n\delta\). Since \(k\le n\), the first transfer must satisfy
\(\displaystyle 0\le x_v\le\delta,\qquad \sum_{v\in V}x_v=k\delta.\)
This transfer exhausts black’s capacity, so black cannot adopt newly eligible edge masses during the same turn.
Let
\(\displaystyle S=\{v\in V:x_v=\delta\}.\)
Because each vertex in \(S\) receives mass \(\delta\), we have \(|S|\le k\). This conclusion allows arbitrary fractional transfers to the other vertices.
At white’s first turn, the eligible gray types are exactly the remaining gray vertex types. Their total mass is
\(\displaystyle \sum_{v\in V}(\delta-x_v)=(n-k)\delta<1.\)
White’s capacity is one. The transfer rule therefore forces white to adopt all this mass. Componentwise, this follows because each transfer is at most its vertex’s gray mass and their sum equals the sum of those gray masses.
Afterward, every vertex has zero gray mass, and its black mass remains \(x_v\). White has no eligible gray type for the rest of play.
The black-eligible edge types are now exactly those whose two endpoints belong to \(S\). Their eligibility cannot change: their contact rows involve only the fixed anchor and the now fixed vertex masses.
Let \(e_G(S)\) denote the number of edges induced by \(S\). Black must eventually adopt all \(e_G(S)\delta\) eligible edge mass. Each subsequent black turn adopts the smaller of its capacity and the remaining eligible mass, so this requires at most
\(\displaystyle \left\lceil\frac{e_G(S)}{k}\right\rceil\)
additional black turns. All other edge types remain gray.
Consequently, for every pair of valid policies, the terminal black mass is exactly
\(\displaystyle B_{\mathrm{term}}=\mu_a+k\delta+e_G(S)\delta.\)
In particular, fractional first-turn transfers cannot compensate for missing induced edges: the first-turn black increment is always \(k\delta\).
We now verify the policy requirement at every admissible rational state, rather than only along the constructed play.
For either player \(p\), fix any ordering \(t_1,\ldots,t_m\) of the types. Define the available mass
\(\displaystyle a_t^p(z)= \begin{cases} z_t^g,&t\in E_p(z),\\ 0,&t\notin E_p(z). \end{cases}\)
For our instances, this can be computed with a constant number of gates per type:
\(\displaystyle z_a^p+z_u^p+z_v^p\ge\mu_a+2\delta\),
and select zero otherwise.
These formulas use the *current* anchor mass. Hence they remain correct even at admissible states other than those reachable from our initial state.
Starting with \(d_0=c\), let
\(\displaystyle x_{t_j}=\min\{a_{t_j}^p,d_{j-1}\},\qquad d_j=d_{j-1}-x_{t_j}\quad(1\le j\le m).\)
Each minimum uses a comparison and conditional selection. No division occurs.
For every admissible state and \(c\ge0\), induction gives
\(\displaystyle d_j=\max\left\{c-\sum_{i=1}^j a_{t_i}^p,0\right\}.\)
Therefore the outputs are nonnegative, bounded by the corresponding gray masses, and zero outside eligibility. Moreover,
\(\displaystyle \sum_t x_t=c-d_m =\min\left\{c,\sum_{t\in E_p(z)}z_t^g\right\}.\)
Thus these are globally valid policies depending only on the current masses and remaining capacity.
They use \(O(m)\) gates. Under a standard binary encoding of indexed gates, their descriptions have length \(O(m\log(m+2))\): wire indices require \(O(\log m)\) bits, and the rational constants require \(O(\log m)\) bits.
Choose, uniformly for the reduction,
\(\displaystyle s=Cm\lceil\log_2(m+2)\rceil,\)
where the fixed constant \(C\) covers this encoding. This bound accommodates every priority ordering for both players. In particular, valid white policies exist within the bound.
If \(G\) contains a clique of size \(k\): black uses the valid priority policy that places those \(k\) vertex types first. Its first transfer adopts each of them completely. Thus \(S\) is that clique, and against every valid white policy,
\(\displaystyle B_{\mathrm{term}}=\mu_a+k\delta+\binom{k}{2}\delta=\alpha.\)
If a black policy guarantees the target: take any valid white policy within the bound. The outcome formula implies
\(\displaystyle e_G(S)\ge q=\binom{k}{2}.\)
But \(|S|\le k\), and simplicity of the graph gives
\(\displaystyle e_G(S)\le\binom{|S|}{2}\le\binom{k}{2}.\)
Since \(k\ge2\), equality forces \(|S|=k\) and every pair in \(S\) to be an edge. Hence \(S\) is a clique of size \(k\).
This proves the required equivalence and therefore \(\mathrm{NP}\)-hardness.
The reduction uses exactly \(m=\tau=n+\ell+1=O(n^2)\) listed types. With the matrix represented explicitly,
\(\displaystyle s=O(\tau\log(\tau+2)),\qquad L=O(m^2+\tau\log(\tau+2)+s)=O(m^2).\)
The instance can be constructed in \(O(m^2+\tau\log(\tau+2)+s)\) bit operations under standard encodings, hence in \(O(n^4)\) time.
Every numerical input has numerator and denominator bounded by \(2m\), since \(2^h<2m\). Also,
\(\displaystyle \frac1{r_b}=\frac{2^h}{k}<2m,\qquad \frac1{r_w}=1.\)
Thus allowing polynomial numerical dependence on inverse capacities does not yield a polynomial decision algorithm unless \(\mathrm{P}=\mathrm{NP}\).
These bounds concern execution of given valid policies, not the decision problem.
Let
\(\displaystyle G_0=\sum_t z_t^g,\qquad r_{\min}=\min\{r_b,r_w\}.\)
Every positive transfer batch has one of two properties:
Therefore the number of positive transfer batches is at most
\(\displaystyle \tau+\left\lfloor\frac{G_0}{r_{\min}}\right\rfloor.\)
Two consecutive empty turns imply termination: neither changes the state, so neither player has eligible gray mass. Consequently, the number of turns is also \(O(\tau+1+G_0/r_{\min})\).
Set
\(\displaystyle H=1+\tau+\left\lfloor\frac{G_0}{r_{\min}}\right\rfloor.\)
Computing eligibility directly costs \(O(m\tau)\) rational operations per state, while evaluating a policy costs \(O(s)\) gates. Simulation therefore uses
\(\displaystyle O\bigl((m\tau+s)H\bigr)\)
rational arithmetic and comparison operations.
This is not automatically a polynomial bit-time bound. For ordinary binary arithmetic gates \(+,-,\times,\div\), one circuit evaluation can increase rational bit lengths by a factor \(2^{O(s)}\). Summing the \(\tau\) transfers adds a further factor \(O(\tau+1)\). Starting from input bit lengths at most \(L\), iteration over at most \(H\) updates therefore gives the conservative exact simulation bound
\(\displaystyle 2^{O(H(s+\log(\tau+1)))}\operatorname{poly}(m,\tau,L,s,H). \)
The proof establishes the requested hardness classification. It does not assert membership in \(\mathrm{NP}\) or \(\Sigma_2^p\), nor require an algorithm for checking global validity of arbitrary policy circuits.
⟨structured verdict parsed — rendered above⟩
The prover establishes the claimed \(\mathrm{NP}\)-hardness for the precise mass game. The reduction respects the support-size convention, symmetry, rational encoding, simultaneous transfers, and globally valid bounded policy requirements. I found no major or minor mathematical issues.
The cited theorem is that CLIQUE on simple undirected graphs is \(\mathrm{NP}\)-complete: given a graph and an integer \(k\), decide whether it contains \(k\) pairwise adjacent vertices. This is the problem used in [Karp’s paper](https://www2.seas.gwu.edu/~simhaweb/champalg/tsp/papers/KarpOriginal.pdf).
Restricting to \(2\le k\le n\) and \(\ell\ge\binom{k}{2}\) preserves hardness as written. The excluded instances are immediately decidable. Both replacement instances satisfy the restrictions: the four-vertex star has three edges and no triangle, while the triangle supplies a YES instance.
The construction lists exactly \(n+\ell+1\) types, so \(m=\tau=n+\ell+1\) correctly counts the support.
With \(h=\lceil\log_2m\rceil\) and \(\delta=2^{-h}\), the inequality \(m\le2^h\) gives \(\mu_a\ge\delta>0\). The masses sum to one, and every initial color decomposition satisfies the required type-mass identity.
There is no use of unlisted exposure types.
The matrix is symmetric and has only nonnegative entries in \(\{0,1\}\). The specified diagonal entries make the anchor and vertex contact rows positive; each edge row has contact mass \(\mu_a+2\delta>0\).
All thresholds are admissible. Both capacities are positive. The target satisfies \(\alpha\le1\) because
\[
1-\alpha=(n-k+\ell-q)\delta\ge0.
\]
Its nonnegativity is immediate from its definition.
The anchor remains entirely black on every reachable state. An edge type contacts exactly the anchor and its endpoints, so the stated black-exposure formula is correct.
Since each endpoint has black mass at most \(\delta\), reaching the threshold \(\mu_a+2\delta\) requires both endpoints to have black mass exactly \(\delta\). Conversely, those endpoint masses attain the threshold.
White exposure is at most \(2\delta\), strictly below the threshold because \(\mu_a>0\). Thus no edge becomes white-eligible during the constructed play.
Every vertex with positive gray mass is eligible for either player because its threshold is zero. The anchor itself has no gray mass.
Initially, precisely the vertices are eligible. Their total gray mass is \(n\delta\), which is at least \(r_b=k\delta\). Consequently, the mandatory first transfer totals exactly \(k\delta\) and exhausts capacity.
Newly eligible edges cannot receive mass in that simultaneous batch: eligibility is evaluated before the transfer. They also cannot receive another batch in that turn because the capacity is exhausted.
The bound \(|S|\le k\) follows from the transfer total and the definition of \(S\). It does not assume integral transfers.
White’s eligible gray mass consists exactly of the remaining vertex mass, totaling \((n-k)\delta<1\). Since its capacity is one, the transfer rule forces adoption of all that mass, componentwise.
If \(n=k\), this mass is zero and white passes; the subsequent conclusions still hold.
Thereafter, all vertex masses are fixed. Exactly the edges induced by \(S\) remain black-eligible, and none is white-eligible. Their eligibility is unaffected by adopting other edge masses because edge rows contain no edge contacts.
Positive black capacity forces eventual adoption of all eligible edge mass. The stated bound of \(\lceil e_G(S)/k\rceil\) additional black turns is correct, including the case \(e_G(S)=0\).
Therefore the terminal-mass identity
\[
B_{\mathrm{term}}=\mu_a+k\delta+e_G(S)\delta
\]
holds for every pair of valid policies.
The availability formulas correctly compute eligible gray mass at arbitrary admissible states. In particular, the edge formula uses the current player-colored anchor mass, rather than assuming the reachable initial anchor configuration.
Omitting a separate positive-gray test causes no discrepancy: a type with zero gray mass contributes zero availability regardless of the comparison.
The priority allocation recurrence and its stated invariant are valid for every nonnegative remaining capacity. They establish all component bounds, eligibility restrictions, and the mandatory total-transfer equality.
These circuits use no division. Their linear gate count and \(O(m\log(m+2))\) description length are consistent with the explicitly stated standard indexed-gate encoding. A fixed encoding constant suffices for every ordering. Thus the common unary bound accommodates both a winning black policy when a clique exists and at least one valid white policy.
In the YES direction, putting the clique vertices first fully adopts precisely those vertices in the first batch. The terminal-mass identity then gives \(\alpha\), independently of white’s policy.
In the reverse direction, choosing any valid bounded white policy is legitimate because Section 3 establishes that such policies exist. A guaranteeing black policy must therefore produce \(e_G(S)\ge\binom{k}{2}\).
The simple-graph bound and \(|S|\le k\) force equality. For \(k\ge2\), a smaller set cannot attain \(\binom{k}{2}\) edges. Thus \(S\) has exactly \(k\) vertices and every pair is adjacent.
This establishes the required equivalence with the existential-black, universal-white decision question.
The constructed game’s rational parameters are dyadic. Their numerators and denominators are bounded by \(2m\), using \(2^h<2m\) and the previously verified parameter ranges.
The dense matrix, remaining parameters, and unary policy bound have the stated total size \(L=O(m^2)\). The construction is polynomial, with the stated \(O(n^4)\) bound under the specified standard encodings.
Both inverse capacities are polynomially bounded. Consequently, the claimed consequence for algorithms polynomial in \(m,\tau,L,s,1/r_b,1/r_w\) follows.
The batch classification is exhaustive. A positive batch either exhausts capacity or consumes all currently eligible gray mass while leaving capacity.
Capacity-exhausting turns each transfer at least \(r_{\min}\). Every batch of the second kind permanently exhausts at least one previously positive gray type. The resulting batch bound is correct.
Two consecutive empty turns certify termination because neither changes the state. The turn bound consequently follows.
The rational-operation simulation bound correctly accounts for eligibility computation, policy evaluation, and state updates. The separate bit-time bound is conservative and valid for the ordinary binary arithmetic gates explicitly specified there. It does not improperly equate rational-operation complexity with polynomial bit complexity.
The output resolves the requested hardness classification. Its simulation bounds concern given valid policies, and it correctly makes no unsupported claim about complexity-class membership or checking arbitrary policies for global validity. No additional clarification is needed.
⟨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.