Answer: Both the unpointed and pointed defensive-coalition existence problems are \(\mathrm{NP}\)-complete.
Theorem 11 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateDEFPALL and DEFALL are NP-complete. The reduction is based on the NP-hardness of a well-known variation of the SATISFIABILITY problem, namely NAE-3SAT, see [Schaefer, 1978]. According to Schaeffer, NAE-3SAT can be defined as a coloring problem as follows: NOT-ALL-EQUAL 3-SATISFIABILITY (NAE-3SAT) Input: A base set X, a collection of sets C1, . . . , Cm ⊆X, each having at most three members Problem: Is there a mapping A : X →{0, 1} such that A(Ci) = {0, 1} for all 1 ≤i ≤m? From the coloring point of view, this means that X is colored with two colors such that no set Ci is all one color.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many types \(T\), positive rational masses \(\mu_t\) summing to \(1\), and a symmetric relation \(\sigma_{tu}\in\{+,-,0\}\) shared by every pair of distinct members of types \(t,u\), does there exist a nonzero coalition mass vector \(x\) with \(0\le x_t\le\mu_t\) such that, for each \(t\) with \(x_t>0\), \(P_t(x)\ge N_t^{\mathrm{in}}(x)\) and \(P_t(x)\ge N_t^{\mathrm{out}}(x)\), where \(P_t(x)=\sum_{u:\sigma_{tu}=+}x_u\), \(N_t^{\mathrm{in}}(x)=\sum_{u:\sigma_{tu}=-}x_u\), and \(N_t^{\mathrm{out}}(x)=\sum_{u:\sigma_{tu}=-}(\mu_u-x_u)\)? In the pointed version, given \(t^\star\in T\), require also \(x_{t^\star}>0\).
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
The input includes a symmetric matrix \(\sigma\in\{+,-,0\}^{T\times T}\): friendship, enmity, or no relation. Diagonal entries specify relations between distinct members of the same type and may take any of these values.
Mass is divisible and atomless; an individual's own mass is zero, so there is no additive self-defense term. Let \(m\) count nonzero entries on or above the matrix diagonal, and let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
For \(x\in\mathbb R^T\), define \(P_t(x)=\sum_{u:\sigma_{tu}=+}x_u\), \(N_t^{\mathrm{in}}(x)=\sum_{u:\sigma_{tu}=-}x_u\), and \(N_t^{\mathrm{out}}(x)=\sum_{u:\sigma_{tu}=-}(\mu_u-x_u)\), including diagonal contributions.
A defensive coalition satisfies \(0\le x_t\le\mu_t\), \(\sum_t x_t>0\), and, for every \(t\) with \(x_t>0\), both \(P_t(x)\ge N_t^{\mathrm{in}}(x)\) and \(P_t(x)\ge N_t^{\mathrm{out}}(x)\). The pointed variant additionally takes \(t^\star\in T\) and requires \(x_{t^\star}>0\).
For each of the unpointed and pointed defensive-coalition existence problems, is it solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite simple signed graphs, existence of a nonempty defensive alliance, with or without a prescribed vertex, is NP-complete; each member's number of positive neighbors inside plus one must dominate its negative neighbors both inside and outside. [Source](https://arxiv.org/html/2309.06801v2)
No result settling exactly the atomless mass formulation above was identified in the literature search.
Both the unpointed and pointed problems are \(\mathrm{NP}\)-complete. Consequently, a polynomial-time algorithm in \(m,\tau,L\) for either problem would imply \(\mathrm{P}=\mathrm{NP}\).
The reduction below uses only positive dyadic masses and has \(m=O(\tau)\). It uses the positive diagonal entries permitted in the question.
Suppose a type \(t\) has no friends and has at least one enemy. Since all type masses are positive, its total enemy mass is positive.
If \(x_t>0\), its defensive inequalities, with \(P_t(x)=0\), require both \(N_t^{\mathrm{in}}(x)=0\) and \(N_t^{\mathrm{out}}(x)=0\). But
\[ N_t^{\mathrm{in}}(x)+N_t^{\mathrm{out}}(x) =\sum_{u:\sigma_{tu}=-}\mu_u>0, \]
a contradiction. Thus such a type has zero mass in every defensive coalition.
Binary PARTITION takes positive integers \(a_1,\ldots,a_n\) and asks whether some index set \(I\) satisfies \(\sum_{i\in I}a_i=W/2\), where \(W=\sum_{i=1}^n a_i\). We use its classical \(\mathrm{NP}\)-hardness; see the [MIT lectures on partition problems](https://courses.csail.mit.edu/6.5440/fall23/lectures/L02.html?notes=2).
Choose \(D\) to be the smallest power of two strictly exceeding \(6W+2\). Introduce the following types, with actual masses \(\mu_t=w_t/D\):
| Type | Raw mass \(w_t\) |
|---|---:|
| Balancing type \(c\) | \(1\) |
| Helper \(h\) | \(W\) |
| Item \(v_i\), for each \(i\) | \(2a_i\) |
| Blocker \(b_i\), for each \(i\) | \(2a_i\) |
| Helper blocker \(b_h\) | \(W+1\) |
| Padding type \(r\) | \(D-(6W+2)\) |
All masses are positive. The raw masses excluding \(r\) sum to \(6W+2\), so the actual masses sum to one. They are dyadic rationals.
Specify the symmetric relations as follows:
For the pointed instance, prescribe \(t^\star=c\).
Work in coordinates \(y_t=Dx_t\). Multiplying every defensive inequality by \(D\) gives exactly the same conditions with raw masses \(w_t\) and bounds \(0\le y_t\le w_t\).
Each \(b_i\), \(b_h\), and \(r\) has no friends and has an enemy of positive mass. Section 1 therefore gives
\[ y_{b_i}=y_{b_h}=y_r=0 \]
in every defensive coalition.
Suppose \(y_{v_i}>0\). Its positive diagonal gives positive-neighbor mass \(y_{v_i}\). Its enemies are \(c\) and \(b_i\). Because \(b_i\) is outside, the outside-defense inequality is
\[ y_{v_i}\ge (1-y_c)+2a_i. \]
Together with \(y_{v_i}\le 2a_i\) and \(y_c\le1\), this forces
\[ y_{v_i}=2a_i,\qquad y_c=1. \]
Thus every item contributes either zero or its entire mass.
Suppose \(y_h>0\). Its friends are its own type and \(c\), while its only enemy is the excluded blocker \(b_h\). Hence outside defense requires
\[ y_h+y_c\ge W+1. \]
The bounds \(y_h\le W\) and \(y_c\le1\) force
\[ y_h=W,\qquad y_c=1. \]
After excluding blockers and padding, a nonempty coalition contains \(c\), \(h\), or some item. The preceding two arguments show that participation by \(h\) or an item forces \(y_c=1\). Therefore every nonempty defensive coalition has \(y_c>0\).
Put \(Z=\sum_i y_{v_i}\). At the active balancing type, the positive-neighbor mass is \(y_h\), while the inside and outside enemy masses are respectively \(Z\) and \(2W-Z\). Its two inequalities are
\[ y_h\ge Z,\qquad y_h\ge2W-Z. \]
Adding them gives \(y_h\ge W\). Since \(y_h\le W\), necessarily \(y_h=W\), and the two inequalities then give \(Z=W\).
Every item mass is either zero or \(2a_i\). Consequently, for \(I=\{i:y_{v_i}>0\}\),
\[ 2\sum_{i\in I}a_i=Z=W. \]
Thus existence of any defensive coalition implies a yes-instance of PARTITION.
Conversely, suppose \(\sum_{i\in I}a_i=W/2\). Set \(y_c=1\), \(y_h=W\), and \(y_{v_i}=2a_i\) for \(i\in I\); set every other coordinate to zero.
For each active type, the three relevant masses are:
| Active type | Positive inside | Negative inside | Negative outside |
|---|---:|---:|---:|
| \(c\) | \(W\) | \(W\) | \(W\) |
| \(h\) | \(W+1\) | \(0\) | \(W+1\) |
| \(v_i\), \(i\in I\) | \(2a_i\) | \(1\) | \(2a_i\) |
Both defensive inequalities hold in every row, since \(a_i\) is a positive integer. The coalition is nonempty and contains \(c\).
We have therefore proved the equivalence
\[ \text{PARTITION is yes} \iff \text{an unpointed coalition exists} \iff \text{a coalition containing }c\text{ exists}. \]
This proves \(\mathrm{NP}\)-hardness of both variants.
The construction has \(\tau=2n+4\) and \(m=3n+4\), including the positive diagonal entries.
Because \(\log D=O(\log(W+2))\), its output length and construction time are \(O(n^2+n\log(W+2))\) with an explicitly written matrix. This is polynomial in the binary PARTITION input length.
Strict positivity requires a witness-size argument.
Fix a nonempty candidate support \(S\subseteq T\). Define
\[ d_t=\sum_{u:\sigma_{tu}=-}\mu_u. \]
Consider the linear program with variables \(x_t\) and \(\varepsilon\), maximizing \(\varepsilon\), subject to:
\[ P_t(x)-N_t^{\mathrm{in}}(x)\ge0,\qquad P_t(x)+N_t^{\mathrm{in}}(x)\ge d_t. \]
The last inequality is exactly outside defense because \(N_t^{\mathrm{out}}(x)=d_t-N_t^{\mathrm{in}}(x)\).
A coalition with support exactly \(S\) exists if and only if this program has positive optimum. Indeed, a coalition permits \(\varepsilon=\min_{t\in S}x_t>0\), while any feasible solution with positive \(\varepsilon\) has exactly that support.
The feasible region is bounded, and all coefficients and right-hand sides are rational. If the optimum is positive, the fundamental theorem of linear programming supplies an optimal vertex.
To bound its encoding length, let \(Q\) be the product of the input mass denominators. Its bit length is \(O(L)\). All constraint coefficients belong to \(\{-1,0,1\}\), and multiplying each right-hand side by \(Q\) produces an integer of absolute value at most \(Q\).
At a vertex, select \(\tau+1\) linearly independent tight constraints. Their integer coefficient matrix \(H\) satisfies, by Hadamard’s inequality,
\[ |\det H|\le(\tau+1)^{(\tau+1)/2}. \]
Cramer’s rule therefore represents every coordinate with common denominator \(Q|\det H|\). Each coordinate has numerator and denominator bit length
\[ b=O\bigl(L+\tau\log(\tau+1)\bigr). \]
Thus a yes-instance has a polynomial-size rational coalition certificate. The verifier checks bounds, nonemptiness, the defensive inequalities only at positive coordinates, and, in the pointed variant, positivity at \(t^\star\).
Using a common denominator and schoolbook integer arithmetic, verification takes \(O(L+(m+\tau)b^2)\) bit operations. Hence both problems belong to \(\mathrm{NP}\).
The reduction and certificate argument establish \(\mathrm{NP}\)-completeness for both variants.
For completeness, enumerating supports and solving the corresponding rational linear programs gives a deterministic running time of \(2^\tau\operatorname{poly}(m,\tau,L)\). In the pointed variant, only supports containing \(t^\star\) need be examined.
⟨structured verdict parsed — rendered above⟩
The output correctly establishes that both variants are \(\mathrm{NP}\)-complete. The reduction respects the atomless model, uses permitted diagonal relations, and works for both unpointed and pointed existence. The rational-certificate argument establishes membership in \(\mathrm{NP}\). I found no major or minor mathematical gaps.
The exclusion argument is correct. For a participating type with no friends, both nonnegative enemy sums must equal zero. Their sum equals the total enemy mass, which is strictly positive whenever the type has an enemy.
This reasoning also applies to diagonal enemy relations: the definitions still split that enemy type’s mass into inside and outside contributions. No self-defense term is introduced.
The reduction uses binary PARTITION with positive integers and unrestricted subset selection. Its classical weak \(\mathrm{NP}\)-hardness suffices; strong hardness is unnecessary. The cited [MIT lecture](https://courses.csail.mit.edu/6.5440/fall23/lectures/L02.html?notes=2) identifies two-partition and discusses the relevant weak-hardness distinction.
The constructed masses satisfy all input requirements:
Scaling by \(D\) preserves the bounds, participation conditions, and defensive inequalities exactly.
Every \(b_i\), \(b_h\), and \(r\) has no positive relation and at least one negative relation to a type of positive mass. Section 1 therefore applies to each of them, regardless of whether its enemies participate.
Their exclusion is fully justified.
For an active item, the stated outside-defense inequality is correct:
\[ y_{v_i}\ge 1-y_c+2a_i. \]
Its positive diagonal contributes \(y_{v_i}\). Its enemies are precisely \(c\) and the excluded \(b_i\).
The upper bounds force both \(y_{v_i}=2a_i\) and \(y_c=1\). Thus the claimed all-or-zero behavior of item coordinates follows.
Using only outside defense here is legitimate: this is a necessary-condition argument, while sufficiency is checked separately.
The helper’s positive mass is \(y_h+y_c\), including its permitted positive diagonal. Its only enemy is the excluded blocker of raw mass \(W+1\).
Consequently, outside defense requires
\[ y_h+y_c\ge W+1. \]
The bounds force \(y_h=W\) and \(y_c=1\), exactly as claimed.
Once blockers and padding are excluded, only \(c\), \(h\), and the items can participate. Participation by either the helper or an item forces \(c\) to participate. A coalition containing only \(c\) also has \(c\) active, so the case distinction is exhaustive.
At \(c\), the two enemy masses are correctly computed as \(Z\) and \(2W-Z\). The inequalities imply
\[ 2y_h\ge 2W. \]
Together with the helper’s upper bound, this gives \(y_h=W\), and the two original inequalities then force \(Z=W\).
Since every active item contributes exactly \(2a_i\), the resulting index set satisfies the PARTITION equation. This argument excludes all unintended nonempty coalitions.
The proposed coordinates obey every mass bound and include \(c\).
All three rows of the defense table are correct:
The item’s inside-defense inequality holds because \(a_i\ge1\). Inactive types require no defensive inequalities.
Thus both directions of the equivalence hold, including the pointed requirement. An odd value of \(W\) introduces no exception: the derived partition equation is then impossible, as required.
The stated counts are correct:
\[ \tau=2n+4,\qquad m=3n+4. \]
The count of \(m\) includes each specified diagonal once and each symmetric off-diagonal relation once.
The denominator has logarithmic bit length in \(W+2\). Writing the explicit matrix and all masses therefore has the claimed polynomial size and construction time. The reduction establishes hardness even when \(m=O(\tau)\).
For a fixed nonempty support, the linear program exactly represents the coalition conditions.
The outside-defense rewrite is valid, including diagonal contributions. A coalition with that support supplies a strictly positive minimum coordinate; conversely, positive \(\varepsilon\) forces every coordinate in the selected support to be positive.
The existence-versus-positive-optimum equivalence is therefore correct.
The feasible region is closed and bounded. In the positive-optimum case it is also nonempty. These hypotheses justify attainment of the linear objective at a vertex.
The coefficient claim is correct: positive and negative relations are mutually exclusive, so the defense rows have coefficients in \(\{-1,0,1\}\), including on the diagonal.
The denominator-clearing argument is valid. The product \(Q\) has bit length \(O(L)\), and every cleared right-hand side has absolute value at most \(Q\).
At a vertex, choosing \(\tau+1\) independent tight constraints is valid even if the polytope has lower dimension. Their coefficient matrix is nonsingular. The stated Hadamard bound and Cramer representation consequently apply.
The resulting coordinates have polynomial encoding length. Their bounded magnitudes also justify the claimed numerator bound. Strict positivity therefore creates no certificate-size obstruction.
A certificate using the common denominator supplied by the vertex argument can be checked within the stated schoolbook-arithmetic bound
\[ O\!\left(L+(m+\tau)b^2\right). \]
This covers checking coordinate bounds, participation, the defensive inequalities, and prescribed-type positivity.
The support-enumeration observation is also correct: rational linear programming decides whether each support’s optimum is positive in polynomial time.
The hardness and membership arguments together establish the claimed \(\mathrm{NP}\)-completeness of both variants.
No repair or additional clarification is needed for mathematical verifiability. The output resolves both assigned existence problems under the specified input encoding.
⟨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.