Answer: NP-hard for every fixed \(0<\varepsilon<1\) to achieve approximation factor \(\tau^{1-\varepsilon}\).
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor maximizing fna, it is NP-hard to compute a signaling scheme that represents a n1−ε-approximation, for any constant ε > 0.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(\mathcal T\) with rational masses \(\mu_t\) summing to \(1\), a finite state set \(\Theta\) with rational prior \(q\), and rational opinions \(a_{t\theta}\in[0,1]\), choose a finite public signaling scheme \(x_{\theta j}\ge 0\) with \(\sum_j x_{\theta j}=q_\theta\). For each signal \(j\), let \(p_j=\sum_\theta x_{\theta j}\) and, when \(p_j>0\), let \(z_{tj}=\sum_\theta a_{t\theta}x_{\theta j}/p_j\). What is the maximum expected covered population mass, \(\sum_j p_j\sum_{t\in\mathcal T}\mu_t\mathbf{1}[z_{tj}\ge 1/2]\)?
A society is given by its support: the list of the \(\tau\) types \(t\in\mathcal T\) with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\ge1\) states \(\Theta\), a binary rational prior \(q_\theta\ge0\) with \(\sum_\theta q_\theta=1\), and binary rational opinions \(a_{t\theta}\in[0,1]\). Let \(L\) be the total input bit length.
The sender observes the state and commits in advance to a public signaling scheme with any finite signal set \(J\), represented by joint probabilities \(x_{\theta j}\ge0\) satisfying \(\sum_{j\in J}x_{\theta j}=q_\theta\).
For \(p_j=\sum_\theta x_{\theta j}>0\), the opinion of type \(t\) is \(z_{tj}=\sum_\theta a_{t\theta}x_{\theta j}/p_j\); its entire mass is covered exactly when \(z_{tj}\ge\tfrac12\), including equality. Signals of probability zero contribute zero.
Maximize \(F(x)=\sum_{j:p_j>0}p_j\sum_t\mu_t\mathbf1[z_{tj}\ge\tfrac12]\), and denote the optimum by \(\mathrm{OPT}\). State running times in \(m,\tau,L\) and any approximation parameters.
For each fixed \(0<\varepsilon<1\), is computing a public signaling scheme with \(F(x)\ge\mathrm{OPT}/\tau^{1-\varepsilon}\) possible in polynomial time in \(m,\tau,L\), or is this approximation task NP-hard?
For discrete societies of \(n\) agents, maximizing the expected number with opinion in \([\tfrac12,1]\) is NP-hard to approximate within \(n^{1-\varepsilon}\) for every fixed \(0<\varepsilon<1\), even without social influence and with a uniform state prior; a polynomial-time \(n\)-approximation is known. [Source](https://arxiv.org/html/2509.07520v1)
No separate result specifically stated for binary rational type masses was verified.
Result. For every fixed \(0<\varepsilon<1\), computing a scheme with \(F(x)\ge \mathrm{OPT}/\tau^{1-\varepsilon}\) is NP-hard. Thus no algorithm polynomial in \(m,\tau,L\) achieves this guarantee unless \(\mathrm P=\mathrm{NP}\). A polynomial-time \(\tau\)-approximation does extend to arbitrary binary rational masses.
1. The discrete hardness premise
We use the discrete-society hardness theorem supplied in the question: approximating the maximum expected number of covered agents within \(n^{1-\varepsilon}\) is NP-hard for every fixed \(0<\varepsilon<1\), even without social influence and with a uniform state prior.
Its numerical hypotheses fit the present input model. The cited construction has \(m=n\), prior probabilities \(1/n\), and opinions drawn from \(0\), \(3/4\), and \(1/2-1/(8n)\). These are binary-encoded rationals of bit length \(O(\log n)\). The desired interval is the closed interval \([1/2,1]\), so its treatment of equality agrees with this problem. See [Theorem 5 and its construction](https://arxiv.org/html/2509.07520v1#S4.SS3).
Here and below, “binary rational” means a rational represented by a binary-encoded numerator and denominator.
2. A polynomial reduction to support representation
Consider a discrete instance with \(n\ge1\) agents. Write \(a_{i\theta}\) for agent \(i\)'s opinion in state \(\theta\).
Partition the agents into equivalence classes according to their complete opinion vectors: agents \(i\) and \(i'\) are equivalent precisely when \(a_{i\theta}=a_{i'\theta}\) for every state \(\theta\). For each class \(t\), let \(k_t\) be its cardinality. Create one type with its common opinion vector and mass \(\mu_t=k_t/n\).
All masses are positive rationals, and \(\sum_t\mu_t=1\). The resulting support size satisfies \(1\le\tau\le n\). Keep the states and prior unchanged.
For a feasible scheme \(x\), define the discrete objective \(C(x)\) to be the expected number of covered agents. Agents in the same class have identical posterior opinions at every positive-probability signal. Consequently,
\(C(x)=\sum_{j:p_j>0}p_j\sum_t k_t\mathbf1[z_{tj}\ge1/2]=nF(x).\)
This identity holds for every feasible finite scheme, including signals that place opinions exactly at the threshold. Zero-probability signals contribute zero to both objectives. Moreover, the feasible schemes depend only on the prior, which was unchanged. Taking optimal values therefore gives
\(\mathrm{OPT}_{\mathrm{discrete}}=n\,\mathrm{OPT}_{\mathrm{types}}.\)
The reduction is polynomial in the discrete input length \(B\), \(n\), and \(m\): exact rational comparisons identify the classes, and each new mass requires \(O(\log n)\) bits. The resulting input length satisfies \(L=O(B+n\log n)\).
Now suppose an algorithm, polynomial in \(m,\tau,L\), always returned a scheme satisfying the requested guarantee. Apply it to the constructed type instance and use its joint probabilities as the discrete signaling scheme. Then
\(C(x)=nF(x)\ge \dfrac{n\,\mathrm{OPT}_{\mathrm{types}}}{\tau^{1-\varepsilon}}=\dfrac{\mathrm{OPT}_{\mathrm{discrete}}}{\tau^{1-\varepsilon}}\ge\dfrac{\mathrm{OPT}_{\mathrm{discrete}}}{n^{1-\varepsilon}}.\)
The last inequality follows from \(\tau\le n\) and \(1-\varepsilon>0\). Its running time is polynomial in the original input parameters, contradicting the discrete hardness premise unless \(\mathrm P=\mathrm{NP}\).
Thus coincident opinion vectors cause no difficulty: merging them makes the proposed approximation guarantee at least as strong as the forbidden discrete guarantee. No separate hardness theorem for arbitrary rational masses is needed.
3. A polynomial-time \(\tau\)-approximation
For completeness, the baseline approximation also extends without expanding the masses into individual agents.
For each type \(t\), solve the rational linear program
\(\displaystyle M_t=\max\left\{\sum_\theta y_\theta:\ 0\le y_\theta\le q_\theta,\quad \sum_\theta(a_{t\theta}-1/2)y_\theta\ge0\right\}.\)
Its feasible set is nonempty and compact, so an optimum exists. Rational linear programming computes an optimal \(y^{(t)}\) in time polynomial in \(m,L\).
Let \(R_t(x)\) denote the total probability of signals covering type \(t\). For any scheme, sum its joint-probability columns over those signals. The resulting vector satisfies the LP constraints: each covered column satisfies the displayed coverage inequality, and their sum is coordinatewise at most \(q\). Hence \(R_t(x)\le M_t\).
Conversely, the two columns \(y^{(t)}\) and \(q-y^{(t)}\) form a feasible scheme. If its first column has positive probability, it covers \(t\) by the LP inequality; otherwise \(M_t=0\). Therefore this scheme achieves \(R_t(x)\ge M_t\). Together with the preceding upper bound, this proves that \(M_t\) is exactly the maximum achievable coverage probability for type \(t\).
For every scheme,
\(F(x)=\sum_t\mu_tR_t(x)\le\sum_t\mu_tM_t\le\tau\max_t\mu_tM_t.\)
Choose a type maximizing \(\mu_tM_t\), and output its two-column scheme. Its value is at least that maximum, hence at least \(\mathrm{OPT}/\tau\).
This algorithm uses \(\tau\) LPs, each with \(m\) variables and \(2m+1\) inequalities. Its total running time is \(\tau\,\operatorname{poly}(m,L)\), with at most two signals and polynomial output bit length.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned question correctly: for every fixed \(0<\varepsilon<1\), obtaining the stated \(\tau^{1-\varepsilon}\) approximation is NP-hard under the discrete hardness premise supplied in USER_TASK. The additional polynomial-time \(\tau\)-approximation is also correct.
No major or minor mathematical issues were found.
The prover states the supplied discrete hardness theorem with the relevant quantifiers: hardness holds for every fixed \(0<\varepsilon<1\), for public signaling, without social influence, and with a uniform prior.
The numerical compatibility claim is accurate. The cited construction uses one state per agent, uniform prior probabilities, and precisely the three opinion values listed by the prover. It also uses the closed target interval, so equality at the threshold counts as coverage. These details appear in [Theorem 5 and its construction](https://arxiv.org/html/2509.07520v1#S4.SS3).
Under the explicitly stated numerator-and-denominator interpretation of binary rational encoding, these values have \(O(\log n)\) bit length and lie in \([0,1]\). Thus the reduction does not rely on irrational inputs or an incompatible threshold convention.
The discrete hardness theorem is a supplied premise of USER_TASK; the prover need not reproduce its proof.
Equality of complete opinion vectors defines an equivalence relation on the agents. Every resulting class has a positive integer cardinality \(k_t\), so the constructed masses satisfy
\[ \mu_t=\frac{k_t}{n}>0, \qquad \sum_t\mu_t=1, \qquad 1\le\tau\le n. \]
Different classes have different opinion vectors, so the construction respects the distinction between support size and the number of agents.
For every positive-probability signal, agents in the same class have identical posterior opinions. Therefore the identity
\[ C(x)=nF(x) \]
holds for every feasible finite scheme. It also holds at threshold equality and when zero-probability signals are present.
The states and prior are unchanged. Consequently, both instances have exactly the same feasible joint-probability matrices, and scaling the objective gives
\[ \mathrm{OPT}_{\mathrm{discrete}} = n\,\mathrm{OPT}_{\mathrm{types}}. \]
There is no loss from merging repeated opinion vectors.
Exact comparison of explicitly encoded rational vectors takes polynomial time. The class cardinalities and masses have \(O(\log n)\) bit length. Retaining one vector per class and the original prior is consistent with the claimed bound
\[ L=O(B+n\log n). \]
For a fixed \(0<\varepsilon<1\), the hypothesized type algorithm would produce a discrete scheme satisfying
\[ C(x) \ge \frac{\mathrm{OPT}_{\mathrm{discrete}}} {\tau^{1-\varepsilon}} \ge \frac{\mathrm{OPT}_{\mathrm{discrete}}} {n^{1-\varepsilon}}. \]
The second inequality is correct because \(\tau\le n\) and \(1-\varepsilon>0\). Merging agents strengthens the approximation guarantee required from the hypothetical algorithm.
The constructed parameters are polynomially bounded in the original explicit input length. Reusing the returned joint probabilities requires no expansion of the type masses. Thus an algorithm polynomial in \(m,\tau,L\) would yield the forbidden polynomial-time discrete approximation.
This establishes the claimed hardness for the rational-mass input class. Hardness on the subclass of masses obtained as class frequencies is sufficient; a separate theorem covering every possible rational mass vector is unnecessary.
For a positive-probability column \(y\), type \(t\) is covered exactly when
\[ \sum_\theta \left(a_{t\theta}-\frac12\right)y_\theta \ge0. \]
The LP therefore encodes the probability that can be allocated to a signal covering that type.
Its feasible set contains zero and is closed and bounded by the coordinate constraints. Hence an optimum exists. All coefficients are rational with encoding length polynomial in the input length.
The invoked rational linear-programming result applies: a feasible, bounded rational LP can be solved exactly in polynomial time, with a rational optimal solution of polynomial encoding length. The prover verifies the necessary feasibility, boundedness, and rationality hypotheses.
For any scheme, summing the columns covering type \(t\) produces a nonnegative vector bounded coordinatewise by \(q\). Each included column satisfies the coverage inequality, and summation preserves that inequality. Its objective value is \(R_t(x)\), proving
\[ R_t(x)\le M_t. \]
Conversely, the columns \(y^{(t)}\) and \(q-y^{(t)}\) are nonnegative and sum to \(q\), so they form a feasible scheme. If the first column has positive probability, it covers type \(t\) and has probability \(M_t\). If its probability is zero, then \(M_t=0\), and the claimed lower bound remains valid.
Together, these directions establish exactly the stated characterization of \(M_t\).
Exchanging the finite sums gives
\[ F(x)=\sum_t\mu_tR_t(x). \]
The single-type bounds and nonnegative masses imply
\[ F(x) \le \sum_t\mu_tM_t \le \tau\max_t\mu_tM_t. \]
The selected type’s two-column scheme contributes at least \(\mu_tM_t\) to the full objective. Therefore its value is at least \(\mathrm{OPT}/\tau\).
Each LP has \(m\) variables and \(2m+1\) inequalities. Solving \(\tau\) such LPs and comparing the rational weighted values gives the stated runtime
\[ \tau\,\operatorname{poly}(m,L), \]
with at most two signals and polynomial output bit length.
The argument covers zero-prior states, zero LP optima, \(\mathrm{OPT}=0\), \(m=1\), and \(\tau=1\). None creates a division-by-zero problem or invalidates the guarantee.
None. The hardness conclusion and the baseline approximation are both verifiable as written.
⟨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.