Answer: \(\mathrm{NP}\)-complete for each fixed feature family: product, minimum, and maximum.
Proposition 2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateProblem Pk admits a dual formulation Dk which has |P|+|I|+1 variables and 2(|P|+|I|) constraints: (Dk) max Γ=(α,β,µ)∈Rp+q+1 −1 4λΓ⊺Q⊺Dk −1QΓ + Γ⊺L 0 ≤α ≤1 −1 ≤β ≤1 where p = |P|, q = |I| and Dk is a square diago- nal matrix of size 2n whose diagonal contains the current weighting coefficients 1/ q m(k) j 2 + η2 (and 0 for the single- tons).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(n\), a fixed questionnaire \(Q\) of rational alternative pairs \((x_q,y_q)\in[0,1]^n\), a fixed feature map \(\phi\), and a finite support of complete respondent profiles \(\rho\in\{\succ,\prec,\sim\}^{Q}\) with positive binary-rational masses \(\mu_\rho\) summing to \(1\), together with rational \(\lambda,\delta>0\), find a normalized model \(m\) minimizing \(\sum_{\rho}\mu_\rho\sum_{q\in Q}\ell_{\rho,q}(m)+\lambda\sum_{|S|\ge2}|m_S|\), subject to \(m_{\emptyset}=0\) and \(\sum_{S\subseteq N}m_S=1\). Here \(\ell_{\rho,q}(m)=(\delta-\langle m,\phi(x_q)-\phi(y_q)\rangle)_+\) for \(x_q\succ y_q\), the same expression with \(x_q,y_q\) reversed for \(y_q\succ x_q\), and \(|\langle m,\phi(x_q)-\phi(y_q)\rangle|\) for indifference.
Let \(N=\{1,\ldots,n\}\), with \(n\ge2\). Fix one feature family throughout: for every nonempty \(S\subseteq N\), either \(\phi_S(x)=\prod_{i\in S}x_i\), or \(\phi_S(x)=\min_{i\in S}x_i\), or \(\phi_S(x)=\max_{i\in S}x_i\). Set \(\phi_\emptyset=0\); features are specified by this formula, not by an explicit exponential table.
The input includes a finite questionnaire \(Q\) of rational pairs \((x_q,y_q)\in[0,1]^n\). A society is given by its support: the list of the \(\tau\) complete response types \(\rho\in\{\succ,\prec,\sim\}^{Q}\) with positive binary-rational masses \(\mu_\rho\) summing to \(1\). Thus \(\tau\) is the support size, not the number \(3^{|Q|}\) of possible types.
A model is a real coefficient vector \(a=(a_S)_{S\subseteq N}\), subject only to \(a_\emptyset=0\) and \(\sum_{S\subseteq N}a_S=1\). Coefficients may have either sign; singleton coefficients are unpenalized, and no monotonicity or range constraints are imposed.
Write \(d_q(a)=\sum_{S\subseteq N}a_S(\phi_S(x_q)-\phi_S(y_q))\). For \(\rho_q=\succ,\prec,\sim\), respectively, define \(\ell_{\rho,q}(a)=\max\{0,\delta-d_q(a)\},\max\{0,\delta+d_q(a)\},|d_q(a)|\); the first two responses express strict preference in the indicated direction, and the third expresses indifference.
Given positive binary-rational \(\lambda,\delta\) and a binary-rational threshold \(B\ge0\), let \(J(a)=\sum_\rho\mu_\rho\sum_{q\in Q}\ell_{\rho,q}(a)+\lambda\sum_{|S|\ge2}|a_S|\). Decide whether a feasible model has \(J(a)\le B\).
State running times in the number of criteria \(m=n\), support size \(\tau\), questionnaire size \(|Q|\), and total input bit length \(L\).
For each fixed feature family above, is this threshold problem in P or NP-hard?
For finite preference data, a compact dual formulation is reported for each quadratic IRLS subproblem, with \(p+q+1\) variables and \(2(p+q)\) box constraints, where \(p\) and \(q\) count strict-preference and indifference examples; this is not a complexity classification of the full objective. [Source](https://www.ijcai.org/proceedings/2023/0421.pdf)
No verified complexity classification for the exact distribution-weighted problem specified here was located.
For each fixed feature family—product, minimum, and maximum—the threshold problem is \(\mathrm{NP}\)-complete under polynomial-time many-one reductions.
Hardness holds even when all questionnaire coordinates are Boolean, every response is strict, \(\delta=1\), and \(\tau\le |Q|+1\). The proof below uses the stated freedom to choose signed coefficients and leaves singleton coefficients unpenalized.
Write \(r=|Q|\). If \(r=0\), the answer is immediately yes: a model with one singleton coefficient equal to \(1\) has objective \(0\). We henceforth consider \(r\ge1\).
For each question and response symbol, define its marginal mass by
\[
\text{[replace]}
\]
\(w_{q,s}=\sum_{\rho:\rho_q=s}\mu_\rho,\qquad s\in\{\succ,\prec,\sim\}.\)
Because the loss is summed question by question, the objective depends only on these marginals:
\[
\text{[replace]}
\]
\(J(a)=\sum_{q\in Q}\bigl(w_{q,\succ}\max\{0,\delta-d_q(a)\}+w_{q,\prec}\max\{0,\delta+d_q(a)\}+w_{q,\sim}|d_q(a)|\bigr)+\lambda\sum_{|S|\ge2}|a_S|.\)
These masses can be computed using \(O(\tau r)\) rational additions. Their encoding lengths are polynomial in \(L\).
For every nonempty subset \(S\), introduce nonnegative variables \(u_S,v_S\) and set \(a_S=u_S-v_S\). Introduce nonnegative variables \(t_{q,\succ},t_{q,\prec},t_{q,\sim}\). Impose:
A feasible model supplies a feasible LP solution by taking the positive and negative parts of its coefficients and setting each \(t\) to its actual loss. Conversely, an LP solution supplies a feasible model satisfying \(J(a)\le B\), because its actual losses are bounded by the corresponding \(t\)-variables and \(|u_S-v_S|\le u_S+v_S\).
There are \(4r+1\) inequalities and one normalization equality. Adding slack or surplus variables therefore gives a system \(Az=b,\ z\ge0\) with \(4r+2\) rows.
If this system is feasible, choose a feasible vector having the smallest number of positive coordinates. Its supported columns of \(A\) are linearly independent.
Indeed, suppose they admit a nonzero dependence vector \(h\), supported on those coordinates, with \(Ah=0\). Reverse its sign if necessary so that some \(h_j>0\), and set
\[
\text{[replace]}
\]
\(\varepsilon=\min_{h_j>0}\frac{z_j}{h_j}.\)
Then \(z-\varepsilon h\) remains nonnegative and feasible, and has smaller support—a contradiction. Consequently, the chosen vector has at most \(4r+2\) positive coordinates.
All matrix entries have polynomial encoding length. In particular, a product feature is obtained by multiplying at most \(m\) input rationals; minimum and maximum features select an input rational. Independent supported columns contain an invertible square submatrix. Cramer’s rule, after clearing denominators, shows that their solution coordinates are rational and have polynomial encoding length: for a square system of order \(s\) whose entries have at most \(H\) bits, the resulting coordinates need \(O(s^2H+s\log s)\) bits.
Thus every yes-instance has a rational model with at most \(4r+2\) nonzero coefficients and polynomial total encoding length. A verifier can evaluate its features, normalization, and objective exactly in \(\operatorname{poly}(m,\tau,r,L)\) time. All three problems therefore belong to \(\mathrm{NP}\).
We reduce from unweighted maximum cut: given a simple undirected graph \(G=(V,E)\) and an integer \(k\), decide whether some cut has at least \(k\) edges. This problem is \(\mathrm{NP}\)-complete. [Garey, Johnson, and Stockmeyer, *Some simplified NP-complete graph problems*](https://doi.org/10.1016/0304-3975%2876%2990059-1).
We may assume that \(G\) has no isolated vertices and \(1\le k\le |E|\). Delete isolated vertices; the omitted trivial cases can be mapped to fixed yes- or no-instances satisfying these restrictions.
Introduce two additional criteria \(g,b\), and identify the criteria, after relabeling, with
\[
\text{[replace]}
\]
\(N=V\cup\{g,b\},\qquad m=|V|+2.\)
The criterion \(g\) will gate the cut expression. The criterion \(b\) will provide a singleton invisible to all questions.
Let
\[
\text{[replace]}
\]
\(\mathcal U=\{\{i\},\{g,i\}:i\in V\}\cup\{\{i,j\},\{g,i,j\}:\{i,j\}\in E\}.\)
For each \(U\in\mathcal U\), create the question \((x_U,y)\), where:
These pairs are distinct, and
\[
\text{[replace]}
\]
\(r=2|V|+2|E|.\)
Assign integer weights
\[
\text{[replace]}
\]
\(c_{\{i\}}=\deg_G(i),\quad c_{\{g,i\}}=-\deg_G(i),\quad c_{\{i,j\}}=-2,\quad c_{\{g,i,j\}}=2.\)
They satisfy \(\sum_{U\in\mathcal U}c_U=0\).
For the product or minimum family, write
\[
\text{[replace]}
\]
\(D_{U,S}=\phi_S(x_U)-\phi_S(y),\qquad F(S)=\sum_{U\in\mathcal U}c_U D_{U,S}.\)
The two feature families coincide on Boolean points.
If \(b\in S\), both feature values vanish, so \(F(S)=0\).
Suppose \(b\notin S\). Since \(S\ne\emptyset\),
\[
\text{[replace]}
\]
\(D_{U,S}=\mathbf1_{\{S\cap U=\emptyset\}}-1.\)
The constant terms cancel because \(\sum_Uc_U=0\). Put \(z_i=\mathbf1_{\{i\in S\}}\) and \(E_U=\prod_{i\in U}(1-z_i)\). Each edge \(\{i,j\}\) contributes
\[
\text{[replace]}
\]
\(E_{\{i\}}+E_{\{j\}}-E_{\{g,i\}}-E_{\{g,j\}}-2E_{\{i,j\}}+2E_{\{g,i,j\}}\)
\(\displaystyle =z_g\bigl((1-z_i)+(1-z_j)-2(1-z_i)(1-z_j)\bigr)\)
\(\displaystyle =z_g(z_i+z_j-2z_iz_j).\)
The last parenthesis is \(1\) exactly when the edge crosses the cut determined by \(S\cap V\). Hence
\[
\text{[replace]}
\]
\(F(S)=\mathbf1_{\{g\in S\}}\operatorname{cut}_G(S\cap V)\qquad\text{when }b\notin S.\)
Let \(K\) denote the maximum cut size. We have proved:
The vanishing singleton scores are what prevents the unpenalized singleton coefficients from defeating the reduction.
Choose a power of two \(C\) strictly larger than \(\max_U|c_U|\), and set
\[
\text{[replace]}
\]
\(p_U=\frac{1+c_U/C}{2}.\)
We require marginal probability \(p_U\) of response \(\succ\), marginal probability \(1-p_U\) of response \(\prec\), and no indifference.
Here is an explicit society with these marginals. Sort the distinct values in \(\{0,1\}\cup\{p_U:U\in\mathcal U\}\):
\[
\text{[replace]}
\]
\(0=t_0<t_1<\cdots<t_\tau=1.\)
For each interval, define a complete response type of mass \(t_j-t_{j-1}\), responding \(\succ\) to question \(U\) exactly when \(t_j\le p_U\), and otherwise responding \(\prec\).
All masses are positive binary rationals and sum to \(1\). The total mass responding \(\succ\) to question \(U\) is exactly \(p_U\). Adjacent types differ at a question whose probability is their common boundary, so the listed types are distinct. Moreover, \(\tau\le r+1\).
Set
\[
\text{[replace]}
\]
\(\delta=1,\qquad \lambda=\frac{k-\tfrac12}{C},\qquad B=r-\frac1{2C}.\)
These satisfy \(\lambda>0\), \(B\ge0\), and the required rational encoding conditions.
For any real \(d\), the expected loss on question \(U\) obeys
\[
\text{[replace]}
\]
\(p_U\max\{0,1-d\}+(1-p_U)\max\{0,1+d\}\ge1-\frac{c_U}{C}d.\)
This follows by replacing each maximum by its affine argument. Equality holds whenever \(-1\le d\le1\).
Let \(A(a)=\sum_{|S|\ge2}|a_S|\). Summing the inequalities yields
\[
\text{[replace]}
\]
\(J(a)\ge r-\frac1C\sum_Sa_SF(S)+\lambda A(a).\)
Because singleton scores vanish and \(0\le F(S)\le K\),
\[
\text{[replace]}
\]
\(\sum_Sa_SF(S)=\sum_{|S|\ge2}a_SF(S)\le\sum_{|S|\ge2}|a_S|F(S)\le K A(a).\)
This explicitly covers negative coefficients. Therefore
\[
\text{[replace]}
\]
\(J(a)\ge r+\left(\lambda-\frac KC\right)A(a).\)
If \(K\le k-1\), then
\[
\text{[replace]}
\]
\(\lambda-\frac KC\ge\frac1{2C}.\)
Every feasible model consequently has \(J(a)\ge r>B\). Thus the constructed instance is a no-instance.
The normalization does not make the construction infeasible: \(a_{\{b\}}=1\), with all other coefficients zero, gives \(d_U=0\) on every question and objective \(r\).
Suppose a cut \(T\subseteq V\) has size \(t\ge k\). Set \(S=\{g\}\cup T\) and take \(a_S=1\), with every other coefficient zero.
Since \(t\ge1\), \(T\ne\emptyset\), so \(|S|\ge2\). The model satisfies normalization and has interaction penalty \(\lambda\). Every question difference belongs to \(\{-1,0\}\), so equality holds in the expected-loss formula. Since \(F(S)=t\),
\[
\text{[replace]}
\]
\(J(a)=r-\frac tC+\lambda=r+\frac{k-\tfrac12-t}{C}\le r-\frac1{2C}=B.\)
We have proved the exact equivalence
\[
\text{[replace]}
\]
\(G\text{ has a cut of size at least }k\quad\Longleftrightarrow\quad\exists a\text{ feasible with }J(a)\le B.\)
The construction has \(m=|V|+2\), \(r=2|V|+2|E|\), \(\tau\le r+1\), and total encoding length polynomial in \(|V|+|E|\). It is computable in polynomial time. This proves \(\mathrm{NP}\)-hardness for both product and minimum features.
Transform any minimum-family instance by replacing every question \((x_q,y_q)\) with \((1-x_q,1-y_q)\), and exchanging \(\succ\) with \(\prec\) in every response type.
For every nonempty \(S\),
\[
\text{[replace]}
\]
\(\max_{i\in S}(1-x_i)=1-\min_{i\in S}x_i.\)
Consequently, for the same coefficient vector,
\[
\text{[replace]}
\]
\(d_q^{\max}(a;1-x_q,1-y_q)=-d_q^{\min}(a;x_q,y_q).\)
Exchanging strict-response directions preserves their losses; indifference losses are also preserved. Feasibility and the interaction penalty remain identical. Thus the transformation preserves \(J(a)\) for every feasible model.
It takes polynomial time and preserves the support size. Applying it to the reduction above proves \(\mathrm{NP}\)-hardness for maximum features. Together with Section 1, all three classifications are \(\mathrm{NP}\)-complete.
Marginal aggregation takes \(O(\tau|Q|)\) rational additions. Explicitly constructing all feature columns takes \(O(2^m m|Q|)\) rational operations. The resulting LP has \(O(2^m+|Q|)\) variables, \(O(|Q|)\) constraints, and rational entries of polynomial encoding length.
Rational LP feasibility is solvable in time polynomial in its explicit encoding length. Therefore all three problems admit an exact deterministic algorithm with running time
\[
\text{[replace]}
\]
\(2^{O(m)}\operatorname{poly}(m,\tau,|Q|,L).\)
For fixed \(m\), this is polynomial time. For variable \(m\), a running time polynomial in \(m,\tau,|Q|,L\) would imply \(\mathrm P=\mathrm{NP}\).
The reported compact dual concerns individual quadratic IRLS subproblems. Its variable count does not provide a polynomial-time algorithm for the exact threshold objective classified here. The paper also identifies the exponential feature dimension in forming the weighted dual matrices. [Herin, Perny, and Sokolovska, Proposition 2 and subsequent discussion](https://www.ijcai.org/proceedings/2023/0421.pdf).
⟨structured verdict parsed — rendered above⟩
The claimed classification is sound in substance: each of the product, minimum, and maximum threshold problems is \(\mathrm{NP}\)-complete. I found no false central step or gap requiring new mathematics. The write-up has minor omissions concerning the reduction’s encoding bound, trivial source instances, and notation.
The argument addresses the specified problem: the society is supplied by its support, features are given implicitly, coefficients may be signed, singleton coefficients are unpenalized, and normalization is the only coefficient constraint.
The case \(r=0\) is handled correctly. A singleton coefficient equal to \(1\) satisfies normalization and incurs no interaction penalty, so its objective is \(0\le B\).
For \(r\ge1\), the marginalization identity is correct. Each loss depends only on the response to its own question, so rearranging the finite sum produces exactly the displayed marginal-weighted objective. No independence assumption about response types is needed.
Computing the marginals requires \(O(\tau r)\) rational additions. Their bit lengths remain polynomial in \(L\), including when input rationals have different denominators. This correctly uses the actual support size \(\tau\).
Both directions of the proposed LP equivalence are valid.
From a feasible model, taking positive and negative coefficient parts gives \(u_S+v_S=|a_S|\). Setting the auxiliary variables to the actual losses satisfies every constraint.
Conversely, nonnegativity and the auxiliary inequalities bound each actual loss by its corresponding auxiliary variable. Since all marginal weights are nonnegative and \(\lambda>0\), the inequality \(|u_S-v_S|\le u_S+v_S\) gives the required objective bound.
Zero marginal weights cause no difficulty: their loss variables still have valid lower bounds, and their objective contributions vanish.
The constraint count is correct:
Thus standard-form conversion yields \(4r+2\) rows. Nonnegativity restrictions do not require additional rows.
The minimum-support argument is valid despite the exponentially many columns.
A feasible standard-form system has finitely many coordinates, so a feasible vector minimizing the number of positive coordinates exists. If its supported columns were dependent, the displayed perturbation would preserve the equalities and nonnegativity while eliminating at least one positive coordinate. Coordinates corresponding to negative components of the dependence vector increase, so they create no feasibility problem.
Therefore the supported columns are independent, and the support has size at most \(4r+2\).
The rationality and bit-length argument also checks out:
Passing from these LP coordinates to the model cannot increase the number of supported subsets. Subsets can be recorded using \(m\) bits each, and exact feature evaluation and objective comparison take \(\operatorname{poly}(m,\tau,r,L)\) time.
Thus membership in \(\mathrm{NP}\) is established for all three families. The argument does not assume that every feasible real model has small rational coefficients; it establishes that every yes-instance has such a certificate.
The stated source theorem applies: unweighted maximum-cut decision on simple undirected graphs is \(\mathrm{NP}\)-complete. The cited paper explicitly establishes the unweighted version. [Garey, Johnson, and Stockmeyer](https://www.sciencedirect.com/science/article/pii/0304397576900591).
Deleting isolated vertices preserves every attainable cut size. The restrictions \(1\le k\le |E|\) exclude only immediately decidable threshold cases.
Minor issue: the fixed yes- and no-instances used for those excluded cases are asserted but not specified. To make the reduction completely explicit, identify them and state their answers. This is a routine omission, not a missing hardness argument.
The questionnaire construction is otherwise valid:
The integer weights cancel in their displayed pairs, giving \(\sum_Uc_U=0\).
For product and minimum features, Boolean inputs give identical feature values.
If \(b\in S\), both feature values vanish because coordinate \(b\) is zero in both alternatives. If \(b\notin S\) and \(S\ne\emptyset\), the baseline feature value is \(1\), and the other feature value is \(1\) exactly when \(S\cap U=\emptyset\). Thus the displayed formula for \(D_{U,S}\) is correct.
The edgewise algebra checks out. Its first expression factors as
\(z_g((1-z_i)+(1-z_j)-2(1-z_i)(1-z_j))\),
which equals \(z_g(z_i+z_j-2z_iz_j)\). For Boolean indicators, the latter parenthesis is precisely the crossing-edge indicator.
Therefore the claimed formula for \(F(S)\) follows. In particular:
These facts establish the crucial protection against arbitrarily large, unpenalized singleton coefficients.
Minor notation issue: \(F(S)\) is introduced for nonempty subsets, but a later sum uses all \(S\). Since \(a_\emptyset=0\), this has no mathematical effect. Restrict that sum to nonempty subsets or explicitly define \(F(\emptyset)\).
Because \(C>\max_U|c_U|\), every \(p_U\) lies strictly between \(0\) and \(1\). Since \(C\) is a power of two, these probabilities and the interval masses satisfy the required rational encoding conditions.
The interval construction realizes the marginals exactly. For any question, the intervals assigned response \(\succ\) are precisely those ending at or before its probability boundary. Their masses telescope to \(p_U\).
Every mass is positive. Adjacent types differ at an internal probability boundary; responses switch in only one direction as the intervals advance, so nonadjacent types cannot repeat either. Thus this is a valid support list, with \(\tau\le r+1\).
The parameters satisfy all domain restrictions: \(\delta=1\), \(\lambda>0\), and \(B\ge0\).
Minor encoding issue: merely requiring \(C\) to be a sufficiently large power of two does not bound its encoding length. The polynomial-time construction claim needs a specified choice rule and a polynomial bound on \(\log C\). This requires only routine clarification.
The expected-loss lower bound is valid for every real \(d\). Each maximum dominates its affine argument, and the probabilities are positive. Equality holds throughout \(-1\le d\le1\), including both endpoints.
Summing this bound produces the stated expression involving \(F(S)\). The subsequent coefficient bound is valid even for signed coefficients: singleton terms vanish, and \(0\le F(S)\le K\) permits the termwise bound by \(|a_S|K\).
For a no-instance, \(K\le k-1\) implies \(\lambda-K/C\ge1/(2C)\). Hence every feasible model has \(J(a)\ge r>B\). The invisible singleton example correctly confirms that normalization itself remains feasible.
For a yes-instance, a cut of size \(t\ge k\ge1\) has a nonempty chosen side, so the selected coefficient belongs to a penalized subset. The model satisfies normalization, its differences lie in \(\{-1,0\}\), and therefore the affine loss calculation is exact. The resulting objective is at most \(B\), including equality when \(t=k\).
The many-one equivalence is consequently established. With the minor encoding clarification above, the constructed questionnaire and support list have polynomial total length.
The complement transformation is correct for every nonempty subset and every input coordinate vector. It negates question differences.
Swapping \(\succ\) and \(\prec\) preserves strict-response losses under this negation, and absolute-value losses are unchanged. Normalization and interaction penalties are identical.
The transformation also preserves support size: swapping response symbols is a bijection on complete response types. Thus maximum-feature hardness follows, and its previously established membership yields \(\mathrm{NP}\)-completeness.
The explicit LP has exponentially many coefficient variables but only \(O(r)\) constraints, with polynomial-size entries. The stated theorem that rational LP feasibility is polynomial in explicit encoding length applies to this system. Therefore the bound \(2^{O(m)}\operatorname{poly}(m,\tau,r,L)\) follows.
Polynomial time for fixed \(m\), and the implication that a polynomial algorithm for variable \(m\) would yield \(\mathrm P=\mathrm{NP}\), are both justified.
The IRLS discussion is appropriately limited. Proposition 2 gives the reported compact subproblem dual, while the subsequent discussion identifies exponential feature dimensions in its matrices. Neither fact supplies an exact polynomial-time algorithm for the full threshold problem. [Herin, Perny, and Sokolovska](https://www.ijcai.org/proceedings/2023/0421.pdf).
The repeated display blocks containing [replace] are unresolved editorial placeholders. The actual formulas appear immediately afterward, so they do not conceal missing mathematics. Remove them.
All identified issues are minor. The reduction and certificate argument establish the claimed classification without requiring additional mathematical ideas.
⟨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.