Answer: \(\mathrm{NP}\text{-hard}\); a polynomial-time algorithm with the stated guarantee would imply \(\mathrm{P}=\mathrm{NP}\).
Proposition 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximatePFD is an anytime algorithm. By lemma 2, at iteration t + 2d and t + 2d + δ (δ ≥0) each agent is aware of the P.pbest and P.gbest up to iteration t and t+δ respectively. Let us assume, P.pbest and P.gbest at iteration t+2d+δ ≥t+2d. But for any δ ≥0, t+2d+δ >= t + 2d and P.pbest and P.gbest only gets updated if a better solution is found.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many types \(T\) with rational masses \(\mu_t\), compact rational action intervals \(D_t\), and rational polynomial unary and pairwise costs, determine the complexity of producing rational finite-support action distributions \(\pi_t\) whose per-capita cost is within a supplied rational \(\varepsilon>0\) of the global minimum, where \(J(\pi)=\sum_t\mu_t\int u_t(x)\,d\pi_t(x)+\sum_{t,s}\mu_t w_{ts}\int\!\int f_{ts}(x,y)\,d\pi_t(x)\,d\pi_s(y)\).
A society is given by its support: a list \(T\) of \(\tau\geq1\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type controls one scalar action, so \(m=\tau\), with domain \(D_t=[a_t,b_t]\), where \(a_t,b_t\in\mathbb Q\) and \(a_t\leq b_t\). Inputs include nonnegative rational interaction weights \(w_{ts}\) and unary and pairwise polynomials \(u_t,f_{ts}\) with rational coefficients of either sign, given by explicit dense coefficient arrays; let \(d\) be their maximum degree and \(L\) the total input bit length, including a binary-rational \(\varepsilon>0\).
A feasible choice assigns each type a Borel probability measure \(\pi_t\) on \(D_t\). Define \(J(\pi)=\sum_{t\in T}\mu_t\int u_t(x)\,d\pi_t(x)+\sum_{t,s\in T}\mu_t w_{ts}\iint f_{ts}(x,y)\,d\pi_t(x)\,d\pi_s(y)\). The pair sum is ordered, with no symmetry assumption; even when \(t=s\), the two actions are independent draws.
The computational problem is to produce measures with finite rational action supports and nonnegative rational probabilities summing to \(1\), satisfying \(J(\pi)\leq J^*+\varepsilon\), where \(J^*=\min_{\rho_t\in\mathcal P(D_t)}J(\rho)\).
Is this additive approximation problem solvable in polynomial time in \(m,\tau,d,L\), or is it NP-hard?
For finite-agent F-DCOPs, PFD has an anytime guarantee: its incumbent objective value never increases; this does not establish polynomial-time global approximation ([source](https://cdn.aaai.org/ojs/6198/6198-13-9423-1-10-20200516.pdf)).
No complexity classification for exactly this distribution-valued formulation was located in the search.
The problem is \(\mathrm{NP}\text{-hard}\), even with \(d=2\), all domains equal to \([0,1]\), equal dyadic masses, zero unary terms, zero self-interactions, and the fixed tolerance \(\varepsilon=1/4\). Consequently, a polynomial-time algorithm with the stated guarantee would imply \(\mathrm{P}=\mathrm{NP}\).
We use the known \(\mathrm{NP}\)-completeness of the following decision problem: given a simple unweighted undirected graph \(G=(V,E)\) and an integer \(K\), determine whether some cut has at least \(K\) edges. This is Simple Max Cut in [Garey, Johnson, and Stockmeyer](https://doi.org/10.1016/0304-3975(76)90059-1).
Let \(V=\{1,\ldots,n\}\), with \(n\geq1\), and write \(M(G)\) for the maximum cut size. Choose
\( N=2^{\lceil\log_2 n\rceil}. \)
Add isolated vertices until there are \(N\) vertices. This preserves \(M(G)\).
Construct a society with \(m=\tau=N\), setting, for every type \(i\),
\( \mu_i=1/N,\qquad D_i=[0,1],\qquad u_i(x)=0. \)
For every ordered pair, set
\( f_{ij}(x,y)=2xy-x-y. \)
Define the interaction weights by
\( w_{ij}= \begin{cases} N,& i<j\text{ and }\{i,j\}\in E,\\ 0,&\text{otherwise}. \end{cases} \)
Finally, set \(\varepsilon=1/4\).
These are valid inputs. In particular, the masses are positive dyadic rationals and sum to one; the weights are nonnegative integers; and each edge contributes exactly once to the ordered pair sum. All self-interaction weights vanish.
The construction has polynomial encoding length: \(N\leq2n\), there are \(N^2\) ordered pairs, each polynomial has a constant-size dense coefficient array, and each nonzero weight uses \(O(\log n)\) bits.
Take any feasible family of Borel probability measures \(\pi_i\). Define its means by
\( p_i=\int_{[0,1]}x\,d\pi_i(x)\in[0,1]. \)
For an interacting pair, integration against the product measure gives
\( \iint(2xy-x-y)\,d\pi_i(x)\,d\pi_j(y) =2p_ip_j-p_i-p_j. \)
Since \(\mu_iw_{ij}=1\) on each selected edge, the objective is therefore
\( J(\pi) =-\sum_{\{i,j\}\in E}(p_i+p_j-2p_ip_j). \)
To interpret this sum, let \(B_1,\ldots,B_N\) be independent Bernoulli random variables with \(\Pr(B_i=1)=p_i\). Each realization defines a cut. For every edge,
\( \Pr(B_i\neq B_j) =p_i(1-p_j)+(1-p_i)p_j =p_i+p_j-2p_ip_j. \)
Consequently,
\( -J(\pi) =\mathbb E[\text{number of edges crossing the random cut}] \leq M(G). \)
The inequality holds because every realized cut has at most \(M(G)\) crossing edges. Thus every feasible family satisfies \(J(\pi)\geq-M(G)\).
Conversely, choose a maximum cut and let \(b_i\in\{0,1\}\) encode its sides. The feasible measures \(\pi_i=\delta_{b_i}\) give \(J(\pi)=-M(G)\). These measures already have rational action supports and rational probabilities. Hence the exact optimum is
\( J^*=-M(G). \)
This proves the equality for the full feasible set of measures in the constructed instance, not merely for measures supported at the endpoints.
Suppose an algorithm produces the required finite rational measures in polynomial time. Applied to the constructed instance, its output satisfies
\( -M(G)\leq J(\pi)\leq-M(G)+1/4. \)
Equivalently,
\( M(G)-1/4\leq-J(\pi)\leq M(G). \)
Because \(M(G)\) is an integer, it follows that
\( M(G)=\lceil-J(\pi)\rceil. \)
This value can be computed in polynomial time from the output. Explicitly, if
\( \pi_i=\sum_{r=1}^{k_i}q_{ir}\delta_{x_{ir}}, \)
then \(p_i=\sum_r q_{ir}x_{ir}\), and the formula above evaluates \(J(\pi)\) using rational arithmetic. A polynomial-time algorithm has polynomial output length; the rational sums and products used here also have polynomial bit length. Thus exact evaluation and taking the ceiling require polynomial time.
Comparing the recovered \(M(G)\) with \(K\) decides Simple Max Cut. This establishes the claimed \(\mathrm{NP}\)-hardness.
The hardness also persists if all weights are restricted to \(\{0,1\}\), provided the tolerance remains part of the input. Replace each nonzero weight \(N\) by \(1\) and set \(\varepsilon=1/(4N)\). The resulting objective is the preceding objective divided by \(N\), so its optimum is \(-M(G)/N\), and an approximate output again yields
\( M(G)=\lceil-NJ(\pi)\rceil. \)
This tolerance is dyadic and has \(O(\log n)\) encoding length.
The cited PFD paper proves monotonic improvement of its incumbent in Proposition 1. That statement supplies no polynomial bound on the time needed to achieve a prescribed global additive error, so it is compatible with the hardness proved here. [PFD paper](https://cdn.aaai.org/ojs/6198/6198-13-9423-1-10-20200516.pdf)
⟨structured verdict parsed — rendered above⟩
The proof resolves USER_TASK correctly. It establishes NP-hardness of producing the required additive approximation, even under the stated restrictions. No major or minor mathematical issues were found.
The prover precisely states the decision version of Simple Max Cut: given a simple unweighted undirected graph and an integer threshold, decide whether a cut reaches that threshold. The cited paper establishes NP-completeness of this problem. Its hypotheses match the graphs used in the reduction. [Garey, Johnson, and Stockmeyer](https://www.sciencedirect.com/science/article/pii/0304397576900591)
The padding and input construction are valid:
The encoding-length claim is correct. The construction writes \(N^2\) constant-size polynomial arrays and weights with at most \(O(\log n)\) bits each. Hence both construction time and output input length are polynomial in the explicitly represented graph size.
For every feasible Borel probability measure on \([0,1]\), the mean \(p_i\) exists and lies in \([0,1]\). All relevant integrands are bounded, so the product-measure integration and factorization used in the proof are justified.
The calculation
\( \iint(2xy-x-y)\,d\pi_i(x)\,d\pi_j(y)=2p_ip_j-p_i-p_j \)
is correct. Combining this with the edge coefficients gives exactly
\( J(\pi)=-\sum_{\{i,j\}\in E}(p_i+p_j-2p_ip_j) \).
This establishes the formula for all feasible measures, including measures with infinite or irrational supports. The proof does not silently restrict the optimization domain.
The auxiliary independent Bernoulli variables are well defined for every \(p_i\in[0,1]\), including the endpoints. Their edge-disagreement probability is correctly computed as
\(p_i(1-p_j)+(1-p_i)p_j=p_i+p_j-2p_ip_j\).
Consequently, \(-J(\pi)\) is the expected size of a cut. Every realization has at most \(M(G)\) crossing edges, so the claimed inequality \(J(\pi)\geq-M(G)\) holds for every feasible family.
The converse also holds: the Dirac measures associated with a maximum cut are feasible and attain \(-M(G)\). Their supports and probabilities are rational. Thus \(J^*=-M(G)\), and attainment of the minimum is explicitly established for the constructed instances.
The approximation guarantee and the preceding lower bound together imply
\(M(G)-1/4\leq-J(\pi)\leq M(G)\).
Since \(M(G)\) is an integer and the interval lies strictly above \(M(G)-1\), taking the ceiling recovers it exactly. This remains valid when \(M(G)=0\).
The polynomial-time postprocessing claim is also justified. Under the explicit rational output representation required by USER_TASK, a polynomial-time algorithm can write only polynomially many bits. Computing the means and the edge sum uses polynomially many rational additions and multiplications. The sums of the operand bit lengths bound the resulting denominator and numerator lengths polynomially. Exact evaluation and taking the ceiling therefore require polynomial time.
Comparing the recovered value with \(K\) decides the stated NP-complete problem. This establishes the claimed hardness of the approximation task and the implication that a deterministic polynomial-time algorithm with the required guarantee would yield \(\mathrm{P}=\mathrm{NP}\).
Replacing every nonzero weight \(N\) by \(1\) divides the entire objective by \(N\), because all unary terms vanish. With tolerance \(1/(4N)\), multiplying the approximation inequality by \(N\) reproduces the same recovery interval.
The formula \(M(G)=\lceil-NJ(\pi)\rceil\) is therefore correct. Since \(N\) is a power of two, the new tolerance is dyadic and has \(O(\log n)\) encoding length. This extension is valid.
The description of Proposition 1 is accurate: its proof establishes monotonic improvement of the stored best objective through updates made only upon finding a better solution. It supplies no bound on the iterations required to reach a prescribed global additive error. The prover correctly treats this guarantee as compatible with the reduction. [PFD paper, Proposition 1](https://cdn.aaai.org/ojs/6198/6198-13-9423-1-10-20200516.pdf)
No unjustified nontrivial steps, false statements, quantifier errors, missing hypotheses, or blocking gaps were found. No additional clarification or repair 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.