Answer: \(\mathrm{NP}\)-hard under polynomial-time Turing reductions; more precisely, \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions.
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet G = (V, E) be an (n, d, λ)-graph and sup- pose that d2 λ2 > 1 δ2µ(1 −µ + 2δµ). Then for any strong adversary as above the majority gives the truth. In particular, if G is a Ramanujan graph, that is, λ ≤2 √ d −1 this is the case provided d ≥ 4 δ2µ(1 −µ + 2δµ).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational role masses \(w_i\), a symmetric nonnegative contact matrix \(W_{ij}\), and parameters \(\mu,\delta\), the adversary chooses red-expert and blue-expert masses \(a_i,b_i\) with \(0\leq a_i+b_i\leq w_i\), \(\sum_i a_i=(1/2+\delta)\mu\), and \(\sum_i b_i=(1/2-\delta)\mu\). Each nonexpert of role \(i\) follows the sign of \(q_i=\sum_j W_{ij}(a_j-b_j)\), splitting evenly on a tie. Determine whether every feasible adversary choice leaves strictly more than half the population believing the truth.
A society is given by its support: \(\tau\geq1\) roles with positive binary rational masses \(w_i\), where \(\sum_i w_i=1\); \(\tau\) is the support size, not the number of possible types. There are \(m=2\) opinions, red (truth) and blue.
The input also contains a symmetric matrix \(W\in\mathbb{Q}_{\geq0}^{\tau\times\tau}\) and binary rational parameters \(0<\mu,\delta<1/2\). Diagonal entries are allowed and represent contact within a role; no regularity or spectral promise is imposed. Let \(L\) be the total input bit length.
An adversary chooses real masses \(a_i,b_i\geq0\) satisfying \(a_i+b_i\leq w_i\), \(\sum_i a_i=(1/2+\delta)\mu\), and \(\sum_i b_i=(1/2-\delta)\mu\). These expert masses retain their assigned opinions.
There is one propagation round: the remaining mass of role \(i\) becomes red if \(q_i=\sum_jW_{ij}(a_j-b_j)>0\), blue if \(q_i<0\), and splits equally if \(q_i=0\), including when there is no expert contact.
Define \(h(x)=1\) for \(x>0\), \(h(x)=0\) for \(x<0\), and \(h(0)=1/2\). The final truthful mass is \(T(a,b)=\sum_i a_i+\sum_i(w_i-a_i-b_i)h(q_i)\). Robustness means \(T(a,b)>1/2\) for every feasible adversary choice.
Is deciding robustness in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard under polynomial-time Turing reductions?
For finite societies, a verified sufficient condition guarantees robustness on regular graphs: \(d^2>\lambda^2/[\delta^2\mu(1-\mu+2\delta\mu)]\), where \(d\) is the degree and \(\lambda\) bounds the absolute nonprincipal adjacency eigenvalues. This is a robustness guarantee, not a general decision algorithm. [Source](https://www.ijcai.org/Proceedings/15/Papers/291.pdf)
Discrete minimization of the expected truthful population is reported \(\mathrm{NP}\)-hard even on disjoint unions of cliques; this concerns optimization rather than the fixed majority threshold. [Source](https://edoc.ub.uni-muenchen.de/22969/1/Daknama_Rami.pdf)
No result settling the exact mass-based decision problem was located.
Deciding robustness is \(\mathrm{NP}\)-hard under polynomial-time Turing reductions. More precisely, robustness is \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions.
The proof below treats arbitrary real adversary allocations and the specified tie rule exactly. The hardness construction uses strictly positive role masses and a symmetric matrix whose entries belong to \(\{1/2,3/4,1,5/4,3/2\}\). All constructed numerical inputs are dyadic rationals.
Write \(\mathrm{NONROBUST}\) for the existence of a feasible allocation satisfying \(T(a,b)\leq1/2\)\). Define
\(A=(1/2+\delta)\mu,\qquad B=(1/2-\delta)\mu,\qquad g(x)=1-h(x).\)
Thus \(g(x)\)\) equals \(1\)\) for negative \(x\)\), \(0\)\) for positive \(x\)\), and \(1/2\)\) at zero. For any feasible allocation, define its nominal blue mass
\(F(a,b)=\sum_i w_i g(q_i).\)
This counts the blue outcome of each entire role, including its experts. The actual blue mass is
\(1-T(a,b)=B+\sum_i(w_i-a_i-b_i)g(q_i) =F(a,b)+B-\sum_i(a_i+b_i)g(q_i).\)
Because \(0\leq g(q_i)\leq1\)\) and \(\sum_i(a_i+b_i)=\mu\)\), this gives
\(1-F(a,b)-B\leq T(a,b)\leq1-F(a,b)+A.\)
In particular,
\[1-F(a,b)-\mu\leq T(a,b)\leq1-F(a,b)+\mu. \tag{1}\]
Consequently, every nonrobust allocation satisfies
\[F(a,b)\geq1/2-\mu. \tag{2}\]
These inequalities apply even when the adversary puts experts on the roles used as tests in the construction.
We reduce from weighted maximum cut:
This decision problem is \(\mathrm{NP}\)-complete; it is the weighted MAX CUT problem in [Karp’s *Reducibility Among Combinatorial Problems*](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
Let \(n=|V|\)\), \(r=|E|\)\), and \(M=\sum_e\ell_e\)\). We may restrict to \(n\geq2\)\), \(r\geq1\)\), and \(1\leq K\leq M\)\): inputs outside these conditions are immediately decidable.
Set \(p=n+1\)\). Choose powers of two \(N,H,J\)\), each the smallest satisfying its respective inequality,
\(N\geq8n,\qquad H\geq4(M+1),\qquad J\geq64p.\)
Define
\(C=\frac1N,\qquad D=\frac{C}{H},\qquad v=\frac{D}{J},\qquad \mu=\frac{D}{16},\qquad \delta=\frac2J.\)
The fixed total red-minus-blue expert mass is therefore
\[s=A-B=2\delta\mu=\frac v4. \tag{3}\]
We will use the following bounds:
\[nC\leq\frac18,\qquad MD<\frac C4,\qquad D\leq\frac C8\leq\frac1{64},\qquad pv\leq\frac D{64}. \tag{4}\]
In particular,
\[\mu+pv\leq\frac{5D}{64}<\frac D2,\qquad \mu+pv<\frac C4,\qquad \mu+pv<\frac3{32}. \tag{5}\]
For the middle inequality, use \(D\leq C/8\)\); for the last, use \(D\leq1/64\)\).
The parameters satisfy \(0<\mu,\delta<1/2\)\).
Construct the following distinct roles.
| Roles | Number | Mass of each |
|---|---:|---:|
| Signal roles \(S_0\)\) and \(S_u\)\), \(u\in V\)\) | \(p\)\) | \(v\)\) |
| Vertex tests \(P_u,N_u\)\), \(u\in V\)\) | \(2n\)\) | \(C\)\) |
| Edge tests \(P_e,N_e\)\), \(e\in E\)\) | \(2r\)\) | \(\ell_eD\)\) |
| Guard role \(Z\)\) | \(1\)\) | \(\Gamma\)\) |
| Reservoir role \(R\)\) | \(1\)\) | \(\omega\)\) |
Define
\(\Gamma=\frac12-nC-\left(K-\frac12\right)D,\)
and
\(\omega=1-pv-2nC-2MD-\Gamma.\)
The masses sum to one. They are all strictly positive. Indeed,
\(\Gamma>\frac12-\frac18-\frac C4\geq\frac{11}{32},\qquad \Gamma<\frac12.\)
Also,
\(\omega=\frac12-nC-\left(2M-K+\frac12\right)D-pv >\frac12-\frac18-2MD-pv >\frac5{16}-pv>\frac14.\)
Here the first strict inequality uses \(K\geq1\)\), and the remaining inequalities follow from (4).
The support size is
\(\tau=3n+2r+3.\)
Initially set every entry of \(W\)\), including every diagonal entry, equal to \(1\)\). Make the following changes, always changing the transposed entry as well.
For each vertex \(u\)\), set
\(W_{P_u,S_u}=\frac32,\qquad W_{N_u,S_u}=\frac12.\)
For each edge \(e=\{u,v\}\)\), choose either ordering of its endpoints and set
\(W_{P_e,S_u}=\frac54,\qquad W_{P_e,S_v}=\frac34,\)
\(W_{N_e,S_u}=\frac34,\qquad W_{N_e,S_v}=\frac54.\)
Finally, set
\(W_{Z,S_0}=\frac32.\)
The resulting matrix is symmetric and strictly positive.
For a feasible allocation, put \(x_i=a_i-b_i\)\). Feasibility and (3) imply
\(\sum_i x_i=s,\qquad |x_{S_u}|\leq v,\qquad |x_{S_0}|\leq v.\)
The all-ones baseline contributes exactly \(s\)\) to every row. Hence the test equations are
\[q_{P_u}=s+\frac{x_{S_u}}2,\qquad q_{N_u}=s-\frac{x_{S_u}}2, \tag{6}\]
\[q_{P_e}=s+\frac{x_{S_u}-x_{S_v}}4,\qquad q_{N_e}=s-\frac{x_{S_u}-x_{S_v}}4, \tag{7}\]
and
\[q_Z=s+\frac{x_{S_0}}2,\qquad q_R=s>0. \tag{8}\]
These equations hold regardless of where the adversary places its experts. The symmetric modifications also affect signal-role rows, but those roles have total mass only \(pv\)\).
Define
\(r_u=g(q_{P_u})+g(q_{N_u}),\qquad t_e=g(q_{P_e})+g(q_{N_e}),\qquad z=g(q_Z).\)
Since \(s=v/4\)\), equation (6) gives:
Similarly, equation (7) gives:
In particular, \(0\leq r_u,t_e\leq1\)\). Equation (8) gives \(z=1\)\) exactly when \(x_{S_0}<-v/2\)\); otherwise \(z\leq1/2\)\).
Let \(F_{\mathrm{sig}}\)\) denote the signal roles’ contribution to nominal blue mass. Because the reservoir is red, we have the exact decomposition
\[F=\Gamma z+C\sum_u r_u+D\sum_e\ell_e t_e+F_{\mathrm{sig}}, \qquad 0\leq F_{\mathrm{sig}}\leq pv. \tag{9}\]
We prove
\[\text{there is a cut of weight at least }K \quad\Longleftrightarrow\quad \text{the constructed society is nonrobust}. \tag{10}\]
Suppose a cut has weight \(\kappa\geq K\)\). Set \(x_{S_u}=v\)\) on one side and \(x_{S_u}=-v\)\) on the other, and set \(x_{S_0}=-v\)\).
Realize these choices by making each signal role entirely red experts or entirely blue experts. All other test roles receive no experts. Put the remaining red and blue expert masses in the reservoir.
This allocation is feasible. To check the quotas, note that
\(\mu=\frac D{16}\geq4pv,\qquad B=\frac\mu2-\frac v8\geq2pv-\frac v8>pv,\)
and \(A>B\)\). Neither color uses more than \(pv\)\) among signal roles, so both remaining quotas are nonnegative. Their sum is \(\mu-pv\leq\mu<\omega\)\), so they fit in the reservoir.
Every vertex-test pair contributes \(r_u=1\)\), and the guard has \(z=1\)\). An edge-test pair contributes \(t_e=1\)\) exactly when its edge crosses the chosen cut: its signal difference is then \(2v\)\), whereas a noncrossing edge has difference zero.
Thus, by (9),
\(F\geq\Gamma+nC+\kappa D \geq\Gamma+nC+KD =\frac12+\frac D2.\)
Using (1),
\(T\leq1-F+\mu \leq\frac12-\frac D2+\frac D{16} =\frac12-\frac{7D}{16}<\frac12.\)
The society is nonrobust.
Conversely, suppose an arbitrary feasible real allocation is nonrobust. Equation (2) gives \(F\geq1/2-\mu\)\).
If \(z\leq1/2\)\), then (9) and (4) give
\(F\leq\frac{\Gamma}{2}+nC+MD+pv \leq\frac14+\frac18+\frac1{32}+pv =\frac{13}{32}+pv.\)
By (5), this is strictly less than \(1/2-\mu\)\), a contradiction. Therefore \(z=1\)\).
Suppose some vertex \(u\)\) satisfies \(|x_{S_u}|\leq v/2\)\). Its test pair then has \(r_u\leq1/2\)\), including the equality case. Equation (9) gives
\(F\leq\Gamma+\left(n-\frac12\right)C+MD+pv\)
\(=\frac12-\frac C2+\left(M-K+\frac12\right)D+pv <\frac12-\frac C4+pv.\)
The strict inequality follows from \(K\geq1\)\) and \(MD<C/4\)\). By (5), the last expression is strictly less than \(1/2-\mu\)\), again a contradiction.
Consequently,
\[|x_{S_u}|>v/2\quad\text{for every }u\in V. \tag{11}\]
Partition the vertices according to the sign of \(x_{S_u}\)\); these signs are nonzero by (11).
For endpoints with opposite signs, (11) implies
\(|x_{S_u}-x_{S_v}|>v,\)
so \(t_e=1\)\).
For endpoints with the same sign, their values lie either in \((v/2,v]\)\) or in \([-v,-v/2)\)\). Thus
\(|x_{S_u}-x_{S_v}|<v/2<v,\)
so \(t_e=0\)\). In particular, no edge test is tied.
Let \(\kappa\)\) be this cut’s integer weight. Since every \(r_u=1\)\) and \(z=1\)\), equation (9) becomes
\(F=\Gamma+nC+\kappa D+F_{\mathrm{sig}}.\)
If \(\kappa<K\)\), integrality gives \(\kappa\leq K-1\)\), whence
\(F\leq\Gamma+nC+(K-1)D+pv =\frac12-\frac D2+pv <\frac12-\mu,\)
where the last inequality uses (5). This contradicts (2). Hence \(\kappa\geq K\)\), completing the proof of (10).
There are \(3n+2r+3\)\) roles. The binary lengths of \(N,H,J\)\) are bounded by \(O(\log n+\log M)\)\). Every constructed mass and parameter therefore has polynomial encoding length, even when the integer edge weights are large. No edge weight is expanded into multiple roles.
The matrix has polynomially many entries, each drawn from the fixed five-element set stated above. Thus (10) is a polynomial-time many-one reduction to \(\mathrm{NONROBUST}\).
It remains to prove \(\mathrm{NONROBUST}\in\mathrm{NP}\)\) for the general input problem.
Suppose a real feasible allocation satisfies \(T\leq1/2\)\). Fix its sign pattern \(\sigma_i\in\{-1,0,1\}\)\). Let \(c_i\)\) be the corresponding value of \(h(q_i)\)\), namely \(0\)\), \(1/2\)\), or \(1\)\).
Consider the rational linear program with variables \(a_i,b_i,\varepsilon\)\), containing:
\(\sum_i a_i+\sum_i(w_i-a_i-b_i)c_i\leq1/2\)\).
Maximize \(\varepsilon\)\).
The given real allocation extends to a feasible point with positive \(\varepsilon\)\): take the minimum of \(1\)\) and its finitely many nonzero \(|q_i|\)\). If every \(q_i=0\)\), take \(\varepsilon=1\)\).
This linear program has a bounded feasible polytope, because \(0\leq a_i,b_i\leq w_i\)\) and \(0\leq\varepsilon\leq1\)\). Its optimum is positive and is attained at a vertex. That vertex has rational coordinates of polynomial binary length: after clearing denominators, its coordinates are obtained from a nonsingular system of at most \(2\tau+1\)\) active constraints, and Cramer’s rule bounds their lengths polynomially in the constraint encoding length.
At this vertex, positive \(\varepsilon\)\) ensures the prescribed signs are exact. Its rational allocation therefore satisfies the original objective inequality \(T\leq1/2\)\).
A verifier can check these rational masses, all contact sums, their exact signs, and the resulting truthful mass in polynomial time. Thus \(\mathrm{NONROBUST}\in\mathrm{NP}\)\). This argument does not assume that the discontinuous objective attains a global minimum.
The reduction proves that \(\mathrm{NONROBUST}\) is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions. Section 6 proves membership, so \(\mathrm{NONROBUST}\) is \(\mathrm{NP}\)-complete, and robustness is \(\mathrm{coNP}\)-complete.
A robustness oracle decides weighted maximum cut with one query to the constructed society, followed by negating the answer. Therefore robustness is \(\mathrm{NP}\)-hard under polynomial-time Turing reductions, as requested. A polynomial-time algorithm in the stated input parameters would imply \(\mathrm{P}=\mathrm{NP}\)\).
⟨structured verdict parsed — rendered above⟩
The proof resolves the assigned continuous decision problem. The reduction and certificate argument are correct: robustness is \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions and therefore \(\mathrm{NP}\)-hard under polynomial-time Turing reductions. I found no mathematical gap requiring repair.
Write \(E=\sum_i(a_i+b_i)g(q_i)\). Feasibility gives \(0\leq E\leq\mu\), and the stated identity yields
\(T=1-F-B+E\).
Consequently,
\(1-F-B\leq T\leq1-F+A\),
because \(\mu-B=A\). The weaker bounds in (1) follow from \(A,B\leq\mu\).
In particular, \(T\leq1/2\) implies \(F\geq1/2-B\geq1/2-\mu\), establishing (2). These identities include experts placed on test roles; no restriction on their placement is assumed.
The cited source establishes NP-completeness of the decision version of weighted maximum cut, with positive integer weights and a fixed integer threshold. This matches the stated source problem, rather than merely an optimization problem. [Karp, *Reducibility Among Combinatorial Problems*](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
The restrictions \(n\geq2\), \(r\geq1\), and \(1\leq K\leq M\) exclude only immediately decidable cases. They therefore do not undermine source hardness. The construction uses the usual loopless undirected graph interpretation of this source problem.
Since \(M\geq1\), the choices imply \(H\geq8\). Thus
\(nC\leq1/8\),
\(MD=C(M/H)<C/4\),
and \(D\leq C/8\leq1/64\).
Also, \(J\geq64p\) gives \(pv\leq D/64\).
The prescribed expert imbalance is exactly
\(2\delta\mu=2(2/J)(D/16)=v/4\).
Finally,
\(\mu+pv\leq5D/64<D/2\).
Combining this with \(D\leq C/8\) proves \(\mu+pv<C/4\), and \(D\leq1/64\) proves \(\mu+pv<3/32\). All three bounds in (5) are valid. Both parameters are strictly between zero and \(1/2\).
All signal, vertex-test, and edge-test masses are positive. For the guard,
\(0<(K-1/2)D<MD<C/4\), giving the stated lower bound on \(\Gamma\), while its definition gives \(\Gamma<1/2\).
The reservoir calculation is also valid. The inequality \(K\geq1\) implies \(2M-K+1/2<2M\), and the subsequent bounds establish \(\omega>1/4\). The masses sum exactly to one.
The role count is
\(p+2n+2r+2=3n+2r+3\).
All masses and parameters are dyadic rationals.
Every matrix modification is applied symmetrically, remains strictly positive, and belongs to the advertised five-element set. The unchanged diagonal entries equal one, which is permitted by the task.
Since \(\sum_i x_i=A-B=s\), the all-ones baseline contributes \(s\) to every contact sum.
Each test row receives exactly the deviations specified in (6)–(8). Applying the modifications symmetrically changes the signal rows as well, but introduces no additional deviations into the test, guard, or reservoir rows.
Therefore those equations remain exact even when experts occupy tests or the guard. The reservoir always has \(q_R=s>0\). Bounding all signal contributions by their total role mass \(pv\) is valid regardless of their contact signs or expert occupancy.
For a vertex pair, \(q_{P_u}+q_{N_u}=2s>0\). Substitution of \(s=v/4\) gives the three stated cases for \(r_u\): one negative contact beyond the threshold, one zero contact at the threshold, and two positive contacts inside it.
The same calculation gives the three cases for \(t_e\), with threshold \(v\) on the signal difference.
The guard has negative contact exactly when \(x_{S_0}<-v/2\); equality gives \(z=1/2\), and larger values give \(z=0\).
Consequently, (9) is an exact decomposition, including all possible ties.
Setting every signal difference to either \(v\) or \(-v\) is compatible with its role capacity: the role is filled entirely with experts of the corresponding color.
The quota check is sufficient. From \(pv\leq D/64\),
\(\mu=D/16\geq4pv\), and therefore
\(B=\mu/2-v/8\geq2pv-v/8>pv\).
The final strict inequality holds since \(p=n+1\geq3\). As \(A>B\), neither color quota can be exhausted by its signal placements.
The remaining expert mass is \(\mu-pv\), which is nonnegative and fits in the reservoir because \(\mu<\omega\). Placing the remaining quotas there also ensures the required total imbalance \(s\).
All vertex pairs and the guard contribute one. An edge pair contributes one precisely for a crossing edge. Thus
\(F\geq1/2+D/2\).
Equation (1) then gives
\(T\leq1/2-7D/16<1/2\).
This proves nonrobustness with a strict margin.
A nonrobust allocation must satisfy \(F\geq1/2-\mu\).
If \(z\leq1/2\), the stated estimate
\(F\leq13/32+pv\)
follows from \(\Gamma<1/2\), \(nC\leq1/8\), and \(MD<C/4\leq1/32\). Since \(\mu+pv<3/32\), this contradicts the necessary lower bound. Hence \(z=1\).
If any vertex satisfies \(|x_{S_u}|\leq v/2\), its contribution loses at least \(C/2\). The resulting estimate is
\(F\leq1/2-C/2+(M-K+1/2)D+pv<1/2-C/4+pv\).
Here \(K\geq1\) and \(MD<C/4\) justify the strict inequality. The bound \(\mu+pv<C/4\) again produces a contradiction. Thus every vertex satisfies (11).
Opposite signs then give a difference strictly greater than \(v\), while equal signs give a difference strictly less than \(v/2\). Consequently, edge contributions are exactly the indicators of the induced cut, with no edge ties.
If that cut has weight below \(K\), integrality gives \(\kappa\leq K-1\), hence
\(F\leq1/2-D/2+pv<1/2-\mu\).
This contradicts nonrobustness. Both directions of (10) are established.
The powers \(N,H,J\) have binary lengths bounded polynomially in the explicitly represented graph input. Computing \(M\) from binary edge weights also requires only polynomially many bits.
Products and differences defining the masses preserve polynomial encoding length. There are polynomially many roles and matrix entries, and each matrix entry has constant encoding length. Large edge weights are retained numerically rather than expanded into additional roles.
Thus the construction is a polynomial-time many-one reduction to \(\mathrm{NONROBUST}\).
Fixing the sign pattern makes the truthful-mass expression linear with rational coefficients. The margin variable correctly represents strict positive and negative contact signs while leaving zero contacts as exact equalities.
Any real nonrobust allocation admits a positive margin: there are only finitely many nonzero contact sums. The all-zero case is explicitly handled by taking \(\varepsilon=1\).
The resulting polytope is nonempty and bounded. Therefore the linear objective attains its positive maximum at a vertex, including when the polytope has lower dimension.
The vertex-coordinate argument applies: a vertex has \(2\tau+1\) linearly independent active constraint normals determining its coordinates. Clearing rational denominators preserves polynomial coefficient encoding length, and Cramer’s rule gives polynomial binary lengths for the coordinates.
Positive \(\varepsilon\) preserves the exact sign pattern. The rational allocation therefore satisfies the original objective inequality, including the specified tie rule. Exact rational arithmetic verifies all constraints and the resulting truthful mass in polynomial time. Hence \(\mathrm{NONROBUST}\in\mathrm{NP}\).
The claimed complexity conclusion follows. Complementation gives \(\mathrm{coNP}\)-completeness of robustness under many-one reductions. A robustness oracle answers weighted maximum cut by one query followed by negation, establishing the requested Turing hardness. No additional mathematical 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.