Answer: Every finite multiplicative approximation is \(\mathrm{NP}\)-hard, already for \(k=3\), and for every fixed \(k\ge3\). No polynomial-time algorithm with any finite factor \(\rho(\tau,k,L)\) exists unless \(\mathrm{P}=\mathrm{NP}\).
Theorem 3.5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe offline variant of the problem MaxW-CSG is inapproximable for any k ≥3, unless P = NP.
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\ge0\) summing to \(1\), integer \(k\ge3\), symmetric rational interactions \(w_{tu}\), and rational threshold \(\theta\), choose \(x_{tq}\ge0\) with \(\sum_{q=1}^{k}x_{tq}=\mu_t\) for every \(t\), and compute an assignment maximizing \(F(x)=\frac12\sum_{q=1}^{k}\sum_{t,u\in T}w_{tu}x_{tq}x_{uq}\), or decide whether \(\max_x F(x)\ge\theta\).
A society is given by its support: the list \(T\) of \(\tau\) types with positive masses \(\mu_t\), each a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
The input also contains a binary integer \(k\ge3\) and symmetric binary rational interactions \(w_{tu}\), with both positive and negative entries; normalize nonzero entries to \(|w_{tu}|\ge1\). Zero entries represent absent interactions. Diagonal entries describe interactions between distinct agents of the same type.
All input is available offline. An assignment consists of real masses \(x_{tq}\ge0\) satisfying \(\sum_{q=1}^{k}x_{tq}=\mu_t\). Empty coalitions are allowed, so there are at most \(k\) nonempty coalitions, with no coalition-size bound.
Maximize \(F(x)=\frac12\sum_{q=1}^{k}\sum_{t,u\in T}w_{tu}x_{tq}x_{uq}\), and write \(\mathrm{OPT}=\max_xF(x)\). A multiplicative approximation with finite factor \(\rho\ge1\) returns a feasible rational assignment satisfying \(F(x)\ge\mathrm{OPT}/\rho\) whenever \(\mathrm{OPT}>0\); it must return a feasible assignment on other inputs as well. Assignments may list only nonempty coalitions.
Let \(L\) be the total input bit length. State running times and approximation factors in \(\tau\), \(k\), and \(L\); this model has no separate \(m\) parameter.
Does this continuous maximization problem admit a polynomial-time algorithm with any finite multiplicative approximation factor, or is every such approximation NP-hard?
Discrete total-weight partitioning into at most \(k\) coalitions is inapproximable for every finite multiplicative factor for \(k\ge3\), unless \(\mathrm{P}=\mathrm{NP}\). [Published result](https://research.isikun.edu.tr/server/api/core/bitstreams/483408aa-a7c9-494d-9019-79c1d853120a/content)
No result settling exactly the continuous formulation above was identified in the literature search.
Every finite multiplicative approximation is NP-hard, already for \(k=3\). Consequently, unless \(\mathrm{P}=\mathrm{NP}\), there is no polynomial-time approximation with any finite factor \(\rho(\tau,k,L)\), even one that depends arbitrarily on the input parameters.
The proof uses the permitted diagonal interactions and explicitly accounts for fractional assignments.
Fix an integer \(k\ge3\). We use the NP-completeness of graph \(3\)-colorability. [Garey, Johnson, and Stockmeyer](https://doi.org/10.1016/0304-3975%2876%2990059-1) establish this standard result.
Graph \(k\)-colorability is NP-hard for every such fixed \(k\): given a graph for \(3\)-colorability, add a clique of \(k-3\) vertices, each adjacent to every original vertex. The clique occupies \(k-3\) distinct colors unavailable to the original graph, so the resulting graph is \(k\)-colorable exactly when the original graph is \(3\)-colorable. For fixed \(k\), this transformation has polynomial size.
Let \(G=(V,E)\) be the resulting graph. Add isolated vertices until \(n=|V|\ge2\) is a power of two. This preserves \(k\)-colorability and increases the number of vertices by at most a constant factor.
Construct a society with support \(T=V\cup\{a\}\), where \(a\) is an additional type. Thus \(\tau=n+1\). Set
\(\displaystyle \mu_v=\frac1{2n}\quad(v\in V),\qquad \mu_a=\frac12.\)
These masses are positive dyadic rationals and sum to one. Define the symmetric interactions by
\(\displaystyle w_{vv}=8n^2\quad(v\in V),\)
\(\displaystyle w_{uv}=-8n^2\quad\text{if }\{u,v\}\in E,\)
\(\displaystyle w_{aa}=-8k(n-1),\)
with every remaining entry zero.
All nonzero interactions are integers of absolute value at least one, and both signs occur.
Writing \(z_q=x_{aq}\), the objective becomes
\(\displaystyle F(x)=4n^2\sum_{v\in V}\sum_{q=1}^k x_{vq}^2-8n^2\sum_{\{u,v\}\in E}\sum_{q=1}^k x_{uq}x_{vq}-4k(n-1)\sum_{q=1}^k z_q^2.\)
The edge coefficient accounts for the two symmetric entries in the original objective.
Fix any feasible assignment and a vertex type \(v\). Hold all other rows fixed, and write \(y_q=x_{vq}\) and \(\mu=1/(2n)\). As a function of this row alone, the objective has the form
\(\displaystyle g(y)=C+4n^2\sum_{q=1}^k y_q^2+\sum_{q=1}^k b_qy_q,\)
where \(C\) and the \(b_q\) do not depend on \(y\). The feasible row satisfies \(y_q\ge0\) and \(\sum_qy_q=\mu\).
Let \(\alpha_q=y_q/\mu\), and let \(e_q\) denote the \(q\)-th coordinate vector. Direct calculation gives
\(\displaystyle \sum_{q=1}^k\alpha_qg(\mu e_q)-g(y)=4n^2\left(\mu^2-\sum_{q=1}^k y_q^2\right)\ge0.\)
The inequality follows from
\(\displaystyle \mu^2=\left(\sum_qy_q\right)^2=\sum_qy_q^2+2\sum_{q<r}y_qy_r\ge\sum_qy_q^2.\)
Because the \(\alpha_q\) are nonnegative and sum to one, some \(q\) satisfies \(g(\mu e_q)\ge g(y)\). Moving all of type \(v\)'s mass into that coalition therefore does not decrease the objective.
Apply this argument successively to all \(n\) vertex types, using the current assignment at each step. The resulting feasible assignment has every vertex type entirely in one coalition and has objective at least that of the starting assignment. The additional type \(a\) has remained unchanged.
Thus allowing real, divisible masses cannot improve the optimum beyond assignments with unsplit vertex types.
Type \(a\) has no interactions with any other type. Since \(\sum_qz_q=1/2\), Cauchy–Schwarz gives
\(\displaystyle \sum_{q=1}^kz_q^2\ge\frac{(\sum_qz_q)^2}{k}=\frac1{4k}.\)
Its contribution consequently satisfies
\(\displaystyle -4k(n-1)\sum_{q=1}^kz_q^2\le-(n-1).\)
Equality holds at the feasible rational choice \(z_q=1/(2k)\) for every \(q\). We may therefore replace its row by this uniform row without decreasing the objective.
This uses exactly \(k\) nonempty coalitions, which is permitted by the model.
An assignment with unsplit vertex types defines a coloring \(c:V\to\{1,\ldots,k\}\). Let
\(\displaystyle b(c)=|\{\{u,v\}\in E:c(u)=c(v)\}|\)
be its number of monochromatic edges.
Each vertex diagonal contributes
\(\displaystyle \frac12(8n^2)\left(\frac1{2n}\right)^2=1.\)
Each monochromatic edge contributes
\(\displaystyle (-8n^2)\left(\frac1{2n}\right)^2=-2,\)
and every other edge contributes zero. With type \(a\) uniformly distributed, the total is therefore
\(\displaystyle F(x)=n-2b(c)-(n-1)=1-2b(c).\)
Define \(b_k(G)=\min_c b(c)\). Sections 2 and 3 show that every feasible real assignment can be replaced by one of the preceding form without decreasing its objective. Conversely, every coloring yields such a feasible rational assignment. Hence the exact continuous optimum is
\(\displaystyle \mathrm{OPT}=1-2b_k(G).\)
In particular:
This is a gap for the full continuous feasible region.
Suppose an algorithm always returns a feasible rational assignment and has some finite approximation factor \(\rho(\tau,k,L)\ge1\).
On a colorable instance, its guarantee forces
\(\displaystyle F(x)\ge\frac{\mathrm{OPT}}{\rho(\tau,k,L)}=\frac1{\rho(\tau,k,L)}>0.\)
On a noncolorable instance, feasibility alone forces \(F(x)\le\mathrm{OPT}\le-1\).
Thus checking the sign of the returned objective decides graph \(k\)-colorability. No evaluation or bound on the approximation factor is needed.
For a polynomial-time algorithm, the output has polynomial bit length. Its objective is a finite sum of products of binary rationals, so its sign can be computed exactly in polynomial time. Taking \(k=3\) therefore gives a polynomial-time decision algorithm for an NP-complete problem.
The constructed instance has \(\tau=n+1\). Under an explicit matrix encoding, its total bit length satisfies
\(\displaystyle L=O(\tau^2\log\tau+\log k).\)
The construction takes polynomial time in \(\tau+\log k\); for each fixed \(k\), the preceding graph transformation is also polynomial. In particular, the hardness excludes algorithms running in \(\operatorname{poly}(L)\), or even in \(\operatorname{poly}(\tau,k,L)\), with any finite factor \(\rho(\tau,k,L)\), unless \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The reduction establishes hardness for the stated continuous problem, already with \(k=3\). The fractional rounding argument and the negative offset are valid, and the resulting sign gap applies to every feasible real assignment. No major or minor mathematical issues were found.
The cited result that graph \(3\)-colorability is NP-complete is valid for finite simple undirected graphs, the standard interpretation used by the construction. The cited paper explicitly establishes NP-completeness results for graph \(3\)-colorability. [Garey, Johnson, and Stockmeyer](https://doi.org/10.1016/0304-3975%2876%2990059-1)
For each fixed \(k\ge3\), the clique construction correctly transfers hardness to graph \(k\)-colorability:
For \(k=3\), no clique vertices are added. The polynomial-size claim correctly requires \(k\) to be fixed; the proof states this restriction.
Adding isolated vertices preserves colorability. Padding to a power of two with \(n\ge2\) has only constant-factor overhead. These isolated vertices are included consistently in all subsequent counts and coefficients.
Assessment: correct.
The construction satisfies the input restrictions:
The objective expansion has the correct coefficients. Vertex diagonals contribute a coefficient \(4n^2\); each undirected edge contributes a coefficient \(-8n^2\), because its two symmetric matrix entries cancel the prefactor \(1/2\); and the additional type contributes a coefficient \(-4k(n-1)\).
Assessment: correct, including the factors of two.
With other rows fixed, the dependence on one vertex row is exactly the stated quadratic-plus-linear expression. There are no omitted nonlinear terms involving that row: interactions with other types are linear in its coordinates.
The coefficients \(\alpha_q=y_q/\mu\) are well-defined because \(\mu=1/(2n)>0\). They are nonnegative and sum to one.
In the displayed averaging identity:
Its nonnegativity follows from the stated expansion of \((\sum_q y_q)^2\), using nonnegative coordinates. Consequently, at least one pure row has objective value at least that of the current row.
Successive replacements preserve feasibility and never decrease the objective. Previously rounded rows remain unsplit, and the additional type remains unchanged. The argument applies to arbitrary real coordinates; it does not assume rationality.
The resulting conclusion concerns the existence of a dominating assignment with unsplit vertex rows. It does not require every optimizer to have unsplit rows.
Assessment: correct. Fractional assignments are fully accounted for.
The stated Cauchy–Schwarz inequality applies to the \(k\) real coordinates \(z_q\), whose sum is \(1/2\). It gives \(\sum_qz_q^2\ge1/(4k)\).
Since \(-4k(n-1)<0\), multiplying by this coefficient gives the claimed upper bound \(-(n-1)\). The direction of the inequality is correct.
The uniform row \(z_q=1/(2k)\) attains equality, is feasible, and is rational. Its lack of interactions with other types makes this replacement independent of the vertex rows.
The distinction between dyadic input masses and rational output coordinates causes no problem: the task permits rational assignments. Using all \(k\) coalitions also respects the model.
Assessment: correct.
For an unsplit vertex row, its diagonal contribution is exactly \(1\). A monochromatic edge contributes exactly \(-2\); an edge joining distinct coalitions contributes zero.
Thus the stated total \(n-2b(c)-(n-1)=1-2b(c)\) is correct.
Both directions needed for the optimum identity are present:
Therefore \(\mathrm{OPT}=1-2b_k(G)\) follows.
If the graph is colorable, \(b_k(G)=0\), so \(\mathrm{OPT}=1\). If it is not colorable, every coloring has at least one monochromatic edge, so \(\mathrm{OPT}\le-1\).
In particular, the negative upper bound holds for all feasible fractional assignments, not merely the rounded assignments.
Assessment: correct. The sign gap settles the continuous formulation.
On a colorable instance, any finite factor \(\rho(\tau,k,L)\ge1\) forces the returned objective to be strictly positive.
On a noncolorable instance, the requirement to return a feasible assignment forces its objective to be at most \(-1\), even though no approximation guarantee is required when the optimum is nonpositive.
Thus the returned objective’s sign distinguishes the two cases. The proof correctly avoids needing to compute, represent, or bound the approximation factor.
For a polynomial-time algorithm, the explicit rational output has polynomial bit length. Evaluating its quadratic objective and determining its sign using exact rational arithmetic takes polynomial time. This remains valid even when a positive returned value is very small.
Fixing \(k=3\) therefore gives the claimed polynomial-time decision procedure for an NP-complete problem if such an approximation algorithm exists.
Assessment: correct.
The stated bound \(L=O(\tau^2\log\tau+\log k)\) is valid for an explicit matrix encoding:
There is no missing factor of \(\tau^2\) multiplying \(\log k\), because the dependence on \(k\) occurs in only one interaction entry.
The construction is polynomial in \(\tau+\log k\). The graph transformation is polynomial for each fixed \(k\), as expressly stated. Hardness at \(k=3\) also excludes algorithms polynomial in \(\tau,k,L\): with \(k\) fixed, such a running time is polynomial in the reduced instance size.
Assessment: correct.
None. The proof resolves the assigned target without relying on the discrete partitioning result or leaving an unverified transfer from discrete to continuous assignments.
⟨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.