Answer: Uniformity and coverage are both \(\mathrm{NP}\text{-hard}\), already for \(\tau=3\) and equal masses.
Theorem 8 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateUNIFORMITY / COVERAGE PARETO PRUNING are NP-hard, even for three objectives. For DIRECTED COVERAGE PARETO PRUNING, we are able to show hardness for four objectives.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set \(A\) of alternatives that are Pareto optimal under three evaluator types \(T\), their rational scores \(u_t(a)\), rational masses \(\mu_t>0\) summing to \(1\), and a slate size \(k\), compute an optimal size-\(k\) slate \(S\subseteq A\). For uniformity, maximize \(\min_{a,b\in S,\ a\ne b}D_\mu(a,b)\); for coverage, minimize \(\max_{a\in A}\min_{s\in S}D_\mu(a,s)\), where \(D_\mu(a,b)=\sum_{t\in T}\mu_t|u_t(a)-u_t(b)|\). Theorem 8 establishes hardness on the subfamily with \(\mu_t=1/3\).
A society is given by its support: the list of \(\tau=3\) evaluator types \(T\), each with a positive binary rational mass \(\mu_t\), with \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
The input also lists \(m\) alternatives \(A\) with distinct score vectors \((u_t(a))_{t\in T}\in\mathbb{Q}^{\tau}\); scores may have either sign, and larger scores are preferred. All alternatives are Pareto optimal. Let \(L\) be the total binary input length.
Define \(D_\mu(a,b)=\sum_{t\in T}\mu_t|u_t(a)-u_t(b)|\). A slate is a subset \(S\subseteq A\) with \(|S|=k\); any optimal slate is acceptable.
Uniformity maximizes \(\min_{a,b\in S,\ a\ne b}D_\mu(a,b)\), with \(2\le k\le m\). Coverage minimizes \(\max_{a\in A}\min_{s\in S}D_\mu(a,s)\), with \(1\le k\le m\).
For each objective separately, is computing an optimal slate polynomial-time solvable in \(m,\tau,k,L\), or is it NP-hard?
Known results: unweighted uniformity and coverage Pareto pruning are both NP-hard for three cardinal objectives, including rational-score instances ([verified full version](https://arxiv.org/html/2511.10716#A4.SS1)). The equal-mass subfamily of the stated problem has the same optimal slates; consequently, this target is already settled by the anchor and is not an open complexity question.
Both uniformity and coverage are \(\mathrm{NP}\text{-hard}\), even with support size fixed at \(\tau=3\). Here \(k\) is part of the input.
We use the supplied hardness result: selecting an optimal size-\(k\) subset of distinct, Pareto-optimal rational vectors in three dimensions is \(\mathrm{NP}\text{-hard}\) for both unweighted uniformity and unweighted coverage, using Manhattan distance. This is Theorem 4.3 of the [cited full version, with proof in Appendix D.1](https://arxiv.org/html/2511.10716#A4.SS1).
Take an instance of either unweighted problem, with alternatives \(A\subseteq\mathbb{Q}^3\) and slate size \(k\). Write each vector as \(x(a)=(x_1(a),x_2(a),x_3(a))\), and define its unweighted distance by
\(d(a,b)=\sum_{i=1}^{3}|x_i(a)-x_i(b)|.\)
Construct the target instance with \(T=\{1,2,3\}\), masses \(\mu_i=1/3\), and scores \(u_i(a)=x_i(a)\). Keep \(A\) and \(k\) unchanged.
All three masses are positive and sum to one. Each mass has constant binary encoding length as a rational numerator and denominator. The score vectors remain rational and distinct. Pareto optimality is preserved because every coordinate comparison is unchanged. Thus the construction satisfies all target restrictions, takes polynomial time, and increases the input length by only a constant amount beyond the copied data.
For every pair of alternatives,
\(D_\mu(a,b)=\sum_{i=1}^{3}\frac13|x_i(a)-x_i(b)|=\frac13d(a,b).\)
For every feasible slate \(S\), define its unweighted uniformity as \(U_0(S)=\min_{a,b\in S,\ a\ne b}d(a,b)\). Since \(k\ge2\), the minimum is over a nonempty finite set. Positive scaling commutes with this minimum, so
\(U_\mu(S)=\min_{a,b\in S,\ a\ne b}D_\mu(a,b)=\frac13U_0(S).\)
Consequently, for any two feasible slates \(S,S'\), we have \(U_\mu(S)\ge U_\mu(S')\) if and only if \(U_0(S)\ge U_0(S')\). The sets of maximizing slates are therefore identical, including all ties.
A polynomial-time algorithm returning any optimal target slate would consequently return an optimal slate for the unweighted hard instance. Hence computing an optimal uniformity slate is \(\mathrm{NP}\text{-hard}\).
For every feasible slate \(S\), define its unweighted coverage as \(C_0(S)=\max_{a\in A}\min_{s\in S}d(a,s)\). Since \(k\ge1\), all inner minima are defined. Positive scaling commutes with both the minima and the maximum, giving
\(C_\mu(S)=\max_{a\in A}\min_{s\in S}D_\mu(a,s)=\frac13C_0(S).\)
Thus \(C_\mu(S)\le C_\mu(S')\) if and only if \(C_0(S)\le C_0(S')\). The sets of minimizing slates are identical.
A polynomial-time algorithm returning any optimal target slate would therefore solve the unweighted coverage problem. Hence computing an optimal coverage slate is also \(\mathrm{NP}\text{-hard}\).
Neither objective admits a polynomial-time exact algorithm in \(m,\tau,k,L\) unless \(\mathrm{P}=\mathrm{NP}\). The hardness already holds with three equally weighted supported types; no expansion into a population of evaluators is needed.
⟨structured verdict parsed — rendered above⟩
Proved. The output correctly establishes NP-hardness for each objective, already with exactly three equally weighted supported types. No major or minor mathematical issues were found.
USER_TASK. The citation correctly identifies Theorem 4.3 and Appendix D.1 of the [full version](https://arxiv.org/html/2511.10716#A4.SS1). Reliance on this supplied result is justified; reproducing its proof is unnecessary.\[
D_\mu(a,b)=\sum_{i=1}^{3}\frac13|x_i(a)-x_i(b)|=\frac13d(a,b).
\]
The scaling factor is strictly positive and independent of both alternatives and the slate.
None. Both assigned objectives are resolved, and no 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.