Answer: \(\mathrm{NP}\text{-complete}\)
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateBnB-ADOPT terminates with the minimal solution cost γr Xr.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), finite domains \(D_t\), symmetric nonnegative rational interaction weights \(w_{tu}\), and symmetric nonnegative rational pair-cost tables \(c_{tu}(d,e)\), choose fractions \(x_{td}\ge 0\) with \(\sum_{d\in D_t}x_{td}=1\) to minimize \(\Phi(x)=\frac{1}{2}\sum_{t,u\in T}\mu_t\mu_u w_{tu}\sum_{d\in D_t,e\in D_u}x_{td}x_{ue}c_{tu}(d,e)\). Return the minimum and a minimizing table, where each unit of population still receives one integral value; equivalently, for rational \(K\), decide whether some feasible table has \(\Phi(x)\le K\).
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) counts supported types, not all possible types.
Each type has an explicitly listed nonempty finite domain \(D_t\). Input includes finite nonnegative binary-rational weights \(w_{tu}=w_{ut}\), tables \(c_{tu}(d,e)=c_{ut}(e,d)\geq 0\), and a binary-rational threshold \(K\).
A feasible allocation has real fractions \(x_{td}\geq 0\) with \(\sum_{d\in D_t}x_{td}=1\): mass \(\mu_tx_{td}\) receives the single domain value \(d\), shared across all its interactions.
Its cost is \(\Phi(x)=\frac12\sum_{t,u\in T}\mu_t\mu_uw_{tu}\sum_{d\in D_t,e\in D_u}x_{td}x_{ue}c_{tu}(d,e)\). Terms with \(t=u\) represent interactions between distinct individuals of the same type and are permitted.
Decide whether a feasible allocation satisfies \(\Phi(x)\leq K\). Let \(m=\max_t|D_t|\) and \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is this continuous allocation decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For finite agents choosing one domain value each and minimizing the sum of binary constraint costs, BnB-ADOPT terminates with the exact minimum; this is a correctness guarantee, without a polynomial-time bound, and discrete DCOP optimization is reported as \(\mathrm{NP}\)-hard. [Yeoh, Felner and Koenig](https://tzin.bgu.ac.il/~felner/2010/DFBnB.pdf)
General rational quadratic feasibility over a rational polyhedron is known to belong to \(\mathrm{NP}\); no classification of the precise mass-allocation problem above was verified. [Del Pia, Dey and Molinaro](https://arxiv.org/abs/1407.4798)
The decision problem is \(\mathrm{NP}\)-complete. In particular, it is \(\mathrm{NP}\)-hard even when \(\tau=1\). It is also \(\mathrm{NP}\)-hard when \(m=2\) and all same-type interaction weights vanish.
An exact deterministic algorithm runs in
\[
\]
\(\displaystyle O\!\left((2^m-1)^\tau\operatorname{poly}(L)\right).\)
The proofs below account for real fractional allocations and binary encoding lengths.
We reduce from CLIQUE: given a nonempty finite simple graph \(G=(V,E)\) and an integer \(k\) with \(1\leq k\leq |V|\), decide whether \(G\) contains a clique of size at least \(k\). This restricted problem is \(\mathrm{NP}\)-complete; the omitted cases are immediately decidable. See [Karp’s original paper](https://doi.org/10.1007/978-1-4684-2001-2_9).
Construct an allocation instance with one type \(t\), setting
\(\displaystyle \mu_t=1,\qquad D_t=V,\qquad w_{tt}=k,\qquad K=\frac12.\)
Its symmetric cost table \(C=c_{tt}\) is defined by:
All input numbers are integers or dyadic rationals. The explicitly listed table has polynomial size.
Write \(\omega(G)\) for the largest clique size. We prove
\(\displaystyle \min_{\substack{x\geq 0\\ \sum_{v\in V}x_v=1}}x^\top Cx=\frac1{\omega(G)}.\)
The simplex is compact, so the continuous function \(F(x)=x^\top Cx\) attains its minimum. Choose a minimizer having the smallest possible number of positive coordinates.
Suppose two vertices \(a,b\) in its support are nonadjacent. Set \(s=x_a+x_b>0\), keep all other coordinates fixed, and replace \(x_a,x_b\) by \(r,s-r\), where \(0\leq r\leq s\).
Because \(C_{aa}=C_{bb}=C_{ab}=1\), the terms involving only these coordinates sum to
\(\displaystyle r^2+(s-r)^2+2r(s-r)=s^2.\)
Define
\(\displaystyle A=\sum_{v\notin\{a,b\}}C_{av}x_v,\qquad B=\sum_{v\notin\{a,b\}}C_{bv}x_v.\)
For a constant \(C_0\) containing the terms involving neither coordinate, the resulting objective is
\(\displaystyle F(x(r))=C_0+s^2+2rA+2(s-r)B.\)
This is affine in \(r\). Consequently, one endpoint has objective no greater than the original point. Since the original point is a global minimizer, that endpoint is also a global minimizer. It has smaller support, a contradiction.
Thus the chosen minimizer is supported on a clique.
If that clique support has size \(r\), all its off-diagonal costs vanish. Hence, by Cauchy–Schwarz,
\(\displaystyle F(x)=\sum_{v\in\operatorname{supp}(x)}x_v^2\geq\frac{\left(\sum_vx_v\right)^2}{r}=\frac1r\geq\frac1{\omega(G)}.\)
Conversely, the uniform distribution on a largest clique has objective \(1/\omega(G)\). This proves the claimed identity.
The constructed allocation instance therefore satisfies
\(\displaystyle \min_x\Phi(x)=\frac{k}{2\omega(G)}.\)
It follows that
\(\displaystyle \exists x:\Phi(x)\leq K\quad\Longleftrightarrow\quad\frac{k}{2\omega(G)}\leq\frac12\quad\Longleftrightarrow\quad\omega(G)\geq k.\)
This is a polynomial-time reduction proving hardness with \(\tau=1\). It uses precisely the same-type interactions permitted in the question.
First we establish why fractions do not improve the optimum when \(w_{tt}=0\) for every type.
A pure allocation chooses one value \(d_t\in D_t\) for each type and assigns that value to its entire mass.
Given any fractional allocation \(x\), independently choose a random value \(Y_t\) for each type with
\(\displaystyle \Pr(Y_t=d)=x_{td}.\)
For distinct types, independence gives
\(\displaystyle \mathbb E[c_{tu}(Y_t,Y_u)]=\sum_{d\in D_t,e\in D_u}x_{td}x_{ue}c_{tu}(d,e).\)
Because all same-type terms vanish, the expected cost of this random pure allocation equals \(\Phi(x)\). At least one outcome has cost at most its expectation. Conversely, every pure allocation is feasible. Therefore
\(\displaystyle \min_{\text{fractional }x}\Phi(x)=\min_{\text{pure }x}\Phi(x).\)
The decision problem asking whether a graph has a cut containing at least \(B\) edges is \(\mathrm{NP}\)-complete; this precise version is also stated in the proof of Corollary 2 of [Del Pia, Dey and Molinaro](https://arxiv.org/pdf/1407.4798).
Given \(G=(V,E)\), pad it with isolated vertices until its number \(N\) of vertices is a power of two. This adds fewer than \(|V|\) vertices.
Create one supported type per padded vertex, with
\(\displaystyle \tau=N,\qquad D_t=\{0,1\},\qquad \mu_t=\frac1N.\)
For every original edge \(\{t,u\}\), set \(w_{tu}=N^2\); set all other weights, including \(w_{tt}\), to zero. For distinct types, set \(c_{tu}(d,e)=1\) if \(d=e\), and zero otherwise. Set all same-type tables to zero and choose
\(\displaystyle K=|E|-B.\)
Symmetry and the factor \(1/2\) in the objective yield
\(\displaystyle \Phi(x)=\sum_{\{t,u\}\in E}\left(x_{t0}x_{u0}+x_{t1}x_{u1}\right).\)
For a pure allocation this counts exactly the uncut edges. By the pure-allocation lemma,
\(\displaystyle \min_x\Phi(x)=|E|-\operatorname{MaxCut}(G).\)
Thus the allocation instance is a yes-instance exactly when \(G\) has a cut of size at least \(B\).
Every supported mass is positive and dyadic. The construction lists \(O(N^2)\) constant-size tables and weights having \(O(\log N)\) bits, so its output length and construction time are polynomial in the source input length. This proves hardness with \(m=2\) and no same-type interactions.
Let
\(\displaystyle n=\sum_{t\in T}|D_t|\leq m\tau.\)
Index coordinates by pairs \((t,d)\), and define the rational symmetric matrix
\(\displaystyle Q_{(t,d),(u,e)}=\mu_t\mu_uw_{tu}c_{tu}(d,e).\)
Then \(\Phi(x)=\tfrac12x^\top Qx\). The feasible region is a nonempty compact product of simplices, so a global minimizer exists.
We now prove that an optimum can be recovered by enumerating supports and solving rational linear feasibility problems.
Choose nonempty subsets \(S_t\subseteq D_t\), and let \(Q_S\) be the principal submatrix on their coordinates. Choose a reference value \(r_t\in S_t\) for each type.
Define \(R_S\) by the following linear constraints:
\(\displaystyle z_{td}\geq0,\qquad \sum_{d\in S_t}z_{td}=1\quad(t\in T),\)
\(\displaystyle (Q_Sz)_{td}=(Q_Sz)_{t r_t}\quad(t\in T,\ d\in S_t\setminus\{r_t\}).\)
Every point of \(R_S\), extended by zero outside the selected subsets, is a feasible allocation.
Let \(x^*\) be a global minimizer, and choose its actual supports
\(\displaystyle S_t=\{d\in D_t:x^*_{td}>0\}.\)
For any \(d,r_t\in S_t\), sufficiently small transfers of mass in either direction between those two coordinates remain feasible. The derivative of the objective in that direction must therefore vanish. Since its gradient on the selected coordinates is \(Q_Sx^*\), these derivatives give exactly the displayed stationarity equations. Consequently, \(x^*\in R_S\).
Take \(z,y\in R_S\) and put \(\delta=y-z\). For each type,
\(\displaystyle \sum_{d\in S_t}\delta_{td}=0.\)
The stationarity equations make \(Q_Sz\) and \(Q_Sy\) constant within each type’s coordinates. Therefore
\(\displaystyle \delta^\top Q_Sz=\delta^\top Q_Sy=0.\)
Using symmetry,
\(\displaystyle \frac12y^\top Q_Sy-\frac12z^\top Q_Sz=\frac12(y-z)^\top Q_S(y+z)=0.\)
Thus any point of a nonempty \(R_S\) gives its unique objective value. In particular, any point of the set associated with an optimal support is itself globally optimal.
Each \(R_S\) is a bounded rational polyhedron: nonnegativity and the normalization equations bound every coordinate between zero and one. If nonempty, it has a vertex.
Its linear description has size polynomial in \(L\). To justify polynomial-size vertex coordinates, select a full-rank collection of active constraints determining a vertex. Such a collection exists: otherwise a nonzero direction preserving the active constraints would permit small feasible perturbations in both directions, contradicting extremality.
Clear denominators in those equations and apply Cramer’s rule. The integer coefficients have polynomial bit length; determinant bounds then give polynomial bit length for every vertex coordinate.
Applying this to an optimal support proves that every instance has a rational global minimizer of encoding length polynomial in \(L\). A certificate for a yes-instance consists of its rational coordinates. Nonnegativity, normalization, and \(\Phi(x)\leq K\) can all be checked by exact rational arithmetic in polynomial time. Hence the problem belongs to \(\mathrm{NP}\).
This also verifies the hypotheses of the general quadratic-feasibility result: the objective and threshold are rational, and the feasible region is a rational polyhedron. The continuous result appears as Theorem 3 in [Del Pia, Dey and Molinaro](https://arxiv.org/pdf/1407.4798).
Enumerate every choice of nonempty \(S_t\subseteq D_t\). For each choice, use polynomial-time rational linear programming to test whether \(R_S\) is nonempty and obtain a rational feasible point when it is. Evaluate its objective and compare with \(K\).
Every evaluated point is feasible, and the enumeration includes an optimal support. Thus this algorithm decides the problem exactly.
The number of choices is
\(\displaystyle \prod_{t\in T}(2^{|D_t|}-1)\leq(2^m-1)^\tau.\)
The total running time is therefore
\(\displaystyle O\!\left((2^m-1)^\tau\operatorname{poly}(L)\right)\subseteq O\!\left(2^{m\tau}\operatorname{poly}(L)\right).\)
When all same-type weights vanish, the pure-allocation lemma instead permits enumeration in
\(\displaystyle O\!\left(m^\tau\operatorname{poly}(L)\right).\)
For \(m=1\), the allocation is uniquely determined and the decision takes polynomial time in \(L\). For fixed \(m\) and \(\tau\), the support-enumeration algorithm is polynomial in \(L\). Fixing only \(\tau\) does not suffice: hardness already holds for \(\tau=1\). Fixing only \(m\) does not suffice either: hardness holds for \(m=2\).
The stated termination and optimality guarantee for BnB-ADOPT concerns exact discrete optimization; it does not supply a polynomial running-time bound. [Yeoh, Felner and Koenig](https://tzin.bgu.ac.il/~felner/2010/DFBnB.pdf). The reductions above directly establish hardness for the continuous allocation model, and the certificate argument establishes membership in \(\mathrm{NP}\).
Together they prove \(\mathrm{NP}\)-completeness. A polynomial-time algorithm for the general problem exists if and only if \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The output establishes the intended continuous problem’s \(\mathrm{NP}\)-completeness. Both hardness arguments and the support-enumeration algorithm are sound in substance. There is one minor omission: the MAX-CUT reduction must explicitly exclude empty source graphs or handle them separately. No major issue prevents the main classification.
The constructed instance satisfies the task’s requirements. The support contains exactly one type, its mass is positive and sums to one, its domain is nonempty, and the weight and cost table are symmetric and nonnegative. The threshold and all constructed numerical data have valid binary encodings. Listing the table takes polynomial space and time.
Existence and choice of minimizer are justified. The simplex is nonempty and compact, and the objective is continuous. Among its minimizers, choosing one with minimum support size is valid because support sizes belong to a finite set of positive integers.
The support-elimination calculation is correct. For nonadjacent supported vertices, the three relevant table entries equal one. Thus their internal contribution remains constant during the transfer. The remaining contribution is affine in the transferred coordinate. An endpoint has no greater objective, remains feasible, and eliminates a positive coordinate. Global minimality then makes that endpoint another minimizer, contradicting the chosen minimum support size.
The minimum-value identity follows as written. On a clique support, only diagonal terms remain. Cauchy–Schwarz supplies the stated lower bound, and the uniform distribution on a largest clique attains it. Nonemptiness of the graph ensures that the clique number is positive, so every division is legitimate.
The reduction’s scaling and decision equivalence are correct. Substituting the mass and weight into the objective gives the claimed minimum. Comparison with the threshold is equivalent to the source CLIQUE condition, including equality at the threshold.
This section independently establishes \(\mathrm{NP}\)-hardness for \(\tau=1\).
The pure-allocation lemma is valid under its stated hypothesis. Independent sampling reproduces every distinct-type product in expectation. Vanishing same-type weights remove exactly the terms for which that independence argument would fail. The random allocation has finitely many outcomes, so some outcome has cost at most the expectation. Pure allocations are feasible fractional allocations, giving the reverse optimum inequality.
The lemma respects the requirement that each type’s chosen value is shared across all interactions: each sampled type receives one value, used throughout.
The MAX-CUT construction is valid for nonempty source graphs. Padding preserves the maximum cut, produces positive dyadic masses summing to one, and preserves polynomial output size. The weight cancels the product of masses. Symmetry and the objective’s factor of one half count each original edge exactly once.
The cost interpretation is correct. For a pure allocation, an edge contributes one exactly when its endpoints receive equal values. The pure-allocation lemma therefore gives the stated relationship between minimum allocation cost and maximum cut size.
The cited source explicitly states the required unweighted cut-cardinality decision problem’s \(\mathrm{NP}\)-completeness in the proof of Corollary 2. [Del Pia, Dey and Molinaro](https://arxiv.org/pdf/1407.4798)
Minor issue: empty source graphs. Unlike the CLIQUE section, this section does not require the source graph to be nonempty. If its vertex set is empty, the asserted padding bound and the mass expression \(1/N\) do not apply as written.
Minimum clarification: explicitly restrict the MAX-CUT source problem to nonempty graphs and acknowledge the immediately decidable omitted case, or specify its treatment. This does not undermine the hardness result.
Negative thresholds require no additional restriction: the task permits them, and the reduction’s equivalence remains valid for out-of-range cut thresholds.
The matrix formulation is correct. The task’s symmetries make the defined matrix symmetric, and its quadratic form reproduces the objective with the correct factor.
Stationarity is used only where justified. On the actual support of a global minimizer, both coordinates involved in a within-type transfer are positive. Sufficiently small transfers in either direction therefore remain feasible. Differentiability and local minimality force the displayed derivative equalities. Singleton supports require no transfer equations.
Every point in the selected polyhedron is feasible. Nonnegativity and normalization suffice after extending by zero outside the selected subsets. It is harmless that some selected coordinates may themselves be zero.
The constancy calculation is correct. The difference of two feasible points has zero coordinate sum within each type. The stationarity equations make each relevant matrix-vector product constant within that type. Consequently, both displayed inner products vanish. Symmetry justifies the difference-of-quadratic-values identity.
The proof does not incorrectly treat stationarity as sufficient for global optimality. Instead, it proves that every point in the particular polyhedron containing a global minimizer has the same objective as that minimizer. This is sufficient for the algorithm and certificate argument.
The polyhedron’s boundedness and rationality are established. Its coordinates lie between zero and one, and its constraints have rational coefficients. A nonempty bounded polyhedron has a vertex; full dimensionality is unnecessary.
The active-constraint argument is valid. Failure of full rank would permit sufficiently small feasible perturbations in both directions, contradicting extremality. The argument also applies when normalization or stationarity equations reduce the affine dimension.
The encoding-length conclusion is justified. The explicitly represented input bounds the number of variables and constraints polynomially in \(L\). Forming matrix entries and stationarity coefficients preserves polynomial bit length. Clearing denominators and applying Cramer’s rule and determinant bounds therefore gives polynomial-length vertex coordinates.
The determinant estimate is abbreviated, but it is a routine calculation with the necessary dimension and coefficient bounds already supplied; no additional mathematical argument is needed.
The certificate conclusion follows. A vertex of the polyhedron associated with an optimal support is itself globally optimal by the proved constancy property. Its rational coordinates give a polynomial-length certificate whenever the threshold is attainable. Exact verification of normalization, nonnegativity, and the objective inequality takes polynomial time.
Certificate coordinates need not be dyadic: the feasible allocations permit arbitrary real coordinates, including general rationals.
The supplementary reference is accurate: Theorem 3 states membership in \(\mathrm{NP}\) for continuous rational quadratic feasibility over a rational polyhedron. Its hypotheses are satisfied here. The output also supplies an independent certificate argument. [Del Pia, Dey and Molinaro](https://arxiv.org/pdf/1407.4798)
The enumeration algorithm is exact. Every evaluated point is feasible, preventing false positive answers. The enumeration includes the actual support of a global minimizer, whose polyhedron is nonempty and has constant optimal objective, preventing false negative answers. Exact rational linear programming applies to the stated linear systems with polynomial encoding length.
The support count and running-time bounds are correct. The product counts every nonempty subset choice once, and its bounds by \((2^m-1)^\tau\) and \(2^{m\tau}\) are valid. Polynomial preprocessing and per-support arithmetic can be absorbed into the stated polynomial factor in \(L\).
The special cases follow. Pure-allocation enumeration gives the claimed \(m^\tau\) bound when same-type weights vanish. Singleton domains determine a unique allocation. Fixing both parameters makes the support count constant, while either parameter alone admits the stated hardness restriction.
The DCOP discussion is appropriately limited. The cited paper’s Theorems 1 and 2 establish finite termination and minimum solution cost; the output does not infer polynomial running time from them. [Yeoh, Felner and Koenig](https://tzin.bgu.ac.il/~felner/2010/DFBnB.pdf)
The hardness and membership arguments together establish the claimed \(\mathrm{NP}\)-completeness. The final equivalence with \(\mathrm{P}=\mathrm{NP}\) is correct.
⟨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.