Answer: \(\mathrm{NP}\text{-hard}\), even with \(\tau=1\), singleton classes, and explicit four-entry monotone tables.
Theorem 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateCSC is NP-hard and W[1]-hard with respect to the number z of classes even if all the synergy functions are monotone.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given alternatives \(A\) partitioned into classes \(C_1,\ldots,C_z\), committee size \(k\), and a finite support of complete rankings \(t\) with binary-rational masses \(\mu_t\geq 0\) summing to \(1\), define each alternative's SNTV support share as \(p_\mu(a)=\sum_{t:\,a\text{ is ranked first in }t}\mu_t\). Given explicit nonnegative rational synergy tables \(g_J\) for listed class subsets \(J\), each nondecreasing in every coordinate, compute a size-\(k\) committee \(S\subseteq A\) maximizing \(\sum_{a\in S}p_\mu(a)+\sum_{J}g_J((|S\cap C_j|)_{j\in J})\).
Let \(A\) contain \(m\geq 1\) alternatives, partitioned into \(z\) nonempty classes \(C_1,\ldots,C_z\), and let \(1\leq k\leq m\) be an integer.
A society is given by its support: a list of \(\tau\) distinct strict complete rankings \(t\) of \(A\), each with positive binary-rational mass \(\mu_t\), with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings. Define \(p_\mu(a)=\sum_{t:\,a\text{ ranks first in }t}\mu_t\).
The input lists a family \(\mathcal J\) of nonempty subsets of \(\{1,\ldots,z\}\). For each \(J\in\mathcal J\), it explicitly supplies every entry of a coordinatewise nondecreasing table \(g_J:\prod_{j\in J}\{0,\ldots,|C_j|\}\to\mathbb Q_{\geq0}\), with coordinates ordered by class index and values encoded in binary. Unlisted subsets contribute zero.
Choose an ordinary committee \(S\subseteq A\) with \(|S|=k\) maximizing \(F(S)=\sum_{a\in S}p_\mu(a)+\sum_{J\in\mathcal J}g_J((|S\cap C_j|)_{j\in J})\); any maximizer is acceptable. Let \(L\) be the total input bit length, including all table entries. State running times in \(m,\tau,L,k,z\).
Is computing an optimal committee for this distributional SNTV problem possible in polynomial time, or is the problem NP-hard?
The discrete committee problem with integer individual weights and explicit monotone synergy tables is NP-hard and \(\mathrm{W}[1]\)-hard parameterized by \(z\). [Source](https://ojs.aaai.org/index.php/AAAI/article/download/11479/11338)
No result settling exactly the normalized distributional SNTV problem above was identified in the search.
Computing an optimal committee is \(\mathrm{NP}\)-hard, even when \(\tau=1\), every class is a singleton, and every listed synergy table has only four entries, all belonging to \(\{0,2\}\). The threshold decision version is \(\mathrm{NP}\)-complete.
Moreover, the normalized problem remains \(\mathrm{W}[1]\)-hard parameterized by \(z\), but is polynomial-time solvable for every fixed \(z\).
Reduce from the \(\mathrm{NP}\)-complete CLIQUE problem: given a simple undirected graph \(G=(V,E)\) and an integer \(r\), decide whether \(G\) contains a clique of size \(r\). We restrict to \(2\leq r\leq |V|\); instances outside this range are immediately decidable, so this restriction preserves hardness.
Write \(V=\{v_1,\ldots,v_n\}\). Construct the following committee instance.
\[
\]
\(g_{\{i,j\}}(0,0)=g_{\{i,j\}}(1,0)=g_{\{i,j\}}(0,1)=0,\qquad g_{\{i,j\}}(1,1)=2.\)
The empty display above is unnecessary; the four entries specified in the equation are the entire table. Each table is nonnegative and coordinatewise nondecreasing. All other scopes are unlisted and contribute zero.
For a committee \(S\), let \(V_S=\{v_i:a_i\in S\}\), and let \(e_G(V_S)\) denote the number of edges induced by \(V_S\). By construction,
\(F(S)=2e_G(V_S)+\mathbf{1}_{\{a_1\in S\}}.\)
Set the decision threshold to \(q=2\binom{r}{2}\).
If \(G\) has an \(r\)-clique, its corresponding committee satisfies \(F(S)\geq q\).
Conversely, suppose \(G\) has no \(r\)-clique. Every \(r\)-vertex set then induces at most \(\binom{r}{2}-1\) edges. Consequently every feasible committee satisfies
\(F(S)\leq 2\bigl(\binom{r}{2}-1\bigr)+1=q-1<q.\)
Therefore,
\(G\text{ contains an }r\text{-clique}\quad\Longleftrightarrow\quad \max_{|S|=k}F(S)\geq q.\)
The construction writes one ranking and four constant-size entries per edge. Its output length is \(O((n+|E|)\log(n+1))\), and it can be produced in polynomial time.
An algorithm returning any optimal committee would decide CLIQUE by evaluating that committee and comparing its score with \(q\). This proves hardness for exactly the normalized distributional model in the question.
Consider the decision problem obtained by supplying an additional binary-rational threshold \(q\) and asking whether some size-\(k\) committee satisfies \(F(S)\geq q\).
A certificate is the committee itself. Its cardinality and class counts can be checked directly. Its first-place score is computed from the listed support, and each synergy contribution is read from its explicit table.
These calculations require polynomial bit complexity. Indeed, the product of all encoded denominators, including the denominator of \(q\), has bit length at most their total encoded length. Using this common denominator, all relevant sums and comparisons involve integers of polynomial bit length.
Thus the decision problem belongs to \(\mathrm{NP}\). Together with Section 1, it is \(\mathrm{NP}\)-complete.
For completeness, the stronger parameterized hardness also survives normalization.
Use Multicolored Clique: vertices are partitioned into \(h\) nonempty color classes \(V_1,\ldots,V_h\), and the question is whether one can select one vertex from each class so that all selected vertices are pairwise adjacent. This problem is \(\mathrm{W}[1]\)-hard parameterized by \(h\); it is also the starting problem in Theorem 1 of the [cited paper](https://ojs.aaai.org/index.php/AAAI/article/download/11479/11338).
Assume \(h\geq2\). By adding isolated vertices, make every color class have the same size \(n\), and write \(V_i=\{v_i^1,\ldots,v_i^n\}\). Such padding preserves the answer because an isolated vertex cannot belong to a clique of size \(h\).
Create alternative classes \(C_1,\ldots,C_h\), each of size \(n\), and a padding class \(D\) of size \(hn\). Set
\(m=2hn,\qquad z=h+1,\qquad k=hn.\)
Again use a single strict ranking of mass \(1\), with some fixed alternative \(a^\star\) first.
For each \(i<j\), define, on the entire domain \(\{0,\ldots,n\}^2\),
\(\varepsilon_{ij}(x,y)=\begin{cases}1,&x\geq1,\ y\geq1,\ \{v_i^x,v_j^y\}\in E,\\0,&\text{otherwise},\end{cases}\)
and explicitly supply the table
\(g_{\{i,j\}}(x,y)=2\bigl(x+y+\varepsilon_{ij}(x,y)\bigr).\)
Also supply the unary table for the padding class:
\(g_{\{h+1\}}(d)=2(h-1)d,\qquad 0\leq d\leq hn.\)
All entries are nonnegative integers. For \(x<n\),
\(g_{\{i,j\}}(x+1,y)-g_{\{i,j\}}(x,y)=2+2\bigl(\varepsilon_{ij}(x+1,y)-\varepsilon_{ij}(x,y)\bigr)\in\{0,2,4\}.\)
The same calculation applies when increasing \(y\). Thus every pair table is coordinatewise nondecreasing, and the unary table is also nondecreasing.
For a committee \(S\), write \(x_i=|S\cap C_i|\) and \(d=|S\cap D|\). Since \(\sum_i x_i+d=k\), its synergy sum is
\(\sum_{i<j}g_{\{i,j\}}(x_i,x_j)+g_{\{h+1\}}(d)=2(h-1)k+2\sum_{i<j}\varepsilon_{ij}(x_i,x_j).\)
Here each \(x_i\) occurs in exactly \(h-1\) unordered pairs. Therefore
\(F(S)=2(h-1)k+2\sum_{i<j}\varepsilon_{ij}(x_i,x_j)+\mathbf{1}_{\{a^\star\in S\}}.\)
Set \(q=2(h-1)k+2\binom{h}{2}\).
If a multicolored clique has vertices \(v_i^{r_i}\), choose \(x_i=r_i\) and \(d=hn-\sum_i r_i\). These counts are feasible: each \(r_i\) lies between \(1\) and \(n\), and \(0\leq d\leq hn\). A committee realizing them has score at least \(q\).
Conversely, attaining \(q\) requires every \(\varepsilon_{ij}(x_i,x_j)\) to equal \(1\): one missing contribution loses \(2\), whereas the first-place term contributes at most \(1\). Because \(h\geq2\), this also requires every \(x_i\geq1\). The vertices \(v_i^{x_i}\) therefore form a multicolored clique.
The construction explicitly writes \(\binom{h}{2}(n+1)^2+hn+1\) table entries. Its bit length and construction time are bounded by \(O(h^2(n+1)^2\log(hn+1))\), and its output parameter is \(z=h+1\). This is a parameterized reduction, proving \(\mathrm{W}[1]\)-hardness in \(z\), even with \(\tau=1\).
Let \(c_j=|C_j|\). Compute every \(p_\mu(a)\), then order each class as \(a_{j,1},\ldots,a_{j,c_j}\) by nonincreasing first-place probability. Define
\(P_j(x)=\sum_{\ell=1}^{x}p_\mu(a_{j,\ell}),\qquad P_j(0)=0.\)
For fixed class counts \(x_1,\ldots,x_z\), selecting the first \(x_j\) alternatives in each class maximizes the individual-score term. This follows because the sum of any \(x_j\) probabilities in that class is at most the sum of its \(x_j\) largest probabilities. Synergy contributions depend only on the counts.
Hence it suffices to maximize
\(H(x_1,\ldots,x_z)=\sum_{j=1}^{z}P_j(x_j)+\sum_{J\in\mathcal J}g_J((x_j)_{j\in J})\)
subject to \(0\leq x_j\leq c_j\) and \(\sum_jx_j=k\).
Enumerate the first \(z-1\) counts, each between \(0\) and \(\min(c_j,k)\), and determine the last count from the sum constraint. There are at most \((k+1)^{z-1}\) assignments to inspect. Reject infeasible assignments, evaluate the rest, and retain a maximizing vector.
A conservative bit-complexity bound, including input reading, sorting, table evaluation, and exact arithmetic, is
\(O\!\left(\left[\tau m+m\log(m+1)+L+(k+1)^{z-1}(z+L)\right](L+1)^3\right).\)
Thus the problem is polynomial-time solvable for every fixed \(z\), although a running time \(f(z)\operatorname{poly}(m,\tau,L,k)\) would imply \(\mathrm{FPT}=\mathrm{W}[1]\).
The boundary cases are also easy: for \(k=1\), evaluate all singleton committees; for \(k=m\), there is one feasible committee; and for \(z=1\), all synergy contributions are fixed, so select the \(k\) highest-probability alternatives.
⟨structured verdict parsed — rendered above⟩
The prover resolves the requested problem correctly: computing an optimal committee is \(\mathrm{NP}\)-hard under the stated normalized distributional model. The threshold decision problem is \(\mathrm{NP}\)-complete. The additional parameterized-hardness claim and fixed-\(z\) algorithm are also justified.
No major or minor mathematical issues were found.
The source problem is stated precisely. Restricting CLIQUE to \(2\leq r\leq |V|\) preserves hardness because the excluded cases are immediately decidable.
The constructed instance satisfies every relevant input requirement:
For singleton classes, an edge table contributes \(2\) exactly when both associated alternatives are selected. Consequently, the identity
\[
F(S)=2e_G(V_S)+\mathbf{1}_{\{a_1\in S\}}
\]
is correct.
The threshold argument checks both directions:
The gap of \(2\) between successive edge contributions exceeds the possible first-place contribution of \(1\). Thus normalization does not invalidate the reduction.
The stated output-size bound is valid: the ranking, alternatives, and partition require \(O(n\log(n+1))\) bits, while the edge scopes and tables require \(O(|E|\log(n+1))\) bits. The threshold also has polynomial encoding length.
Finally, returning any maximizing committee suffices: evaluating its score and comparing it with \(q\) decides the source instance. The reduction therefore proves the requested optimization hardness.
A committee is a polynomial-size certificate. Its size, class counts, first-place contribution, and applicable table entries can all be checked in polynomial time.
The denominator argument is correct. For positive encoded denominators \(d_1,\ldots,d_s\), the bit length of their product is bounded by their aggregate encoding length, up to an additive constant. Scaling the relevant rational values to this common denominator yields integers of polynomial bit length. Summing polynomially many such integers adds only polynomially many bits.
For the decision problem, the total encoding length includes the additional threshold. The prover explicitly includes its denominator in the argument.
Hence certificate verification has polynomial bit complexity, establishing membership in \(\mathrm{NP}\). Together with the reduction, this proves \(\mathrm{NP}\)-completeness.
The cited premise is appropriate: Multicolored Clique asks for one vertex from each of \(h\) color classes, all pairwise adjacent, and is \(\mathrm{W}[1]\)-hard parameterized by \(h\). The linked paper indeed uses this source problem in Theorem 1. [Source](https://ojs.aaai.org/index.php/AAAI/article/download/11479/11338)
The additional construction is independently justified in the prover’s text.
Padding and domains. Restricting to \(h\geq2\) excludes only trivial cases. Adding isolated vertices preserves the answer because none can participate in a clique of size at least \(2\). The resulting classes and padding class are nonempty, and \(k=hn\leq m=2hn\).
The definition of \(\varepsilon_{ij}\) explicitly handles zero counts, avoiding undefined vertex indices.
Monotonicity. Increasing either coordinate by one changes the corresponding table value by
\[
2+2\Delta\varepsilon,
\]
where \(\Delta\varepsilon\in\{-1,0,1\}\). Thus the change lies in \(\{0,2,4\}\). This verifies monotonicity throughout the domain, including transitions from zero. The unary padding table is also nondecreasing.
Score identity. Each \(x_i\) appears in exactly \(h-1\) pair scopes. Combining those terms with the padding contribution and the cardinality equation gives exactly the displayed synergy sum and objective formula.
Forward implication. Clique vertex indices \(r_i\) produce valid class counts. The proposed padding count is within its capacity, and an ordinary committee realizes these counts. Every pair indicator then equals \(1\), yielding score at least \(q\).
Reverse implication. Each pair indicator is at most \(1\). If any is zero, the synergy score loses at least \(2\), which the first-place contribution cannot compensate. Thus meeting the threshold forces every pair indicator to equal \(1\). Since \(h\geq2\), every class occurs in a pair, forcing every \(x_i\geq1\). The indexed vertices consequently form a multicolored clique.
Reduction size and parameter. The table-entry count and bit-length bound are valid. The construction is polynomial-time, and its output parameter is \(z=h+1\). These facts establish the claimed parameterized reduction.
For fixed class counts, the individual-score contribution is maximized by selecting the highest-probability alternatives in each class. This follows directly from the ordering, while all synergy contributions remain fixed. Arbitrary tie-breaking is valid because any maximizer is acceptable.
The enumeration covers every feasible count vector: its first \(z-1\) coordinates appear among the enumerated choices, and the final coordinate is uniquely determined by the cardinality constraint. Infeasibility checks enforce all remaining bounds.
The number of inspected assignments is at most \((k+1)^{z-1}\). Keeping a maximizing vector and selecting the corresponding class prefixes therefore returns an optimal committee.
The stated conservative bound
\[
O\!\left(\left[\tau m+m\log(m+1)+L+(k+1)^{z-1}(z+L)\right](L+1)^3\right)
\]
adequately covers input reading, probability computation, sorting, table evaluation, and polynomial-bit exact arithmetic. Explicit tables can be scanned within the allotted per-assignment cost; constant-time lookup is unnecessary.
For fixed \(z\), the bound is polynomial because \(k\leq m\). This is consistent with \(\mathrm{W}[1]\)-hardness: the exponent depends on \(z\). The stated implication of an algorithm with running time \(f(z)\operatorname{poly}(m,\tau,L,k)\) is correct.
The cases \(k=1\), \(k=m\), and \(z=1\) are handled correctly. In particular, when \(z=1\), the sole class count is fixed at \(k\), so every synergy contribution is constant across feasible committees.
No mathematical repair or additional clarification is needed. The empty display acknowledged in Section 1 is a harmless formatting artifact.
⟨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.