Answer: \(\mathrm{NP}\text{-hard}\) for every fixed \(k\ge3\).
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor any integer k ≥3, k-CLOSEST EQUIFAIR is NP-hard. We present a polynomial-time reduction from the 3-PARTITION problem (defined below) to k-CLOSEST EQUIFAIR.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(k\ge3\), rational masses \(\mu_{c,d}\ge0\) with \(\sum_d\mu_{c,d}=1/k\) for every color \(c\), and a rational threshold \(q\), let type \((c,d)\) have initial cluster label \(d\). Decide whether there is a finite or countable measurable partition \((F_a)\) of the population such that every \(F_a\) has equal mass from each color and \(J(F)\le q\), where \(J(F)=\frac12\int_{[0,1]^2}\left|\mathbf{1}[d(x)=d(y)]-\mathbf{1}[f(x)=f(y)]\right|\,d\rho(x)\,d\rho(y)\), and \(f(x)\) is the output cluster containing \(x\).
Let \(k\ge3\) and \(m\ge1\) be integers. A society is given by its support: the list of the \(\tau\) types \((c,d)\in\{1,\ldots,k\}\times\{1,\ldots,m\}\) with positive mass, each mass \(\mu_{c,d}\) a binary rational; omitted types have zero mass. Here \(\tau\) is the support size, not the number of possible types. Require \(\sum_d\mu_{c,d}=1/k\) for every color and \(\sum_c\mu_{c,d}>0\) for every initial cluster label.
Realize the population as \([0,1]\) with Lebesgue probability measure \(\rho\), partitioned into measurable type sets of the prescribed masses; \(c(x)\) and \(d(x)\) denote the color and initial cluster label. Type masses may be split arbitrarily among output clusters.
An admissible output is a finite or countable measurable partition \((F_a)\), up to null sets, into positive-mass clusters satisfying \(\rho(F_a\cap\{x:c(x)=c\})=\rho(F_a)/k\) for every \(a,c\). There is no prescribed number of output clusters; let \(f(x)=a\) on \(F_a\).
Given a nonnegative binary rational threshold \(q\), decide whether an admissible partition exists with \(J(F)\le q\), where \(J(F)=\frac12\int_{[0,1]^2}\left|\mathbf{1}[d(x)=d(y)]-\mathbf{1}[f(x)=f(y)]\right|\,d(\rho\otimes\rho)(x,y)\). This asks for an actual partition attaining the threshold, not merely an infimum below or equal to it.
Is this continuous closest equifair clustering decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? State running times in \(m,\tau,k,L\), where \(L\) is the total binary input length and \(k\) is part of the input.
For finite populations of indivisible points, the corresponding decision problem with unordered-pair disagreement cost is \(\mathrm{NP}\)-hard for every fixed \(k\ge3\), even with equal color-class sizes ([source](https://arxiv.org/pdf/2511.11539)). No result settling the exact atomless decision problem above was located in the literature search.
The decision problem is \(\mathrm{NP}\)-hard for every fixed \(k\ge3\). This holds with arbitrary splitting of type masses and with finite or countably infinite admissible partitions.
The reduction below establishes a lower bound valid for every measurable admissible partition. Attaining its threshold forces an actual solution of \(\mathrm{3\text{-}PARTITION}\). Conversely, every yes-instance has a finite admissible partition attaining the threshold.
Use the standard strongly \(\mathrm{NP}\)-complete restricted \(\mathrm{3\text{-}PARTITION}\) problem: given positive integers \(x_1,\ldots,x_{3h},T\) satisfying
\(\displaystyle \sum_{j=1}^{3h}x_j=hT,\qquad \frac T4<x_j<\frac T2,\)
decide whether the items can be partitioned into \(h\) triples, each summing to \(T\). Strong \(\mathrm{NP}\)-completeness permits restricting \(T\) to be polynomially bounded in \(h\). This is the source problem used in [Definition 4 and the hardness reduction of the supplied paper](https://arxiv.org/pdf/2511.11539).
Fix \(k\ge3\), and put \(N=khT\). Construct \(h\) initial bin clusters \(D_1,\ldots,D_h\) and \(3h\) initial item clusters \(R_1,\ldots,R_{3h}\):
This uses the bin/item support construction of the cited finite reduction. The argument below verifies its behavior directly for atomless populations.
Every color has total mass \(hT/N=1/k\), and every initial label has positive mass. The parameters are
\(\displaystyle m=4h,\qquad \tau=(k+2)h.\)
Write
\(\displaystyle S=\sum_{j=1}^{3h}x_j^2,\qquad C=\frac12\bigl((k-1)^2hT^2+S\bigr).\)
The chosen threshold will depend on whether \(k=3\) or \(k\ge4\).
Let \((F_a)\) be any admissible finite or countable partition. Define the following nonnegative, unnormalized masses:
\(\displaystyle t_a=\frac{N\rho(F_a)}k,\qquad r_{aj}=N\rho(F_a\cap R_j),\qquad z_{ai}=\frac{N}{k-1}\rho(F_a\cap D_i).\)
Fairness and the prescribed type masses imply
\(\displaystyle \sum_jr_{aj}=t_a,\qquad \sum_iz_{ai}=t_a,\qquad \sum_ar_{aj}=x_j,\qquad \sum_az_{ai}=T.\)
Indeed, the item clusters contain exactly color \(1\), while the bin clusters contain exactly colors \(2,\ldots,k\). Each \(F_a\) contains unnormalized mass \(t_a\) of each color. Also, \(t_a>0\) for every output cluster.
Set
\(\displaystyle u_a=\sum_jr_{aj}^2,\qquad v_a=\sum_iz_{ai}^2.\)
Expanding the disagreement indicator gives the exact identity
\(\displaystyle N^2J(F)=C-\sum_aH_a,\qquad H_a=u_a+(k-1)^2v_a-\frac{k^2}{2}t_a^2.\)
To verify this, let \(s_a=\rho(F_a)\), \(p_d=\rho(\{d(x)=d\})\), and \(b_{ad}=\rho(F_a\cap\{d(x)=d\})\). Then
\(\displaystyle J(F)=\frac12\left(\sum_dp_d^2+\sum_as_a^2-2\sum_{a,d}b_{ad}^2\right).\)
Here the initial cluster masses are \((k-1)T/N\) and \(x_j/N\), while the output overlaps are \((k-1)z_{ai}/N\) and \(r_{aj}/N\), yielding the claimed formula.
These identities hold for countable partitions: Tonelli’s theorem justifies the nonnegative sums, and all sums of squared masses are finite.
We shall repeatedly use the following elementary fact. For a finite or countable nonnegative sequence with \(\sum_\ell w_\ell=W<\infty\),
\(\displaystyle \sum_\ell w_\ell^2\le W^2,\)
with equality precisely when at most one entry is positive. This follows from
\(\displaystyle W^2-\sum_\ell w_\ell^2=2\sum_{\ell<\ell'}w_\ell w_{\ell'}.\)
Consequently,
\(\displaystyle u_a\le t_a^2,\qquad v_a\le t_a^2,\qquad \sum_au_a\le S,\qquad \sum_av_a\le hT^2.\)
For \(k=3\),
\(\displaystyle H_a=u_a+4v_a-\frac92t_a^2.\)
The following exact gap identity supplies both the bound and its equality conditions:
\(\displaystyle \frac S2-\sum_aH_a =\frac12\left(S-\sum_au_a\right) +\frac12\sum_a(t_a^2-u_a) +4\sum_a(t_a^2-v_a).\)
Every term on the right is nonnegative. Therefore
\(\displaystyle \sum_aH_a\le\frac S2,\qquad N^2J(F)\ge C-\frac S2=2hT^2.\)
Choose
\(\displaystyle q_3=\frac{2hT^2}{N^2}=\frac{2}{9h}.\)
Suppose an admissible partition satisfies \(J(F)\le q_3\). The preceding bound forces equality, so all three nonnegative terms in the gap identity vanish.
First, \(\sum_au_a=S\). For each item \(j\),
\(\displaystyle \sum_ar_{aj}^2\le x_j^2.\)
Equality of the total sums forces equality for every \(j\). Thus each item’s entire mass belongs to exactly one output cluster.
Second, \(u_a=t_a^2\) for every \(a\). Since \(\sum_jr_{aj}=t_a>0\), each output cluster contains mass from exactly one item.
Third, \(v_a=t_a^2\) for every \(a\). Since \(\sum_iz_{ai}=t_a>0\), each output cluster draws its nonred mass from exactly one bin.
Hence each item \(j\) is assigned to a unique bin, and its output cluster has \(t_a=x_j\). For each bin \(i\), the column identity \(\sum_az_{ai}=T\) says that the assigned item sizes sum to \(T\).
Every such group contains exactly three items: two or fewer sum to less than \(T\), while four or more sum to more than \(T\), by the strict bounds on the \(x_j\). We have therefore obtained a solution of \(\mathrm{3\text{-}PARTITION}\).
The argument also excludes countable partitions as additional witnesses: equality forces exactly one output cluster for each of the finitely many items.
Conversely, suppose the items are partitioned into triples summing to \(T\). Assign one triple to each bin.
For each item \(j\), create an output cluster containing:
The triple sums ensure that every bin’s masses are exhausted. Every output cluster has equal masses of all three colors.
These measurable subdivisions exist for any given realization: for a measurable Lebesgue set \(A\), the function \(s\mapsto\rho(A\cap[0,s])\) is continuous, allowing successive cuts of prescribed masses.
For the cluster associated with item \(j\),
\(\displaystyle t_a=x_j,\qquad u_a=v_a=x_j^2,\qquad H_a=\frac12x_j^2.\)
Thus this finite partition satisfies \(J(F)=q_3\).
We have proved
\(\displaystyle \mathrm{3\text{-}PARTITION}\text{ is yes}\quad\Longleftrightarrow\quad \exists F:\ J(F)\le q_3.\)
For completeness, the same support also proves hardness for each larger fixed number of colors.
Define
\(\displaystyle A_k=(k-1)^2-\frac{k^2}{2}=\frac{k^2-4k+2}{2}>0.\)
Then
\(\displaystyle H_a=u_a+A_kv_a-\frac{k^2}{2}(t_a^2-v_a).\)
The universal inequalities imply
\(\displaystyle \sum_aH_a\le S+A_khT^2=:B_k.\)
More explicitly,
\(\displaystyle B_k-\sum_aH_a =\left(S-\sum_au_a\right) +A_k\left(hT^2-\sum_av_a\right) +\frac{k^2}{2}\sum_a(t_a^2-v_a),\)
a sum of nonnegative quantities.
Choose
\(\displaystyle q_k=\frac{C-B_k}{N^2} =\frac{(2k-1)hT^2-S}{2N^2}.\)
This threshold is positive: the source promises give \(S<(T/2)\sum_jx_j=hT^2/2\).
If \(J(F)\le q_k\), the reward bound forces equality, so:
Thus there is exactly one output cluster for each bin. Its bin coordinate is \(z_{ai}=T\), so \(t_a=T\). Its whole items therefore sum to \(T\). As before, each group contains exactly three items, giving a valid \(\mathrm{3\text{-}PARTITION}\).
These equality arguments remain valid for countable partitions because a sum of nonnegative gaps can vanish only when every gap vanishes.
Given a valid three-partition, create one output cluster per bin, containing that entire bin and its assigned three whole item clusters.
Each color has mass \(T/N\) in this output cluster. Its reward is
\(\displaystyle H_a=\sum_{j\text{ assigned to }a}x_j^2+A_kT^2.\)
Summing gives \(\sum_aH_a=B_k\), and hence \(J(F)=q_k\).
Therefore the reduction is correct for every fixed \(k\ge4\) as well.
All constructed masses and thresholds are rational numbers with binary encodings. Put \(b=\lceil\log_2(khT+1)\rceil\). The construction has
\(\displaystyle m=4h,\qquad \tau=(k+2)h,\qquad L=O(\tau b).\)
It computes a sum of squares and writes \(\tau\) support entries. Elementary binary arithmetic, including fraction reduction if desired, gives construction time \(O((h+\tau)b^3)\).
On the strongly \(\mathrm{NP}\)-complete source family, \(T\) is polynomially bounded in \(h\). Thus the reduction is polynomial-time; a conservative bound expressed in the requested parameters is \(O((m+\tau+k)L^3)\) bit operations.
Consequently, an exact decision algorithm running in \(O((m+\tau+k+L)^C)\) for any constant \(C\) would imply \(\mathrm{P}=\mathrm{NP}\). Hardness already holds at \(k=3\), where \(m=4h\) and \(\tau=5h\).
The reduction addresses threshold attainment directly: yes-instances have explicit finite witnesses, and every admissible partition meeting the threshold yields a valid three-partition.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The reduction establishes \(\mathrm{NP}\)-hardness for every fixed \(k\ge3\), including arbitrary splitting of type masses and countably infinite admissible partitions. I found no mathematical gaps or incorrect steps.
The invoked source theorem is stated sufficiently precisely: restricted \(\mathrm{3\text{-}PARTITION}\) remains strongly \(\mathrm{NP}\)-complete under the promises \(\sum_jx_j=hT\) and \(T/4<x_j<T/2\), with polynomially bounded numerical values. The discussion following Definition 4 in the [cited paper](https://arxiv.org/pdf/2511.11539) confirms this restricted source problem.
The constructed society satisfies every input requirement. Color \(1\) has total mass \(\sum_jx_j/N=hT/N=1/k\). Each other color has total mass \(hT/N=1/k\). All \(4h\) initial labels have positive mass.
The support count is correct: there are \((k-1)h\) bin types and \(3h\) item types, giving \(\tau=(k+2)h\). In particular, the proof correctly distinguishes support size from the number of possible types.
Fairness gives each output cluster mass \(t_a/N\) of every color. Because all color-\(1\) mass lies in item labels, \(\sum_jr_{aj}=t_a\). Because the remaining colors lie in bin labels, \(\sum_iz_{ai}=t_a\). The column identities \(\sum_ar_{aj}=x_j\) and \(\sum_az_{ai}=T\) follow from the partition property.
The objective expansion is correct. For the two indicator functions, their absolute difference equals their sum minus twice their product. The three resulting integrals are respectively \(\sum_dp_d^2\), \(\sum_as_a^2\), and \(\sum_{a,d}b_{ad}^2\). Substitution gives exactly
\(N^2J(F)=C-\sum_aH_a\).
Countable partitions cause no convergence gap. Tonelli applies to the nonnegative indicator expansions. The squared-mass sums are finite, so the subsequent regroupings are justified.
The stated inequality \(\sum_\ell w_\ell^2\le W^2\), including its equality characterization, is valid for finite and countable nonnegative sequences of finite total mass.
Its row applications give \(u_a\le t_a^2\) and \(v_a\le t_a^2\). Its column applications give \(\sum_au_a\le S\) and \(\sum_av_a\le hT^2\).
The equality arguments are also valid: a vanishing sum of nonnegative gaps forces every individual gap to vanish. Positive column totals then force exactly one positive entry, rather than merely at most one.
Expanding the displayed gap identity gives \(S/2-\sum_aH_a\) with the correct coefficients. Every term on its right is nonnegative. Consequently, the lower bound and threshold \(q_3=2/(9h)\) are correct.
If \(J(F)\le q_3\), equality forces:
These conditions assign each item to one bin, and the bin column totals force assigned sizes to sum to \(T\). The strict source bounds exclude groups of at most two or at least four items. Thus the extracted groups are triples.
The converse construction is admissible and exhausts every type mass. The stated cutting argument is sufficient for measurable Lebesgue sets. Its computed reward \(H_a=x_j^2/2\) is correct, so the constructed partition attains \(q_3\).
The countable case is fully covered: equality forces exactly one output cluster per item, hence finitely many clusters.
The coefficient \(A_k=(k^2-4k+2)/2\) is strictly positive throughout the stated range. Both the rewritten reward and the gap identity are algebraically correct.
The threshold calculation is correct:
\(C-B_k=((2k-1)hT^2-S)/2\).
Its positivity follows from the stated strict bound \(S<hT^2/2\).
Equality forces every item and every bin to remain whole, while each output cluster contains exactly one bin. Because every positive output cluster contains bin mass, there are no additional clusters without bins. Each resulting cluster has \(t_a=T\), so its whole items sum to \(T\) and form a triple.
Conversely, a valid three-partition gives fair clusters with the stated rewards and attains \(q_k\). The necessity argument remains valid for countable partitions.
All numerators, denominators, labels, and intermediate quantities have \(O(b)\) bits for \(b=\lceil\log_2(khT+1)\rceil\). Squaring and summing do not invalidate this bound. Therefore \(L=O(\tau b)\) and the conservative construction time \(O((h+\tau)b^3)\) are valid.
The bound \(O((m+\tau+k)L^3)\) is likewise a valid conservative bound for the constructed instances. Fixing \(k\), particularly \(k=3\), makes the reduction polynomial in the source input length. Consequently, the stated implication that a polynomial-time decision algorithm would yield \(\mathrm{P}=\mathrm{NP}\) is justified.
The proof settles the requested hardness alternative. It addresses actual threshold attainment: yes-instances have finite witnesses, and every finite or countable witness meeting the threshold yields a source solution. It does not require any claim about whether an unattained infimum equals the threshold.
No repairs or additional clarifications are needed. The output establishes hardness without asserting membership in \(\mathrm{NP}\), which is sufficient for the task.
⟨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.