Answer: The decision problem is in \(\mathrm{P}\); an exact maximizing trigger vector is computable in time polynomial in \(m,\tau,L\).
Theorem 1 — class: other
Given a finite set of peer-effect types \(T\), rational population masses \(\mu_t>0\) summing to one, and finite rational distributions \(\nu_t\) over observed influence-outcome pairs \((I,Y)\), choose a trigger \(r_t\) for each type to maximize \(\sum_{t\in T}\mu_t\bigl(\mathbb{E}_{\nu_t}[Y\mid I\ge r_t]-\mathbb{E}_{\nu_t}[Y\mid I<r_t]\bigr)\), with both conditional sets nonempty.
A society is given by its support: a list \(T\) of \(\tau\geq 1\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) counts supported types, not possible types.
For each type \(t\), the input explicitly lists a finite probability distribution \(\nu_t\) with positive binary-rational probabilities on pairs \((I,Y)\), where \(I\in\mathbb{Q}\cap[0,1]\) is normalized activation influence and \(Y\in\{0,1\}\) indicates activation. Each distribution has at least two distinct influence values; no deterministic threshold relation is promised.
Choose one trigger \(r_t\in[0,1]\) per type, requiring \(\nu_t(I<r_t)>0\) and \(\nu_t(I\geq r_t)>0\). Conditional expectations use the probabilities in \(\nu_t\); equal influence values remain together, with equality assigned above the trigger. Any maximizing choice is acceptable.
The objective is \(F(r)=\sum_{t\in T}\mu_t\bigl(\mathbb{E}_{\nu_t}[Y\mid I\geq r_t]-\mathbb{E}_{\nu_t}[Y\mid I<r_t]\bigr)\). Let \(m=\sum_t|\operatorname{supp}(\nu_t)|\), and let \(L\) be the total binary input length, including a rational target value \(q\).
Is deciding whether there exist feasible triggers with \(F(r)\geq q\) in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For finite deterministic linear-threshold potential outcomes with both activation classes present, the true threshold maximizes the difference of conditional means; this is presented as a threshold-estimation result, without a complexity classification ([Tran and Zheleva, 2022](https://arxiv.org/pdf/2201.11242)).
No result settling this exact explicitly encoded mass problem was located in the literature search.
The decision problem is in \(\mathrm{P}\). An exact maximizing trigger vector can also be computed in time polynomial in \(m,\tau,L\).
The proof uses two properties of the stated input: each distribution is explicitly listed, and triggers for different types are unconstrained by one another. No deterministic threshold relation is needed.
Fix a type \(t\). Let its distinct influence values, in increasing order, be
\(x_{t,1}<\cdots<x_{t,s_t}\).
By hypothesis, \(s_t\geq 2\).
For each influence value define
\[
\text{}
\]
The following quantities aggregate all outcomes at that influence:
\(w_{t,j}=\nu_t(I=x_{t,j})\) and
\(a_{t,j}=\nu_t(I=x_{t,j},Y=1)\).
Thus \(w_{t,j}>0\), \(0\leq a_{t,j}\leq w_{t,j}\), and
\(\sum_{j=1}^{s_t}w_{t,j}=1\). This aggregation keeps equal influence values together, as required.
A trigger \(r_t\) is feasible precisely when, for some
\(k\in\{1,\ldots,s_t-1\}\), it satisfies
\(x_{t,k}<r_t\leq x_{t,k+1}\).
Indeed, positivity of the probabilities on both sides requires at least one influence value below the trigger and at least one at or above it. Sorting then identifies exactly such a cut.
Conversely, every such cut is feasible and has the representative trigger
\(r_t=x_{t,k+1}\in[0,1]\).
Equality belongs above the trigger, so this representative puts exactly the first \(k\) influence groups below it.
Define the prefix quantities
\(W_{t,k}=\sum_{j=1}^{k}w_{t,j}\),
\(A_{t,k}=\sum_{j=1}^{k}a_{t,j}\), and the total activation probability
\(B_t=\sum_{j=1}^{s_t}a_{t,j}\).
For every feasible cut, \(0<W_{t,k}<1\). Since \(Y\) is binary, its two conditional means are
\(\mathbb{E}[Y\mid I<r_t]=A_{t,k}/W_{t,k}\) and
\(\mathbb{E}[Y\mid I\geq r_t]=(B_t-A_{t,k})/(1-W_{t,k})\).
Consequently, the score of cut \(k\) is exactly
\(d_{t,k}=(B_t-A_{t,k})/(1-W_{t,k})-A_{t,k}/W_{t,k}\).
Every feasible trigger has one of these scores, and every listed score is attained.
Let
\(d_t^*=\max_{1\leq k<s_t}d_{t,k}\),
and choose any maximizing index \(k_t^*\). These maxima exist because their candidate sets are finite and nonempty.
For every feasible trigger vector \(r\), the score of type \(t\) is at most \(d_t^*\). Since \(\mu_t>0\), summing these inequalities gives
\(F(r)\leq\sum_{t\in T}\mu_t d_t^*\).
Now choose \(r_t^*=x_{t,k_t^*+1}\) independently for every type. Section 1 proves that each choice is feasible and attains its local maximum. Therefore
\(F(r^*)=\sum_{t\in T}\mu_t d_t^*\).
Hence the attained global maximum is exactly
\(F^*=\sum_{t\in T}\mu_t d_t^*\).
The decision answer is yes if and only if \(F^*\geq q\).
This requires evaluating at most
\(\sum_t(s_t-1)\leq m-\tau\) candidate scores, rather than enumerating combinations of cuts.
It remains to verify that the rational computations above do not require exponentially many bits. All bit lengths below refer to the ordinary explicit binary encoding in the question.
For type \(t\), write each listed probability as
\(p_{t,\ell}=c_{t,\ell}/b_{t,\ell}\), where numerator and denominator are positive integers. Put
\(D_t=\prod_{\ell}b_{t,\ell}\) and
\(z_{t,\ell}=c_{t,\ell}(D_t/b_{t,\ell})\).
These are integers, and normalization gives
\(\sum_{\ell}z_{t,\ell}=D_t\).
Computing them requires only integer multiplication and exact integer division.
For cut \(k\), let \(U_{t,k}\) be the sum of the integer weights below the cut, \(V_{t,k}\) the sum below the cut with \(Y=1\), and \(C_t\) the total integer weight with \(Y=1\). Then
\(1\leq U_{t,k}\leq D_t-1\), and the score becomes
\(d_{t,k}=(U_{t,k}C_t-D_tV_{t,k})/[U_{t,k}(D_t-U_{t,k})]\).
The denominator is strictly positive. Thus two candidates can be compared exactly by cross multiplication, including when their numerators are negative.
Because the denominator encodings form part of the input,
\(\sum_t\log_2 D_t=\sum_{t,\ell}\log_2 b_{t,\ell}\leq L\).
Every integer weight and prefix sum is at most \(D_t\). Each candidate numerator has absolute value at most \(D_t^2\), and each candidate denominator is at most \(D_t^2\). All these integers, and the products needed to compare them, therefore have \(O(L)\) bits.
For each selected score write
\(d_t^*=N_t/H_t\), using the integer expression above, with \(H_t>0\). Write the input mass as
\(\mu_t=u_t/v_t\), with \(v_t>0\).
A common denominator for the weighted sum is
\(Q=\prod_{t\in T}v_tH_t\).
Since \(H_t\leq D_t^2\), we have
\(\log_2 Q\leq\sum_t\log_2 v_t+2\sum_t\log_2 D_t=O(L)\).
Thus even this unreduced common denominator has only \(O(L)\) bits.
The corresponding numerator also has \(O(L)\) bits. To see this explicitly, each score belongs to \([-1,1]\), because it is a difference of two conditional means in \([0,1]\). For any subset of processed types, the absolute value of its weighted sum is therefore at most the sum of its masses, which is at most \(1\). When sequential rational addition uses the product of the processed denominators, its numerator consequently has absolute value at most that denominator.
Finally, write \(q=c/e\), with \(e>0\). If \(F^*=P/Q\), the answer is determined exactly by comparing the integers \(Pe\) and \(cQ\). Both have \(O(L)\) bits.
The algorithm is:
Sorting requires \(O(m\log(m+1))\) rational comparisons. The remaining work requires \(O(m+\tau)\) integer arithmetic operations. Every operation uses integers of \(O(L)\) bits. Using elementary quadratic-time integer arithmetic gives the polynomial bit-operation bound
\(O((m\log(m+1)+m+\tau)L^2)\).
The deterministic threshold-estimation setting discussed by [Tran and Zheleva (2022)](https://arxiv.org/pdf/2201.11242) is not needed for this argument. The algorithm applies to every explicitly supplied distribution satisfying the question’s hypotheses, including those with no deterministic threshold relation.
Thus the stated problem is polynomial-time solvable. Under polynomial-time many-one reductions, it could be \(\mathrm{NP}\)-hard only if \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated decision problem correctly: it supplies an exact polynomial-time algorithm and proves that its computed value is the attained global maximum. There are no mathematical gaps. The only issue is a harmless formatting fragment.
The aggregation by distinct influence values is valid. For every group, \(w_{t,j}>0\), because the explicitly listed support probabilities are positive. The activation weight satisfies \(0\leq a_{t,j}\leq w_{t,j}\), including groups containing outcomes from both activation classes.
The feasibility characterization
\(x_{t,k}<r_t\leq x_{t,k+1}\), for \(1\leq k<s_t\), is exact. A feasible trigger must leave at least one influence group on each side, and the strict inequality below the trigger fixes the stated endpoint conventions.
The representative \(r_t=x_{t,k+1}\) belongs to \([0,1]\) and realizes the intended cut. This also handles influence values at \(0\) or \(1\). The hypothesis \(s_t\geq2\) guarantees at least one feasible cut.
The conditional means are correctly computed from the prefix probabilities. Their denominators are nonzero because \(0<W_{t,k}<1\). Thus the displayed score formula covers every feasible trigger and each candidate score is attained.
Each local maximum exists because its candidate set is finite and nonempty. The inequality
\(F(r)\leq\sum_t\mu_t d_t^*\)
follows from the local bounds and the positive masses.
The independently chosen representatives are jointly feasible: the task imposes no constraint coupling different types. They attain equality in that bound. Therefore the formula for \(F^*\) is justified, and comparing it with \(q\) answers the existential decision question exactly.
The candidate count is also correct:
\(\sum_t(s_t-1)\leq m-\tau\).
Aggregation cannot increase the number of support entries.
The denominator product \(D_t\) is a valid common denominator, whether or not the input fractions are reduced. Each \(z_{t,\ell}\) is a positive integer, and normalization gives \(\sum_\ell z_{t,\ell}=D_t\).
For a feasible cut, both sides have positive integer weight, so
\(1\leq U_{t,k}\leq D_t-1\).
Substituting the integer weights into the conditional means gives
\[
\frac{C_t-V_{t,k}}{D_t-U_{t,k}}-\frac{V_{t,k}}{U_{t,k}}
=
\frac{U_{t,k}C_t-D_tV_{t,k}}
{U_{t,k}(D_t-U_{t,k})}.
\]
The numerator and denominator in the prover’s expression are therefore correct. The denominator is strictly positive, so cross multiplication preserves comparisons even for negative scores.
The bound \(\sum_t\log_2D_t\leq L\) follows from the explicit encoding of the probability denominators. Every integer weight and prefix sum lies between \(0\) and \(D_t\).
The candidate numerator has absolute value at most \(D_t^2\), and its denominator is at most \(D_t^2\). Cross products used to compare candidates consequently have \(O(L)\) bits.
For the weighted sum, the product denominator
\(Q=\prod_t v_tH_t\)
has \(O(L)\) bits because the mass denominators are also explicitly encoded and \(H_t\leq D_t^2\).
The numerator argument is valid. Each score lies in \([-1,1]\), and every partial sum of the positive masses is at most \(1\). Thus the numerator of a processed weighted sum has absolute value at most its product denominator. Intermediate multiplication and addition operands also retain \(O(L)\) bits.
The final comparison with the rational target uses a positive denominator \(e\). Both comparison integers have \(O(L)\) bits, including when the target or optimum is negative.
Exact rational sorting and equality testing are available by integer cross multiplication. The sorting comparison count is bounded by \(O(m\log(m+1))\).
Constructing denominator products, converting probabilities to integer weights, forming prefixes, scanning cuts, and combining the chosen scores requires \(O(m+\tau)\) arithmetic operations. All operands have \(O(L)\) bits. Elementary integer arithmetic therefore supports the stated polynomial bound.
The returned triggers are input influence values, so their exact output representation also has polynomial length.
No external theorem or literature claim is needed for the argument. The qualification concerning NP-hardness is correct for polynomial-time many-one reductions.
Minor — Section 1, immediately after “For each influence value define”. An empty display containing \text{} interrupts the sentence. The quantities are nevertheless defined unambiguously immediately afterward. Remove the empty display or join the introductory sentence to those definitions. No mathematical clarification is required.
⟨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.