Answer: \(\mathrm{NP}\text{-complete}\)
Theorem 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThe size of a UTIL message produced by an agent is exponential in the number of its separator and its interface descendants.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set \(T\) of complete ADCOP types with rational masses \(\mu_t>0\), \(\sum_{t\in T}\mu_t=1\), finite domains \(D_t\), nonnegative rational interaction intensities \(\rho_{tu}\), asymmetric rational costs \(c_{t\leftarrow u}(a,b)\), and a rational threshold \(B\), decide whether \(\min_q F(q)\le B\), where \(q_{ta}\ge0\), \(\sum_{a\in D_t}q_{ta}=1\), and \(F(q)=\sum_{t,u\in T}\mu_t\mu_u\rho_{tu}\sum_{a\in D_t,\,b\in D_u}q_{ta}q_{ub}c_{t\leftarrow u}(a,b)\).
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), satisfying \(\sum_t\mu_t=1\). Here \(\tau=|T|\) is the support size, not the number of possible types.
Each type controls one decision with an explicitly listed nonempty finite domain \(D_t\). The input supplies nonnegative binary rational intensities \(\rho_{tu}\), explicit cost tables \(c_{t\leftarrow u}:D_t\times D_u\to\mathbb Q_{\ge0}\), and a threshold \(B\in\mathbb Q\). Neither intensities nor costs must be symmetric.
A feasible allocation has real fractions \(q_{ta}\ge0\) with \(\sum_{a\in D_t}q_{ta}=1\); the mass assigned action \(a\) is \(\mu_tq_{ta}\). Interacting actions are independently drawn from these fractions, including between distinct individuals of the same type.
Define \(F(q)=\sum_{t,u\in T}\mu_t\mu_u\rho_{tu}\sum_{a\in D_t,\,b\in D_u}q_{ta}q_{ub}c_{t\leftarrow u}(a,b)\). The ordered sum includes \(t=u\) and aggregates both directed costs without a factor of one half. All input tables are available to the algorithm.
Let \(m=\max_t|D_t|\) and let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is deciding whether \(\min_q F(q)\le B\) solvable in polynomial time, or is it NP-hard?
For finite ADCOPs, AsymDPOP has utility-message size exponential in the counts of separator ancestors (ancestors adjacent to the current subtree) and interface descendants (descendants adjacent to those ancestors). [AsymDPOP](https://www.ijcai.org/proceedings/2019/0032.pdf)
Discrete ADCOP optimization is NP-hard. [Scheduling operations in a large hospital by multiple agents](https://tzin.bgu.ac.il/~zivanr/files/operationsEAAI.pdf) No classification of exactly the mass-allocation problem above was located in the literature search.
The decision problem is \(\mathrm{NP}\)-complete, under polynomial-time many-one reductions. Thus it has a polynomial-time algorithm exactly if \(\mathrm{P}=\mathrm{NP}\).
Hardness holds even under either of these restrictions:
Below, all running times are bit-complexity bounds.
Call an allocation pure if each type assigns fraction \(1\) to one action. For a pure action vector \(a=(a_t)_{t\in T}\), write its cost as \(F(a)\).
Lemma. If \(\rho_{tt}=0\) for every \(t\), then
\(\displaystyle \min_q F(q)=\min_{a\in\prod_{t\in T}D_t}F(a).\)
Proof. Given a feasible allocation \(q\), draw one random action \(A_t\) for each type, independently across types, with probability \(\Pr(A_t=a)=q_{ta}\). For distinct types \(t,u\), independence gives
\(\displaystyle \mathbb E[c_{t\leftarrow u}(A_t,A_u)]=\sum_{a\in D_t,\ b\in D_u}q_{ta}q_{ub}c_{t\leftarrow u}(a,b).\)
Because all self-interaction terms vanish, summing this identity yields \(\mathbb E[F(A)]=F(q)\). An average of pure-allocation costs is at least their minimum. Consequently, every feasible \(q\) satisfies \(F(q)\ge\min_a F(a)\). Pure allocations are themselves feasible, proving equality. \(\square\)
The hypothesis matters: with self-interactions, the model draws two actions independently from the same type, whereas a pure action vector supplies only one action for that type.
We reduce from weighted MAX-CUT: given a simple undirected graph \(G=(V,E)\), positive binary integer edge weights \(w_e\), and an integer threshold \(K\), decide whether some cut has weight at least \(K\). This problem is \(\mathrm{NP}\)-complete; weighted MAX-CUT and CLIQUE are among the problems treated in [Karp’s original paper](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
Let \(n=|V|\), taking the nonempty-graph restriction, which retains hardness. Construct the society as follows:
All masses are positive and sum to \(1\); intensities and costs are nonnegative. Each undirected edge contributes through exactly one ordered pair, so there is no factor-of-two ambiguity.
For a pure allocation \(a\), let \(\operatorname{cut}_w(a)\) denote the weight of edges whose endpoint actions differ. Then
\(\displaystyle F(a)=\frac{1}{n^2}\sum_{\{i,j\}\in E}w_{\{i,j\}}\mathbf 1_{\{a_i=a_j\}}=\frac{W-\operatorname{cut}_w(a)}{n^2}.\)
The lemma therefore gives
\(\displaystyle \min_qF(q)=\frac{W-\operatorname{MaxCut}_w(G)}{n^2}.\)
Consequently,
\(\displaystyle \min_qF(q)\le B\quad\Longleftrightarrow\quad\operatorname{MaxCut}_w(G)\ge K.\)
The construction writes only quadratically many constant-size cost tables. The masses, intensities, and threshold have polynomial encoding length, so this is a polynomial-time reduction. It proves \(\mathrm{NP}\)-hardness even when \(m=2\) and every self-interaction vanishes.
This second reduction shows that fixing the support size \(\tau\) does not make the unrestricted problem polynomial-time solvable.
Given a nonempty simple graph \(G=(V,E)\), take one type \(t\), with \(\mu_t=\rho_{tt}=1\), and domain \(D_t=V\). Define
\(\displaystyle c_{t\leftarrow t}(v,w)=\begin{cases}0,&\{v,w\}\in E,\\1,&\text{otherwise}.\end{cases}\)
In particular, every diagonal entry is \(1\). For a probability vector \(q\) on \(V\), the ordered-sum convention gives
\(\displaystyle F(q)=1-2H(q),\qquad H(q)=\sum_{\{v,w\}\in E}q_vq_w.\)
Let \(\omega(G)\) be the maximum clique size. We prove directly that
\(\displaystyle \min_qF(q)=\frac1{\omega(G)}.\)
The simplex is compact and \(H\) is continuous, so a maximizer exists. Choose a maximizer with the smallest possible number of positive coordinates.
Suppose two positive coordinates \(q_i,q_j\) correspond to nonadjacent vertices. Holding every other coordinate fixed, define
\(\displaystyle A_i=\sum_{v:\{i,v\}\in E}q_v,\qquad A_j=\sum_{v:\{j,v\}\in E}q_v.\)
Neither sum depends on \(q_i\) or \(q_j\), because the graph has no loops and \(i,j\) are nonadjacent. The terms involving these coordinates are exactly \(q_iA_i+q_jA_j\).
If \(A_i\ge A_j\), replace \((q_i,q_j)\) by \((q_i+q_j,0)\). This changes \(H\) by \(q_j(A_i-A_j)\ge0\). If \(A_j>A_i\), merge both coordinates into \(j\) instead. In either case the resulting vector must remain a maximizer, because the original value was globally maximal, but its positive support is smaller. This is a contradiction.
Thus the chosen maximizer is supported on a clique of size \(r\le\omega(G)\). On that support,
\(\displaystyle H(q)=\frac12\left(1-\sum_vq_v^2\right).\)
Cauchy–Schwarz gives \(\sum_vq_v^2\ge1/r\), hence
\(\displaystyle H(q)\le\frac12\left(1-\frac1r\right)\le\frac12\left(1-\frac1{\omega(G)}\right).\)
The uniform distribution on a maximum clique attains the last bound. The asserted formula for \(\min_qF(q)\) follows.
For a CLIQUE instance with threshold \(1\le k\le|V|\), set \(B=1/k\). Then
\(\displaystyle \min_qF(q)\le B\quad\Longleftrightarrow\quad\omega(G)\ge k.\)
The construction has polynomial size. Hence the problem remains \(\mathrm{NP}\)-hard when \(\tau=1\), even with symmetric costs in \(\{0,1\}\).
Real-valued feasibility does not by itself establish membership in \(\mathrm{NP}\). We now prove the needed certificate bound.
Let \(N=\sum_t|D_t|\le m\tau\), and index coordinates by pairs \(i=(t,a)\). Define the rational matrix
\(\displaystyle Q_{(t,a),(u,b)}=\mu_t\mu_u\rho_{tu}c_{t\leftarrow u}(a,b),\qquad M=\frac{Q+Q^{\mathsf T}}2.\)
Then \(M\) is symmetric and \(F(q)=q^{\mathsf T}Mq\). This symmetrization preserves the given ordered sum exactly.
The feasible product of simplexes is nonempty and compact, so let \(q^*\) be a global minimizer. Define its positive support in each type by \(S_t=\{a:q^*_{ta}>0\}\).
For any \(a,b\in S_t\), sufficiently small transfers of mass between these coordinates are feasible in either direction. Differentiating along that direction at a minimum gives
\(\displaystyle (Mq^*)_{ta}=(Mq^*)_{tb}.\)
Choose one reference action \(a_t\in S_t\) for each type. Consider the following rational linear system with nonnegativity constraints:
\(\displaystyle z_{ta}=0\ \text{for }a\notin S_t,\qquad z_{ta}\ge0,\qquad \sum_{a\in S_t}z_{ta}=1,\)
\(\displaystyle (Mz)_{ta}=(Mz)_{t a_t}\quad\text{for every }a\in S_t.\)
Its feasible set is nonempty because it contains \(q^*\).
Every feasible point of this system has the same objective value. To see this, let \(x,y\) be feasible and put \(h=x-y\). For every type, \(\sum_a h_{ta}=0\); moreover, \(h\) vanishes outside the selected supports. Both \(Mx\) and \(My\) are constant within each selected type support. Symmetry of \(M\) therefore gives
\(\displaystyle F(x)-F(y)=h^{\mathsf T}M(x+y)=0.\)
In particular, every feasible point has value \(F(q^*)\).
It remains to bound the encoding length of a rational feasible point. After deleting coordinates outside the selected supports, write the equalities as \(Cz=b\), with \(z\ge0\). Choose a feasible point \(z\) having the fewest positive coordinates.
The columns of \(C\) indexed by those positive coordinates are linearly independent. Otherwise, there would be a nonzero vector \(h\) supported on them with \(Ch=0\). The type-sum equations imply that \(h\) has both positive and negative entries. Moving from \(z\) in direction \(h\) until the first positive coordinate becomes zero preserves feasibility and reduces the positive support, a contradiction.
Let the positive support have size \(r\). Select \(r\) rows forming an invertible square submatrix on these columns. Cramer’s rule expresses every positive coordinate of \(z\) as a ratio of determinants of rational matrices.
Here the entries of \(C\) have \(O(L)\) bits: each coefficient involves only a fixed number of products, sums, and differences of input rationals. Clearing denominators separately in each row produces integer entries with \(O(NL)\) bits. For an \(r\)-by-\(r\) integer matrix whose entries have at most \(R\) bits, the determinant has \(O(rR+r\log r)\) bits, since its absolute value is at most \(r!2^{rR}\).
Thus all coordinates of \(z\), and their total encoding, have polynomial length in \(L\), using \(N\le L\) up to the encoding convention. We have proved that a polynomial-length rational global minimizer exists.
A certificate consists simply of that rational allocation. Exact arithmetic verifies nonnegativity, type sums, and \(F(z)\le B\) in \(\operatorname{poly}(m,\tau,L)\) time. Therefore the decision problem belongs to \(\mathrm{NP}\). Together with Section 2, this proves \(\mathrm{NP}\)-completeness.
When all self-interactions vanish, Section 1 gives an exact algorithm by enumerating pure allocations. Its running time is
\(\displaystyle m^\tau\,\operatorname{poly}(m,\tau,L).\)
For the general problem, enumerate every tuple of nonempty supports \(S_t\subseteq D_t\). For each tuple, solve the rational linear feasibility problem from Section 4 and evaluate any feasible point. Rational linear-programming feasibility and witness construction take polynomial time in the system’s binary encoding length.
Every candidate is a feasible allocation, so its cost is at least the global minimum. The support tuple of a global minimizer produces a candidate with exactly the global minimum, by the constant-value argument above. Taking the least candidate value is therefore exact.
There are \(\prod_t(2^{|D_t|}-1)\) support tuples, giving the bound
\(\displaystyle \left(\prod_t(2^{|D_t|}-1)\right)\operatorname{poly}(m,\tau,L)\le2^{m\tau}\operatorname{poly}(m,\tau,L).\)
For \(m=1\), the allocation is unique and direct evaluation takes polynomial time. For fixed \(m\) and fixed \(\tau\), the general algorithm is polynomial in \(L\). Fixing either parameter alone does not suffice, by Sections 2 and 3.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The general decision problem is \(\mathrm{NP}\)-complete, and both restricted hardness claims are established. The rational-certificate argument and the exact exponential-time algorithms are sound.
I found no major or minor mathematical issues. No additional clarification is needed.
The lemma is correct under its stated hypothesis \(\rho_{tt}=0\) for every type.
The random action vector selects actions independently across distinct types. Thus, for every surviving interaction term, the expected cost is exactly the corresponding bilinear expression in the allocation fractions. Linearity of expectation then gives \(\mathbb E[F(A)]=F(q)\).
The distribution of \(A\) is supported on finitely many pure allocations, so its expected cost is at least the minimum pure cost. Conversely, pure allocations satisfy the continuous feasibility constraints. These two inequalities establish the asserted equality of minima.
The discussion of self-interactions is accurate: selecting one action per type does not reproduce two independent draws from that type’s fractions. The lemma is not used outside its hypotheses.
The source problem is correctly specified as a decision problem with binary integer weights. Weighted MAX-CUT and CLIQUE are standard complete problems treated in [Karp’s original paper](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
All constructed data satisfy the task’s requirements:
The use of just one ordered orientation for each edge is permitted because the task does not require symmetric intensities. Consequently, each edge contributes exactly once, with coefficient \(w_e/n^2\).
For pure allocations, the calculation
\[
F(a)=\frac{W-\operatorname{cut}_w(a)}{n^2}
\]
is correct. Section 1 applies directly, so the same optimum identity holds for fractional allocations. Substitution of the constructed threshold gives the required equivalence with the MAX-CUT decision question.
There is no threshold-domain issue when \(K>W\): the resulting negative \(B\) is permitted by the task, and the decision equivalence still holds.
The construction has polynomial binary size. There are quadratically many tables of constant dimension; encoding the weights, masses, and threshold requires polynomially many bits. This establishes hardness with \(m=2\), equal masses, and no self-interactions.
The construction respects the same-type independent-draw convention exactly.
The graph is simple, so diagonal costs equal \(1\). Every undirected edge contributes two ordered zero-cost entries. Since the probability vector sums to \(1\), the identity
\[
F(q)=1-2H(q)
\]
has the correct normalization.
The proof of the clique formula is complete:
Thus \(\min_q F(q)=1/\omega(G)\) is established as written. For \(1\le k\le |V|\), the threshold comparison is equivalent to \(\omega(G)\ge k\).
The nonempty edgeless case is also covered: its maximum clique size is \(1\), and the formula gives minimum cost \(1\). The restriction on the CLIQUE threshold removes only trivial instances and retains hardness.
The explicitly supplied symmetric table has quadratic size. This establishes hardness with \(\tau=1\) and costs in \(\{0,1\}\).
This section correctly addresses the additional burden imposed by real allocation variables.
Quadratic representation. The matrix \(Q\) includes the masses, intensities, and directed costs exactly once. Symmetrization preserves the scalar quadratic form, so \(F(q)=q^{\mathsf T}Mq\) matches the ordered objective.
Support stationarity. Each selected support \(S_t\) is nonempty because the type’s fractions sum to \(1\). Transfers between two positive coordinates are feasible in both directions for sufficiently small magnitude. At a minimum, their directional derivative vanishes. Since \(M\) is symmetric, this gives precisely the stated equality of the corresponding entries of \(Mq^*\).
Linear-system feasibility. The global minimizer satisfies every constraint in the constructed system, so that system is nonempty.
Constancy of the objective. For feasible \(x,y\), the difference \(h=x-y\) vanishes outside the selected supports and has coordinate sum zero within each type. Both \(Mx\) and \(My\) are constant on each selected type support. Therefore the displayed expression \(h^{\mathsf T}M(x+y)\) is zero, and symmetry identifies it with \(F(x)-F(y)\).
This reasoning remains valid when a feasible point has zeros inside a selected support. Strict positivity is not required here. Every feasible point therefore attains the global minimum represented by \(q^*\).
Rational witness and encoding bound. The minimum-positive-support argument is valid. A dependence among the corresponding columns would yield a nonzero feasible direction. The type-sum equations force that direction to have both signs, so moving until a positive coordinate first reaches zero preserves feasibility and reduces support.
Independent columns admit the stated invertible square row selection. Cramer’s rule then gives rational coordinates. The coefficient-length, denominator-clearing, and determinant bounds are correct. Explicit input listing ensures that \(N\) is bounded by the input length, so the total certificate length is polynomial.
Finally, exact rational arithmetic can verify the allocation constraints and threshold inequality in polynomial time. A verifier need not verify global optimality; it only needs a feasible allocation with cost at most \(B\). The proved existence of a short rational global minimizer supplies such a certificate for every yes-instance.
Membership in \(\mathrm{NP}\) is established.
Both algorithms are correct.
Without self-interactions, enumerating pure allocations examines at most \(m^\tau\) candidates. Each objective evaluation takes polynomial bit time, giving the stated bound.
For the general problem, the support enumeration considers exactly
\[
\prod_t(2^{|D_t|}-1)
\]
tuples. Each associated system has polynomial dimension and coefficient length. The invoked rational linear-programming result—polynomial-time feasibility testing and rational witness construction—applies to these explicitly encoded rational linear constraints.
Every returned candidate is a feasible allocation. The support tuple of a global minimizer yields a candidate with the same global minimum by Section 4. Taking the least candidate value therefore gives the exact optimum.
The upper bound \(2^{m\tau}\operatorname{poly}(m,\tau,L)\) follows from the support count. The unique-allocation case \(m=1\) and polynomial running time when both parameters are fixed are correctly identified.
The parameter-hardness statements are also consistent: hardness persists at \(m=2\) when \(\tau\) varies, and at \(\tau=1\) when \(m\) varies. As usual, these exclude polynomial-time algorithms for those restricted classes unless \(\mathrm P=\mathrm{NP}\).
None. The proof establishes the claimed classification, and its running-time statements address the requested parameters.
⟨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.