Answer: NP-hard to approximate within \(o(\tau)\), already for \(m=3\). Even a polynomial-time multiplicative \(\tau\)-approximation would imply \(\mathrm{P}=\mathrm{NP}\).
Theorem 8(i) — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIf n is the number of nodes of a network, then (i) It is NP-hard to approximate MIN-ADOPTION with an approximation ratio better than Ω(n). (ii) The MAX-ADOPTION problem can be solved in O(n2) time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite product set \(P\), cohort types \(i\in\{1,\ldots,\tau\}\) with rational masses \(\mu_i\), thresholds \(\theta_i\), initial adopted products or available-product sets \(S_i\), and rational influence coefficients \(q_{ji}\), let \(x_{j,p}\) be the fraction of type \(j\) that has adopted product \(p\), with exposure \(E_{i,p}=\sum_j q_{ji}x_{j,p}\). A legal move transfers any positive fraction of a type's undecided mass to an available product \(p\) when \(E_{i,p}\ge\theta_i\), and adopted mass cannot switch. Find the minimum \(\sum_i\mu_i x_{i,\mathrm{top}}\) over finite legal sequences ending in a state where no undecided mass can adopt any available product.
A society is given by its support: a list of \(\tau\) types with positive binary-rational masses \(\mu_i\), normalized by \(\sum_i\mu_i=1\). Here \(\tau\) is the support size, not the number of possible types. Let \(P\) contain \(m\ge3\) products, with designated product \(\mathrm{top}\).
Input also includes a directed graph on the types without parallel edges or self-loops; write \(N(i)\) for the incoming neighbours. Edge coefficients are binary rationals \(q_{ji}\in[0,1]\), with \(\sum_{j\in N(i)}q_{ji}\le1\), and product-independent thresholds are binary rationals \(\theta_i\in(0,1]\).
Each type has a nonempty set \(S_i\subseteq P\). If \(S_i=\{p\}\), its entire mass initially adopts \(p\); otherwise its entire mass is initially undecided.
A state records adopted fractions \(x_{i,p}\ge0\), with \(\sum_{p\in P}x_{i,p}\le1\); its undecided fraction is \(u_i=1-\sum_{p\in P}x_{i,p}\). Exposure is \(E_{i,p}=\sum_{j\in N(i)}q_{ji}x_{j,p}\).
A legal move increases one \(x_{i,p}\) by any real \(\delta\in(0,u_i]\), for \(p\in S_i\), provided either \(N(i)=\varnothing\) or \(E_{i,p}\ge\theta_i\) before the move. Adopted mass never switches; the undecided remainder retains all choices in \(S_i\).
A terminal state permits no legal move. Define \(\mathrm{OPT}\) as the infimum of \(\sum_i\mu_i x_{i,\mathrm{top}}\) over terminal states reachable by finite legal sequences. A multiplicative \(\rho\)-approximation returns such a sequence with terminal cost at most \(\rho\mathrm{OPT}\), including when \(\mathrm{OPT}=0\).
Does continuous MIN-ADOPTION admit a polynomial-time multiplicative approximation with ratio \(o(\tau)\), or is achieving such a ratio NP-hard? State running times in \(m,\tau,L\), where \(L\) is the total input bit length.
Discrete MIN-ADOPTION is NP-hard to approximate within \(o(n)\), already with three products and product-independent thresholds; with two products it has an \(O(n^2)\) algorithm ([verified source](https://arxiv.org/pdf/1204.5636)).
No result settling this precise continuous approximation problem was located.
Achieving a multiplicative approximation ratio \(o(\tau)\) is NP-hard. In fact, a polynomial-time multiplicative \(\tau\)-approximation would imply \(\mathrm{P}=\mathrm{NP}\).
This holds already with three products, an acyclic graph, product-independent thresholds, and dyadic coefficients and masses. The reduction has positive optimum in every instance, so the hardness does not depend on the zero-cost requirement.
The discrete result in the [provided paper](https://arxiv.org/pdf/1204.5636) concerns indivisible adoption. The following reduction directly handles the continuous model.
Let \(\Phi\) be a three-literal conjunctive normal form formula with \(v\) variables and \(c\) clauses. We reduce from the standard NP-complete satisfiability problem for such formulas. Treat repeated literal occurrences as separate occurrences.
Use products \(P=\{A,B,\mathrm{top}\}\). Interpret complete adoption of \(A\) by a variable type as true, and complete adoption of \(B\) as false.
Create the following types.
Give \(z\) threshold \(1\); its threshold does not affect its initial adoption.
The support size is
\(\tau=v+4c+2.\)
All thresholds are product-independent. The graph is acyclic, has no self-loops or parallel edges, and the incoming coefficient sum is \(1\) at each sensor and clause type. Separate occurrence sensors ensure that repeated literals do not create parallel edges.
Let \(K\) be the least power of two satisfying \(K\ge\tau\), and set \(\varepsilon=1/K^2\). Thus \(\tau\le K<2\tau\).
Assign masses
\(\mu_z=\varepsilon,\qquad \mu_i=1/K\quad\text{for every }i\notin\{z,d\},\)
and
\(\mu_d=1-\varepsilon-(\tau-2)/K.\)
These masses sum to \(1\). Moreover,
\(\mu_d\ge 2/K-1/K^2>0,\)
because \(\tau\le K\). Every mass is dyadic and has \(O(\log\tau)\) encoding length.
We establish properties valid for arbitrary real move sizes.
Consider a positive-occurrence sensor \(H\) for variable \(V_i\). At every reachable state,
\(E_{H,A}=x_{V_i,A},\qquad E_{H,\mathrm{top}}=0.\)
The second equality holds because \(V_i\) cannot adopt \(\mathrm{top}\). Consequently, \(H\) can never adopt \(\mathrm{top}\), and it can start adopting \(A\) only when \(x_{V_i,A}=1\).
Once \(x_{V_i,A}=1\), the variable has no undecided remainder and can never change. In a terminal state, \(H\) must then adopt \(A\) completely: otherwise its positive undecided remainder would permit another legal \(A\)-move.
Conversely, if the final value satisfies \(x_{V_i,A}<1\), monotonicity implies that it was less than \(1\) throughout the sequence. Hence \(H\) could never make any move.
Therefore, in every reachable terminal state,
\(x_{H,A}=1\quad\text{if }x_{V_i,A}=1,\qquad x_{H,A}=0\quad\text{otherwise}.\)
The identical argument for a negative-occurrence sensor gives complete adoption of \(B\) exactly when its variable completely adopts \(B\).
Thus a variable may split fractionally between \(A\) and \(B\), but such a split activates neither kind of sensor.
At every reachable state, a clause type has
\(E_{W_C,\mathrm{top}}=1/4.\)
Indeed, \(z\) supplies this exposure, and its sensors never adopt \(\mathrm{top}\). Hence any positive undecided remainder at \(W_C\) permits a legal \(\mathrm{top}\)-move.
It follows that every reachable terminal state satisfies
\(x_{W_C,A}+x_{W_C,B}+x_{W_C,\mathrm{top}}=1.\)
Suppose \(\Phi\) has a satisfying assignment.
First, completely allocate each variable type to \(A\) or \(B\) according to that assignment, and allocate \(d\) to \(A\). These moves are legal because these types have no incoming neighbours.
Next, completely allocate each sensor whose literal is true to its corresponding product. Its exposure is \(1\), so the move is legal. Leave every false-literal sensor undecided; its exposure to every available product is \(0\).
Finally, for each clause choose a true literal. Its sensor supplies exposure \(1/4\) to either \(A\) or \(B\), allowing complete allocation of the clause type to that product.
The resulting state is terminal:
This construction uses at most \(\tau-1\) moves. Only \(z\) adopts \(\mathrm{top}\), so its cost is \(\varepsilon\).
Every reachable state already incurs the seed’s cost \(\varepsilon\). Consequently, for satisfiable formulas,
\(\mathrm{OPT}=\varepsilon=1/K^2,\)
and this optimum is attained.
Suppose \(\Phi\) is unsatisfiable, and consider any reachable terminal state.
Define a Boolean assignment as follows:
The first two cases cannot both occur because the adopted fractions sum to at most \(1\).
Since \(\Phi\) is unsatisfiable, some clause \(C\) is false under this assignment. Each sensor of \(C\) must be inactive:
By the sensor property, all three sensors have zero adopted fractions. Thus the final exposures of \(W_C\) to \(A\) and \(B\) are both zero.
These exposures are nondecreasing throughout a legal sequence. Therefore, they were zero throughout the sequence, and \(W_C\) could never legally adopt either \(A\) or \(B\). Since every clause type is completely allocated at terminality, this implies
\(x_{W_C,\mathrm{top}}=1.\)
Its mass is \(1/K\). Therefore every reachable terminal state has cost at least
\(\varepsilon+1/K=(K+1)\varepsilon.\)
Taking the infimum preserves this lower bound:
\(\mathrm{OPT}\ge(K+1)\varepsilon\quad\text{when }\Phi\text{ is unsatisfiable}.\)
This argument covers arbitrary fractional variable choices and arbitrary finite real-valued move sequences.
Suppose an algorithm returns a legal finite sequence ending in a terminal state and guarantees a multiplicative \(\tau\)-approximation.
On a satisfiable formula, its returned cost must satisfy
\(\mathrm{cost}\le\tau\varepsilon\le K\varepsilon=1/K<\varepsilon+1/K.\)
Consequently, no clause type in its output can completely adopt \(\mathrm{top}\): such a clause, together with the seed, would already cost \(\varepsilon+1/K\).
A satisfying assignment can be extracted from the returned sequence without evaluating its real move sizes. Whenever a positive sensor makes a move, assign its variable true; whenever a negative sensor makes a move, assign its variable false. These assignments cannot conflict, because each sensor move requires complete adoption of the corresponding variable product. Assign all remaining variables arbitrarily.
Every clause has a positive non-\(\mathrm{top}\) fraction, since it is completely allocated and is not completely assigned to \(\mathrm{top}\). Its first non-\(\mathrm{top}\) move therefore required positive exposure from a sensor representing a true literal under the extracted assignment. Hence every clause is satisfied.
We can consequently decide satisfiability by running the approximation algorithm, extracting this assignment, and checking it against \(\Phi\). An unsatisfiable formula cannot pass that check.
For a formula of input length \(B\), the reduction has:
The reduction takes \(O(B+\tau\log\tau)\) bit time. If the approximation algorithm runs in time \(T(m,\tau,L)\), the resulting satisfiability algorithm runs in
\(O\!\left(B+\tau\log\tau+T(3,\tau,L)\right),\)
including inspection of its output sequence. Thus polynomial time in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
Finally, any ratio \(o(\tau)\) is at most \(\tau\) for all sufficiently large support sizes. The finitely many smaller sizes can be handled by exhaustive satisfiability search. Therefore achieving \(o(\tau)\) is NP-hard as well.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The reduction establishes hardness even for a multiplicative \(\tau\)-approximation, and therefore for \(o(\tau)\). I found no major or minor mathematical issues.
The construction has one seed, \(v\) variable types, one dummy type, \(3c\) occurrence sensors, and \(c\) clause types. Thus
\[
\tau=v+4c+2.
\]
All choice sets are nonempty, and precisely the seed has a singleton choice set and adopts initially.
The graph is acyclic: its edges run from variables to sensors and from the seed or sensors to clause types. Distinct occurrence sensors prevent parallel edges even when a clause repeats a literal. Sensor incoming coefficients sum to \(1\), and clause incoming coefficients sum to \(4(1/4)=1\). All thresholds satisfy the required range and are product-independent.
Since \(K\) is the least power of two at least \(\tau\),
\[
\tau\le K<2\tau.
\]
There are \(\tau-2\) types receiving mass \(1/K\). The stated dummy mass therefore makes the total mass exactly \(1\). Its positivity follows from
\[
\mu_d
=1-\frac1{K^2}-\frac{\tau-2}{K}
\ge \frac2K-\frac1{K^2}>0.
\]
Every mass is dyadic and has encoding length \(O(\log\tau)\). The seed contributes the unavoidable cost \(\varepsilon=1/K^2\) in every reachable state.
For a positive sensor, its only incoming neighbour is its variable, so the stated exposure identities are exact:
\[
E_{H,A}=x_{V_i,A},\qquad E_{H,\mathrm{top}}=0.
\]
Threshold \(1\), together with \(x_{V_i,A}\le1\), means an \(A\)-move requires complete variable adoption of \(A\). The sensor can never adopt \(\mathrm{top}\).
Complete variable adoption is permanent. Consequently, terminality forces an activated sensor to finish adopting its corresponding product. Conversely, if the variable’s final corresponding fraction is less than \(1\), monotonicity prevents that sensor from having moved earlier. The negative-sensor argument has exactly the same valid hypotheses.
These conclusions correctly cover fractional variable splits and arbitrary positive real move sizes.
The seed supplies exposure \(1/4\) to \(\mathrm{top}\), and sensors never supply any additional \(\mathrm{top}\) exposure. Hence
\[
E_{W_C,\mathrm{top}}=1/4
\]
throughout every reachable sequence. Any positive clause remainder permits a legal move, so every terminal clause is completely allocated. No assumption about integral clause adoption is used.
Every move in the proposed sequence is legal. Variables and the dummy have no incoming neighbours; true-literal sensors receive exposure \(1\); and a chosen true-literal sensor supplies its clause with exposure \(1/4\).
False-literal sensors have zero exposure to both available products. The resulting state is therefore terminal. The move count is at most
\[
v+1+3c+c=\tau-1.
\]
Its only \(\mathrm{top}\) adoption is the seed’s initial adoption. Together with the unavoidable seed cost, this proves the attained optimum
\[
\mathrm{OPT}=\varepsilon.
\]
The Boolean assignment defined from complete variable adoption is consistent because a variable cannot completely adopt both products.
A clause false under that assignment cannot contain an activated sensor: complete adoption of the product corresponding to any of its literals would have made that literal true. The sensor characterization consequently gives zero final sensor adoption for every occurrence in that clause.
Its final \(A\)- and \(B\)-exposures are zero. Nonnegative coefficients and monotone adopted fractions make these exposures nondecreasing, so they were zero throughout the sequence. Threshold \(1/4\) therefore prohibited every non-\(\mathrm{top}\) move at that clause. Complete allocation at terminality forces
\[
x_{W_C,\mathrm{top}}=1.
\]
Thus every reachable terminal state costs at least
\[
\varepsilon+\frac1K=(K+1)\varepsilon.
\]
Taking an infimum preserves this bound; attainment is unnecessary.
The separating inequality is correct:
\[
\tau\varepsilon\le K\varepsilon=\frac1K
<\varepsilon+\frac1K.
\]
On a satisfiable instance, a \(\tau\)-approximation therefore cannot return any clause completely allocated to \(\mathrm{top}\).
Each terminal clause must then have made a non-\(\mathrm{top}\) move. Such a move requires positive sensor exposure, so some corresponding sensor previously moved. The extracted assignment makes that sensor’s literal true. Conflicting assignments cannot arise because sensor moves require permanent complete variable adoption.
The extraction uses move identities, without comparing or evaluating real move sizes. Checking the extracted Boolean assignment therefore provides the claimed satisfiability decision procedure.
The construction has \(m=3\), \(O(\tau)\) edges, and total encoding length \(L=O(\tau\log\tau)\). The stated reduction and decision running times are consistent with explicit input and output encodings; inspecting the returned sequence is bounded by the approximation algorithm’s running time.
A ratio \(o(\tau)\) is eventually at most \(\tau\). The exceptional bounded support sizes also bound the number of formula variables, so the stated exhaustive-search treatment is valid. This establishes the requested hardness conclusion.
No repair or additional clarification is needed. The supplied discrete-hardness result is not needed for this continuous reduction.
⟨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.