Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 4.2 — class: hardness
Given a finite role set \(J\), rational distribution \(\mu\) over types \(\theta=(j,r,z)\) with \(r:J\to\{0,1\}\), target flag \(z\), quotas \(q_1,q_0\in[0,1]\), and mass budget \(\lambda\), may one transfer at most \(\lambda\) mass of complete assessment rows \(r\) to rows \(r'\), preserving \(j,z\), so that every unit of target mass \(z=1\) is socially qualified under \(A_j(\mu')\ge q_1\) for self-approvers and \(1-A_j(\mu')<q_0\) for self-disapprovers?
Let \(J\) be a nonempty role set with \(m=|J|\). Types are \(\theta=(j,r,z)\), where \(j\in J\), \(r\in\{0,1\}^{J}\), and \(z\in\{0,1\}\) marks targets; \(r(k)\) assesses every individual of role \(k\), and \(r(j)\) is self-assessment.
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Masses sum to \(1\); \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length.
The input also contains binary rational quotas \(q_1,q_0\in[0,1]\) and budget \(\lambda\in(0,1]\). For any society \(\nu\), define \(A_k(\nu)=\sum_{(j,r,z)}\nu(j,r,z)r(k)\).
A type \((j,r,z)\) is socially qualified precisely when either \(r(j)=1\) and \(A_j(\nu)\ge q_1\), or \(r(j)=0\) and \(1-A_j(\nu)<q_0\). Assume positive target mass and positive initially unqualified target mass.
A permitted change splits each initial type's mass among arbitrary replacement rows \(r'\in\{0,1\}^{J}\), preserving \(j,z\). Formally, choose nonnegative real masses \(x_{\theta,r'}\) with \(\sum_{r'}x_{\theta,r'}=\mu(\theta)\); their destinations define \(\mu'\), and their cost is \(\sum_{\theta=(j,r,z)}\sum_{r'\ne r}x_{\theta,r'}\).
Changes may include self-assessment and may create types outside the initial support; changing an entire row costs its changed mass, regardless of how many entries differ.
Is deciding whether a permitted change of cost at most \(\lambda\) makes every positive-mass target type in \(\mu'\) socially qualified solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
Discrete constructive whole-row bribery is NP-complete for every fixed pair of integer consent quotas \(s\ge1,t\ge3\). [Source](https://aamas.csc.liv.ac.uk/Proceedings/aamas2017/pdfs/p1142.pdf)
Fractional group identification has been studied for finite agents with fractional membership outputs, rather than divisible societies and mass-transfer bribery. No result settling the decision problem above was located. [Source](https://fass.nus.edu.sg/ecs/wp-content/uploads/sites/4/2020/06/17-10-24.pdf)
The decision problem is NP-hard, even when \(q_1=\frac12\), all numerical inputs are dyadic rationals, and there is exactly one initial type per role.
The proof below handles arbitrary real mass splitting directly. The cited [discrete bribery theorem](https://aamas.csc.liv.ac.uk/Proceedings/aamas2017/pdfs/p1142.pdf) concerns indivisible rows and is not needed for this reduction.
We reduce from Independent Set restricted to graphs with no isolated vertices and instances satisfying \(1\le k<n\), where \(n\) is the number of vertices.
This restriction remains NP-hard. To verify this, use the standard reduction from satisfiability of formulas with three literal occurrences per clause. For a formula with \(c\ge1\) clauses:
The resulting graph has \(n=3c\) vertices and no isolated vertices. An independent set contains at most one vertex from each clause triangle. Consequently, an independent set of size \(c\) selects one occurrence from every clause without selecting complementary literals. Those selections extend to a satisfying assignment. Conversely, a satisfying assignment supplies such an independent set by selecting one true occurrence per clause.
Fix an instance \((G,k)\) of this restricted problem. Write \(V\) for its vertex set and \(N_G[v]\) for the closed neighborhood of \(v\).
Let \(h\) be the least integer satisfying \(2^h\ge2n\), and put \(a=2^{-h}\). Thus \(na\le\frac12\).
The role set is \(J=V\cup\{d\}\), where \(d\) is an additional role.
For each vertex \(v\), create one target type \(\theta_v=(v,r_v,1)\) of mass \(a\), with row
\(r_v(u)=0\) if \(u\in N_G[v]\), and \(r_v(u)=1\) otherwise.
Here \(u\) ranges over \(J\), so in particular \(r_v(d)=1\).
Create one non-target type \(\theta_d=(d,\mathbf1,0)\) of mass \(1-na\), where \(\mathbf1\) is the all-ones row.
Set
\(q_1=\frac12,\qquad q_0=a+a^2,\qquad \lambda=(n-k)a.\)
These are permitted inputs: \(0<q_0<1\) and \(0<\lambda\le\frac12\).
Every target has self-assessment \(r_v(v)=0\). Its initial disapproval mass is
\(1-A_v(\mu)=a\,|N_G[v]|.\)
Indeed, the initial row of vertex \(u\) disapproves role \(v\) precisely when \(u\in N_G[v]\), using the symmetry of the graph.
Since there are no isolated vertices, \(|N_G[v]|\ge2\). Also \(a<1\), so
\(1-A_v(\mu)\ge2a>a+a^2=q_0.\)
Thus every target is initially unqualified. Both promised positive-mass conditions hold.
Suppose \(G\) has an independent set \(I\) with \(|I|\ge k\).
Leave every row belonging to a vertex in \(I\) unchanged. Replace the entire row of every other target type by \(\mathbf1\). Leave the non-target type unchanged.
The cost is
\((n-|I|)a\le(n-k)a=\lambda.\)
We check every resulting target type.
For \(v\notin I\), the replacement row has self-assessment \(1\). The unchanged non-target mass alone approves role \(v\) with mass \(1-na\ge\frac12\). Hence \(A_v(\mu')\ge q_1\), and this target qualifies.
For \(v\in I\), self-assessment remains \(0\). Among the unchanged target rows, only \(v\)'s own row disapproves role \(v\): another vertex of \(I\) is not adjacent to \(v\). All changed rows and the non-target row approve it. Therefore
\(1-A_v(\mu')=a<a+a^2=q_0.\)
This target also qualifies. The change is successful.
Now suppose an arbitrary permitted change succeeds with cost at most \(\lambda\). No restriction is imposed on its replacement rows or on how finely it splits mass.
For each vertex \(v\), let
\(y_v=x_{\theta_v,r_v}\)
be the mass of its initial type that retains its original row. Thus \(0\le y_v\le a\).
The changed target mass is exactly \(\sum_{v\in V}(a-y_v)\). Changes to the non-target type can only add cost. Consequently,
\(na-\sum_{v\in V}y_v\le\lambda=(n-k)a,\)
which implies
\(\sum_{v\in V}y_v\ge ka.\)
If \(y_v>0\), the original target type \((v,r_v,1)\) has positive mass in the final society. Its self-assessment is \(0\), so success requires
\(1-A_v(\mu')<q_0.\)
For every \(u\in N_G[v]\), the unchanged mass \(y_u\) disapproves role \(v\). Other final masses contribute nonnegative disapproval. It follows that
\(\sum_{u\in N_G[v]}y_u\le1-A_v(\mu')<q_0=a+a^2.\)
This inequality holds for every vertex carrying positive unchanged mass.
Start with \(S=\{v\in V:y_v>0\}\). Repeatedly select any vertex \(v_i\) still in \(S\), add it to \(I\), and remove from \(S\) all vertices in \(N_G[v_i]\).
The selected vertices form an independent set: selecting a vertex removes all its neighbors before any later selection.
Let \(B_i\) be the vertices removed at step \(i\). The sets \(B_i\) partition the original positive support, and \(B_i\subseteq N_G[v_i]\). Each selected vertex satisfies \(y_{v_i}>0\). Therefore, by the neighborhood inequality,
\(\sum_{u\in B_i}y_u<q_0.\)
Writing \(s=|I|\), summing over the steps gives
\(\sum_{v\in V}y_v\le s q_0.\)
If \(s\le k-1\), this would imply
\(\sum_{v\in V}y_v\le(k-1)a(1+a)<ka.\)
For the last strict inequality, observe that
\((k-1)a\le(n-1)a<1,\)
and hence \((k-1)(1+a)<k\).
This contradicts \(\sum_v y_v\ge ka\). Thus \(s\ge k\), and \(G\) has an independent set of the required size.
This argument accounts for every allowed fractional change, including changes to self-assessments, arbitrary new rows, and changes to the non-target mass.
The construction has \(m=\tau=n+1\). Its rows require \(O(n^2)\) bits.
Since \(h=O(\log n)\), all masses, quotas, and the budget have polynomial encoding length. In particular,
\(q_0=\dfrac{2^h+1}{2^{2h}}\)
is dyadic. The construction is therefore a polynomial-time many-one reduction, and Sections 3 and 4 prove its equivalence in both directions.
Consequently, the stated decision problem is NP-hard. A polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof resolves the assigned decision problem. The reduction is correct, including its treatment of arbitrary real mass splitting. I found no mathematical gaps or false statements.
The stated restriction of Independent Set remains NP-hard.
The reduction from 3-CNF satisfiability creates \(n=3c\) vertices and sets \(k=c\), with \(c\ge1\). Thus \(1\le k<n\). Each vertex belongs to a clause triangle, so there are no isolated vertices.
The equivalence is valid:
The proof uses the standard NP-hardness of 3-CNF satisfiability. It does not rely on the cited discrete bribery result.
The construction satisfies all required domains and promises.
Since \(2^h\ge2n\), the choice \(a=2^{-h}\) gives \(0<na\le\frac12\). Consequently, every target mass is positive, the non-target mass \(1-na\) is positive, and the masses sum to \(1\).
There are exactly \(n+1\) roles and exactly one initial type per role, so \(m=\tau=n+1\).
The quota and budget bounds are valid. In particular, the source restrictions imply \(n\ge2\), hence \(a\le\frac14\), and therefore \(0<a+a^2<1\). Also, \(1\le k<n\) gives
\[
0<(n-k)a\le na\le\frac12.
\]
Thus the budget lies in the required interval.
For each vertex \(v\), symmetry of adjacency gives
\[
1-A_v(\mu)=a|N_G[v]|.
\]
The non-target row contributes no disapproval. Since the graph has no isolated vertices,
\[
1-A_v(\mu)\ge2a>a+a^2.
\]
Every target initially has self-assessment \(0\), so every target is initially unqualified. Both positive-mass promises are satisfied.
The proposed change from an independent set is permitted and successful.
Every changed target row differs from its original row because its self-entry changes from \(0\) to \(1\). Its full mass therefore contributes exactly \(a\) to the cost. The resulting cost is correctly computed as
\[
(n-|I|)a\le(n-k)a.
\]
For a changed target, the unchanged non-target row supplies approval mass \(1-na\ge\frac12=q_1\), establishing qualification with self-assessment \(1\).
For an unchanged target \(v\in I\), independence ensures that no other unchanged target row disapproves \(v\). Hence its disapproval mass is exactly \(a<q_0\), establishing qualification with self-assessment \(0\).
These checks cover every positive-mass target type produced by this change.
The reverse argument correctly covers the full permitted change model.
The definition \(y_v=x_{\theta_v,r_v}\) identifies the mass retaining the original row. The row-sum constraint gives \(0\le y_v\le a\). Thus changed target mass is exactly
\[
\sum_{v\in V}(a-y_v).
\]
Non-target changes contribute nonnegative additional cost, so the budget implies
\[
\sum_{v\in V}y_v\ge ka.
\]
Whenever \(y_v>0\), the original target type remains present with positive mass and self-assessment \(0\). Successful qualification therefore requires
\[
1-A_v(\mu')<q_0.
\]
Every retained mass \(y_u\) with \(u\in N_G[v]\) disapproves role \(v\). All remaining contributions to disapproval are nonnegative. Consequently,
\[
\sum_{u\in N_G[v]}y_u<q_0.
\]
This conclusion requires no assumption about other replacement rows or changes to the non-target mass.
The greedy procedure terminates and produces an independent set. Its removed sets partition the original positive support, and each removed set lies inside the closed neighborhood of its selected vertex.
Each selected vertex has positive retained mass, so the neighborhood inequality applies at every step. Summing yields the stated bound
\[
\sum_{v\in V}y_v\le s q_0.
\]
The individual inequalities actually give a strict bound; weakening it is valid.
If \(s\le k-1\), then
\[
\sum_{v\in V}y_v\le(k-1)a(1+a)<ka.
\]
The final strict inequality is justified because \((k-1)a<1\), implying \((k-1)(1+a)<k\). This also covers \(k=1\). The contradiction with the budget-derived lower bound proves \(s\ge k\).
Thus fractional splitting cannot invalidate the reverse implication.
The rows require \(O(n^2)\) bits. Since \(h=O(\log n)\), all constructed numerical values have polynomial binary encoding length. The displayed expression for \(q_0\) is correct and dyadic.
The construction is a polynomial-time many-one reduction with both implications proved. It establishes NP-hardness of the continuous decision problem; it does not claim or require membership in NP.
No additional clarification or repair 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.