Answer: Polynomial-time solvable, with exact rational optimal exposures and equilibrium for binary-encoded rational input data.
Proposition 4.2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFinding the best set of edges to add from a specific node $w$ is NP-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \(\mu_1,\ldots,\mu_\tau\), intrinsic opinions \(s_w,s_L,s_1,\ldots,s_\tau\), a distinguished source with baseline self-weight \(1\), and a leaf cohort of mass \(\mu_L\) listening to it with unit weight, choose exposure masses \(x_i\in[0,\mu_i]\) from isolated item types. The mean-field equilibrium is \(z_w=(s_w+\sum_i x_i s_i)/(1+\sum_i x_i)\), each item remains at \(s_i\), and leaves have \(z_L=(s_L+z_w)/2\); minimize \(\mu_L((z_L-s_L)^2+(z_L-z_w)^2)\), excluding the source cost, and return an optimal \(x\) and equilibrium.
Given binary-encoded rational masses \(\mu_L,\mu_1,\ldots,\mu_\tau\geq 0\) and intrinsic opinions \(s_w,s_L,s_1,\ldots,s_\tau\), choose exposure masses \(0\leq x_i\leq\mu_i\) from otherwise isolated item types. The source has baseline self-weight \(1\); its equilibrium opinion is \(z_w=(s_w+\sum_i x_i s_i)/(1+\sum_i x_i)\). Items remain at \(s_i\), and a leaf cohort of mass \(\mu_L\) listens to the source with unit weight, so \(z_L=(s_L+z_w)/2\).
Minimize \(\mu_L((z_L-s_L)^2+(z_L-z_w)^2)\), excluding the source’s cost, and return optimal exposures and the equilibrium.
Is this optimization problem solvable in polynomial time, or is it NP-hard?
For finite agents, selecting the best set of unit-weight outgoing edges from one source is NP-hard [Bindel, Kleinberg, and Oren](https://www.cs.cornell.edu/~bindel/paper/focs11-opinions-full.pdf). Optimal weighting of one specified added edge is polynomial-time computable [Bindel, Kleinberg, and Oren](https://www.cs.cornell.edu/~bindel/papers/2015-geb.pdf).
The problem is solvable exactly in polynomial time, assuming the intrinsic opinions, like the masses, are binary-encoded rationals. The algorithm below returns rational optimal exposures and the complete equilibrium. No restriction on the signs of the intrinsic opinions is needed.
Write \(D(x)=1+\sum_{i=1}^{\tau}x_i\) and \(f(x)=(s_w+\sum_{i=1}^{\tau}x_i s_i)/D(x)\). The feasible set is the box \(B=\prod_{i=1}^{\tau}[0,\mu_i]\), and \(D(x)\geq 1\) throughout this box.
Since \(z_w=f(x)\) and \(z_L=(s_L+f(x))/2\), we have
\(\displaystyle z_L-s_L=\frac{f(x)-s_L}{2},\qquad z_L-z_w=-\frac{f(x)-s_L}{2}.\)
Consequently, the objective is exactly
\(\displaystyle C(x)=\frac{\mu_L}{2}\bigl(f(x)-s_L\bigr)^2.\)
If \(\mu_L=0\), every feasible exposure vector is optimal; return \(x_i=0\), \(z_w=s_w\), \(z_L=(s_L+s_w)/2\), and \(z_i=s_i\). Henceforth suppose \(\mu_L>0\).
Because \(B\) is nonempty and compact and \(f\) is continuous, the quantities \(a=\min_{x\in B}f(x)\) and \(b=\max_{x\in B}f(x)\) exist.
Lemma. A minimizer can be chosen to expose every type with \(s_i<a\) fully and every other type not at all. A maximizer can be chosen to expose every type with \(s_i>b\) fully and every other type not at all.
Proof. For any feasible change of a single coordinate by \(\delta\), direct subtraction gives
\(\displaystyle f(x+\delta e_i)-f(x)=\frac{\delta(s_i-f(x))}{D(x)+\delta}.\)
The denominator is positive because the modified vector is feasible.
At a minimizer \(x\), we have \(f(x)=a\). If \(s_i<a\) and \(x_i<\mu_i\), a positive feasible change strictly decreases \(f\), a contradiction. Thus \(x_i=\mu_i\). If \(s_i>a\) and \(x_i>0\), a negative feasible change strictly decreases \(f\), also a contradiction. Thus \(x_i=0\). When \(s_i=a\), setting \(x_i=0\) leaves \(f\) unchanged by the same identity. Performing these changes proves the minimum assertion.
At a maximizer, a positive feasible change strictly increases \(f\) when \(s_i>b\), and a negative feasible change strictly increases \(f\) when \(s_i<b\). Therefore those coordinates must respectively be full and zero. Coordinates with \(s_i=b\) can again be set to zero without changing \(f\). This proves the maximum assertion.
Now sort the indices so that \(s_{\pi(1)}\leq\cdots\leq s_{\pi(\tau)}\). Define the prefix ratios
\(\displaystyle A_k=\frac{s_w+\sum_{j=1}^{k}\mu_{\pi(j)}s_{\pi(j)}}{1+\sum_{j=1}^{k}\mu_{\pi(j)}}\qquad(0\leq k\leq\tau).\)
The empty prefix has \(A_0=s_w\). Every prefix is feasible, and the lemma supplies a minimizing prefix: precisely the types with opinions strictly below \(a\). Hence
\(\displaystyle a=\min_{0\leq k\leq\tau}A_k.\)
Similarly, sort in descending order, \(s_{\rho(1)}\geq\cdots\geq s_{\rho(\tau)}\), and compute
\(\displaystyle B_k=\frac{s_w+\sum_{j=1}^{k}\mu_{\rho(j)}s_{\rho(j)}}{1+\sum_{j=1}^{k}\mu_{\rho(j)}}.\)
Then \(b=\max_{0\leq k\leq\tau}B_k\). Save the corresponding feasible exposure vectors \(x^{-}\) and \(x^{+}\), attaining \(a\) and \(b\).
This construction also covers zero item masses and the case of no item types.
The desired source opinion is the closest point to \(s_L\) in the interval \([a,b]\):
\(\displaystyle y=\min\{b,\max\{a,s_L\}\}.\)
If \(a=b\), return \(x^{*}=x^{-}\). Otherwise define
\(\displaystyle D_-=1+\sum_i x_i^{-},\qquad D_+=1+\sum_i x_i^{+},\)
\(\displaystyle t=\frac{D_-(y-a)}{D_-(y-a)+D_+(b-y)},\qquad x^{*}=(1-t)x^{-}+t x^{+}.\)
Since \(a\leq y\leq b\) and \(a<b\), the denominator defining \(t\) is positive and \(0\leq t\leq1\). Thus \(x^{*}\in B\).
The numerator and denominator of \(f\) are affine functions of the exposures. Therefore
\(\displaystyle f(x^{*})=\frac{(1-t)D_-a+tD_+b}{(1-t)D_-+tD_+}.\)
The definition of \(t\) gives
\(\displaystyle (1-t)D_-(y-a)=tD_+(b-y),\)
which, upon rearrangement, shows that \(f(x^{*})=y\).
This calculation proves that every point of \([a,b]\) is attainable. By the definitions of \(a\) and \(b\), no point outside it is attainable. Minimizing \(C(x)\) is therefore exactly the problem of minimizing the squared distance to \(s_L\) over this interval, whose minimizer is \(y\).
The returned equilibrium and optimal value are
\(\displaystyle z_w^{*}=y,\qquad z_L^{*}=\frac{s_L+y}{2},\qquad z_i^{*}=s_i,\qquad C^{*}=\frac{\mu_L}{2}(y-s_L)^2.\)
Let \(L\) denote the total binary input length. Sorting requires polynomially many rational comparisons. Prefix sums compute all candidate ratios using linearly many rational arithmetic operations after sorting.
Their bit lengths are polynomial in \(L\): each prefix numerator or denominator is a sum of input rationals or products of two input rationals. A common denominator can be formed by multiplying their denominators; its bit length is at most the sum of the constituent bit lengths. Numerators likewise have polynomial bit length. Exact comparisons use cross multiplication of integers of polynomial bit length.
The interpolation formula uses a constant number of additional rational operations to compute \(t\), followed by a constant number per exposure coordinate. Thus the exposures, equilibrium, and objective value all have polynomial bit length and are computable in polynomial time.
The cited hardness result concerns selecting a discrete set of unit-weight edges; its source-cost-excluded construction is stated in Claim 6.1 of the [2011 paper](https://www.cs.cornell.edu/~bindel/paper/focs11-opinions-full.pdf).
Here the exposures vary continuously throughout a box. In particular, the interpolation in Section 3 is feasible, whereas it need not represent a discrete edge set. The proof above therefore establishes tractability for the stated continuous optimization problem without contradicting that hardness result.
⟨structured verdict parsed — rendered above⟩
Verdict: proved under the explicitly stated rational-input assumption. The argument correctly establishes an exact polynomial-time algorithm returning optimal exposures and the equilibrium. I found no mathematical errors or gaps requiring repair.
The task explicitly specifies binary encoding for masses but leaves the representation of intrinsic opinions unspecified. The prover expressly assumes binary-encoded rational opinions. Its complexity conclusion is valid under that assumption; it does not claim a bit-complexity result for unspecified representations of arbitrary real opinions.
Both differences involving the leaf opinion are computed correctly. Squaring and adding gives \(C(x)=\frac{\mu_L}{2}(f(x)-s_L)^2\), with the correct factor.
When \(\mu_L=0\), the objective vanishes for every feasible vector. The proposed zero exposures and reported equilibrium satisfy all the given equations. Restricting subsequent optimization to \(\mu_L>0\) is justified.
The box is nonempty because zero exposures are feasible, and it is compact because there are finitely many coordinates with finite bounds. The denominator satisfies \(D(x)\geq1\), so \(f\) is continuous throughout the box. The hypotheses of the extreme value theorem are therefore satisfied.
With no item types, the feasible set consists of the unique empty exposure vector, so this reasoning still applies.
The identity
\(f(x+\delta e_i)-f(x)=\frac{\delta(s_i-f(x))}{D(x)+\delta}\)
is algebraically correct. Feasibility of the modified vector ensures its denominator is at least one.
At a minimum, increasing an unsaturated coordinate with \(s_i<a\) strictly decreases the ratio; decreasing a positive coordinate with \(s_i>a\) also strictly decreases it. Both contradict minimality. The corresponding maximum arguments have the correct signs.
If \(s_i=a\), setting that coordinate to zero preserves the minimum value. Performing these changes sequentially is valid because the value remains \(a\) after each change. The same reasoning applies at the maximum with \(s_i=b\).
Zero masses do not create exceptions: their coordinates are necessarily zero and also fully exposed in the sense \(x_i=\mu_i\).
In ascending order, all types with \(s_i<a\) form a prefix. The lemma supplies a minimizer represented by this prefix, and every enumerated prefix is feasible. These two facts establish the asserted equality between \(a\) and the smallest prefix ratio.
Descending order gives the corresponding maximizing prefix. Ties cause no difficulty because the strict threshold excludes the entire group whose opinions equal the extremal value.
The empty prefix handles both choosing no exposures and having no item types. Retaining a prefix attaining each extremum supplies the claimed vectors \(x^{-}\) and \(x^{+}\).
For \(a<b\), both summands in the denominator defining \(t\) are nonnegative, and at least one is positive. Thus \(t\) is defined and belongs to \([0,1]\). Convexity of the box makes \(x^{*}\) feasible.
The displayed expression for \(f(x^{*})\) correctly uses the affinity of its numerator and denominator. The identity involving \(t\) follows from its definition and rearranges to \(f(x^{*})=y\).
Endpoint cases are covered: \(y=a\) gives \(t=0\), and \(y=b\) gives \(t=1\). When \(a=b\), the separately returned vector attains the only possible source opinion, which also equals the clipped target \(y\).
Consequently, the attainable source opinions are exactly \([a,b]\). Clipping \(s_L\) to that interval minimizes the squared distance, and multiplying by the positive constant \(\mu_L/2\) preserves minimizers. All reported equilibrium coordinates and the optimal value follow correctly.
The proof controls both operation counts and operand sizes. Each prefix sum contains only input rationals or products of two input rationals. The common-denominator argument bounds their representation lengths polynomially in the total input length, including the opinions.
Exact rational comparisons by cross multiplication therefore involve polynomial-size integers. There are polynomially many comparisons and arithmetic operations. The interpolation uses only a fixed number of operations on polynomial-size rationals, followed by a fixed number per coordinate. This establishes polynomial running time and polynomial output length.
The algorithm never expands a binary-encoded mass into individual agents.
Claim 6.1 concerns discrete outgoing-edge selection with the source’s cost excluded, as stated in the prover’s discussion. [The cited paper, Appendix 6](https://www.cs.cornell.edu/~bindel/paper/focs11-opinions-full.pdf) supports that attribution.
The continuous interpolation used here need not be a feasible discrete selection. Thus the polynomial-time conclusion does not contradict the cited hardness result. No external hardness theorem is used to justify the algorithm itself.
Repair feedback: None is required. Preserve the explicit rational-opinion encoding assumption in any standalone statement of the result.
⟨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.