Answer: \(\mathrm{NP}\text{-complete}\), already for \(\tau=1\).
Theorem 13 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe decision problem of whether there exists a seed set $S$ with $|S| \leq k$ and $\payoffvar(S) > 0$ is NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite network template \(G=(V,E)\), its thresholds, product quality \(\phi\), payoffs \(p,q\), and per-market seed cap \(k\), consider a continuum of copies indexed by \(z\in[0,1]\). Each copy follows the paper's cascade and payoff rules. Is there a measurable assignment \(S_z\) of accepting seed nodes, with \(|S_z|\le k\) almost everywhere, such that the population-average normalized payoff \(\int_0^1 \pi_G(S_z)/|V|\,dz\) is positive?
A society is given by its support: a list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) counts supported types, not possible types. Here a type is a complete market template, and the support consists of one template of mass \(1\), so \(\tau=1\).
The template is a nonempty finite simple unweighted undirected graph \(G=(V,E)\), with \(m=|V|\), binary-rational thresholds \(\theta_i\in[0,1]\), quality \(\phi\in[0,1]\), positive binary-rational payoffs \(p,q\), and an input integer seed cap \(0\le k\le m\). Let \(L\) be the total binary input length, including \(k\); express running times in \(m,\tau,L,k\).
A node accepts exactly when \(\theta_i\le\phi\). Seeds must be accepting. Exposed accepting nodes expose all their neighbors recursively; rejecting nodes do not transmit. Each exposed node is counted once, including seeds. Writing \(V^+(S)\) and \(V^-(S)\) for exposed accepting and rejecting nodes, define \(\pi_G(S)=p|V^+(S)|-q|V^-(S)|\), with \(\pi_G(\varnothing)=0\).
Markets are independent identical copies indexed by \(z\in[0,1]\) with Lebesgue measure. An assignment \(z\mapsto S_z\subseteq V\) is measurable when \(\{z:S_z=S\}\) is measurable for every subset \(S\); it must use accepting seeds and satisfy \(|S_z|\le k\) almost everywhere.
Is deciding whether such an assignment satisfies \(\int_0^1\pi_G(S_z)/m\,dz>0\) solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For a single finite market, deciding whether an accepting seed set of size at most \(k\) has positive payoff is NP-complete; without the seed cap, payoff maximization is polynomial-time solvable ([Abebe, Adamic, and Kleinberg](https://arxiv.org/pdf/1709.04123)).
No result addressing this exact independent-copy continuum formulation was identified in the literature search.
The existence problem is NP-complete, already for \(\tau=1\). Consequently, a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
I interpret the question as asking whether there exists an admissible measurable assignment with strictly positive integral. An arbitrary supplied measurable assignment has no specified finite input representation.
Define the accepting set and the family of feasible seed sets by
\[
A=\{i\in V:\theta_i\le\phi\},
\qquad
\mathcal F_k=\{S\subseteq A:|S|\le k\}.
\]
Here and below, these expressions mean \(\displaystyle A=\{i\in V:\theta_i\le\phi\}\) and \(\displaystyle\mathcal F_k=\{S\subseteq A:|S|\le k\}\), respectively.
The family \(\mathcal F_k\) is finite and contains \(\varnothing\). Therefore the maximum
\(M_k=\max_{S\in\mathcal F_k}\pi_G(S)\)
exists and satisfies \(M_k\ge0\).
Lemma. The maximum integral over admissible measurable assignments equals \(M_k/m\).
Proof. First replace any infeasible choices on the exceptional null set by \(\varnothing\). This preserves measurability and the integral, so we may assume feasibility everywhere.
For each \(S\in\mathcal F_k\), let
\(E_S=\{z\in[0,1]:S_z=S\}\)
and let \(\lambda_S\) be its Lebesgue measure. By the prescribed measurability condition, every \(E_S\) is measurable. These sets form a finite partition of \([0,1]\), so
\(\lambda_S\ge0\) and \(\sum_{S\in\mathcal F_k}\lambda_S=1\).
The normalized payoff is a measurable simple function. It is bounded in absolute value by \(p+q\), because each exposure count is at most \(m\), and hence is integrable. Its integral is
\(\displaystyle \int_0^1\frac{\pi_G(S_z)}m\,dz = \frac1m\sum_{S\in\mathcal F_k}\lambda_S\pi_G(S) \le \frac1m\sum_{S\in\mathcal F_k}\lambda_SM_k = \frac{M_k}{m}. \)
Choose a maximizing set \(S^\ast\in\mathcal F_k\). The constant assignment \(S_z=S^\ast\) is measurable and admissible, and its integral is \(M_k/m\). This proves the lemma.
Since the graph is nonempty, \(m>0\). Consequently,
\(\displaystyle \exists\text{ admissible measurable assignment with positive integral} \quad\Longleftrightarrow\quad \exists S\subseteq A,\ |S|\le k,\ \pi_G(S)>0. \)
Thus allowing different seed sets on different independent copies does not change the answer.
Use the finite-market NP-completeness result stated in the task: deciding whether an accepting seed set of size at most \(k\) has strictly positive payoff is NP-complete. This is also the decision problem stated in Theorem 13 of [Abebe, Adamic, and Kleinberg](https://arxiv.org/pdf/1709.04123).
Given a finite-market instance, construct the society whose support contains exactly that complete template, with mass \(1\). Preserve its graph, thresholds, quality, payoffs, and seed cap.
This construction satisfies every target restriction:
Writing \(L_0\) for the finite-instance length, the construction takes \(O(L_0)\) time and produces length \(L=O(L_0)\). The equivalence proved in Section 1 shows that it preserves yes-instances and no-instances. It is therefore a polynomial-time many-one reduction, establishing NP-hardness for \(\tau=1\).
By Section 1, a yes-instance has a finite certificate: one accepting seed set \(S\) with \(|S|\le k\) and positive payoff. Listing its vertices requires \(O(k\log(m+1))\) bits.
A verifier first checks the cap and acceptance of every seed. It then computes exposure by graph traversal: exposed accepting vertices transmit to their neighbors, exposed rejecting vertices do not, and a visited flag ensures that every vertex is counted once. This implements exactly the stated cascade rule.
Let \(a=|V^+(S)|\) and \(b=|V^-(S)|\). To check positivity exactly, write the input rationals as \(p=u/v\) and \(q=x/y\), with positive integer denominators. Then
\(\displaystyle \pi_G(S)>0 \quad\Longleftrightarrow\quad uya>xvb. \)
All integers in this comparison have \(O(L+\log(m+1))\) bits. Threshold comparisons are likewise exact rational comparisons. A conservative bound using elementary integer arithmetic and graph traversal is \(O((m+1)^2L^2)\) bit operations. Thus verification is polynomial, proving membership in NP.
For completeness, exhaustive search gives the deterministic bound
\(\displaystyle O\!\left( \left[\sum_{j=0}^{\min(k,|A|)}\binom{|A|}{j}\right] (m+1)^2L^2 \right) \subseteq O\!\left((k+1)m^k(m+1)^2L^2\right). \)
These bounds concern \(\tau=1\). They show polynomial-time solvability for every fixed cap \(k\), while the NP-completeness result concerns an input cap that may grow with \(m\). For \(k=0\), the answer is always no.
When \(k=m\), the cap imposes no restriction, and the unbudgeted polynomial-time optimization result stated in the task applies. The hardness result concerns the family of instances with an arbitrary input cap.
The continuum preserves that cap almost everywhere. The averaging lemma shows that it cannot produce positive aggregate payoff when every feasible finite seed set has nonpositive payoff.
⟨structured verdict parsed — rendered above⟩
The argument is correct and resolves the intended existence question: the continuum problem is NP-complete already for \(\tau=1\). No mathematical gaps or false steps were found.
The prover explicitly interprets the task as asking whether there exists an admissible measurable assignment with positive integral. This is the evidently intended interpretation: the finite input describes the template and seed cap, without providing a representation of a particular measurable assignment.
This clarification is appropriate and does not weaken the target.
The definitions of \(A\) and \(\mathcal F_k\) match the acceptance rule and seed restriction, including equality at the threshold.
Because \(V\) is finite, \(\mathcal F_k\) is finite. It contains \(\varnothing\), whose payoff is zero. Thus \(M_k\) exists and satisfies \(M_k\ge 0\). This remains valid when \(k=0\) or when no node accepts.
The repeated definitions are redundant but harmless.
The replacement of infeasible choices by \(\varnothing\) is valid. In particular, the infeasibility set is measurable: it is a finite union of measurable fibers corresponding to infeasible subsets of \(V\). Admissibility makes this set null.
Replacing its values by \(\varnothing\) preserves fiber measurability and does not change the integral. Thus the subsequent assumption of feasibility everywhere is justified.
After that replacement, the sets \(E_S\), indexed by \(S\in\mathcal F_k\), form a finite measurable partition of \([0,1]\). Consequently, their measures are nonnegative and sum to one.
The payoff function is a measurable simple function. The stated bound is correct:
\[
\left|\frac{\pi_G(S)}m\right|
\le \frac{p|V^+(S)|+q|V^-(S)|}{m}
\le p+q.
\]
Here \(m>0\), as required by the nonempty-graph assumption.
The displayed integral is therefore a finite weighted average of feasible payoffs, divided by \(m\). Bounding each payoff by \(M_k\) proves the claimed upper bound.
A maximizing seed set exists, and its constant assignment is measurable and admissible. It attains that upper bound. Hence the lemma proves exactly the claimed equality of maxima.
The strict-positive equivalence follows without any limit or attainment issue. This is the central step connecting the continuum problem to the finite problem, and it is fully justified.
The prover uses the finite-market NP-completeness statement explicitly supplied in USER_TASK. That statement has the same accepting-seed restriction, cap, and strict-positive objective needed here.
The supplementary citation is accurate: Theorem 13 states NP-completeness of deciding whether a seed set of size at most \(k\) has positive payoff, under the paper’s accepting-seed convention. [Abebe, Adamic, and Kleinberg](https://arxiv.org/pdf/1709.04123)
The reduction copies the finite instance into a singleton support with mass \(1\). It preserves all template restrictions, \(m\), and \(k\), and fixes \(\tau=1\). Its time and output-length bounds are polynomial. The averaging equivalence establishes preservation of both yes-instances and no-instances.
Thus the NP-hardness conclusion follows.
A finite seed set is a sufficient certificate because of the proved equivalence. Its stated encoding size is polynomial in the input length.
The traversal correctly implements the cascade: accepting exposed vertices transmit, rejecting exposed vertices do not, and visited flags prevent repeated counting.
The positivity calculation is correct. Since \(v,y>0\),
\[
\frac{u}{v}a-\frac{x}{y}b>0
\quad\Longleftrightarrow\quad
uya>xvb.
\]
The counts are at most \(m\), so the products have \(O(L+\log(m+1))\) bits. Exact rational acceptance comparisons are also polynomial-time computations.
The conservative verification bound \(O((m+1)^2L^2)\) accommodates graph traversal and elementary integer arithmetic. Membership in NP, and therefore NP-completeness, is established.
The exhaustive-search bound correctly counts feasible subsets. For \(m\ge1\), its simplification to an upper bound involving \((k+1)m^k\) is valid. It establishes polynomial time for every fixed \(k\), without claiming polynomial time uniformly over input caps.
For \(k=0\), only the empty seed set is feasible, so the answer is no. For \(k=m\), the cap is unrestricted and the supplied unbudgeted result applies. Neither case conflicts with hardness for arbitrary input \(k\).
The bounds explicitly concern \(\tau=1\), which is the entire support regime requested by the task.
No repair or 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.