Answer: Deciding whether the optimum is at most \(q\) is \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions, already for \(m=2\) and \(\tau=1\). Exact value computation and finding a minimizing recommendation are NP-hard. For fixed \(p\), the problem is polynomial-time solvable. The threshold problem is NP-hard under Turing reductions, and under many-one reductions if and only if \(\mathrm{NP}=\mathrm{coNP}\).
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet E = Ext(W1 Λ), and for v ∈E, let sv = minσ∈R v· σ, and let E′ be the set { v sv : v ∈E}. Then MR(α, A; V) is equal to maxσ∈R MRσ(α, A; W1 Λ) = MR(α, A; E′) = maxw∈E′ DA w(α) = maxv∈E DA v (α) sv .
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set \(A\) of rational objective vectors and a finite support of user-profile types \(t\), each with rational mass \(\mu_t\), consistent preference constraints \(\Lambda_t\), and a compact rational rescaling range \(R_t\subset\mathbb{R}^p_{>0}\), compute a recommendation \(a_t\in A\) for each type minimizing \(\sum_t\mu_t\max_{\sigma\in R_t}\mathrm{MR}(H_\sigma(a_t),H_\sigma(A);W^1_{H_\sigma(\Lambda_t)})\).
Let \(p\geq1\) and let \(A\subset\mathbb{Q}^p\) be a nonempty explicitly listed set of \(m\) alternatives; objective values may have either sign, and larger values are preferred.
A society is given by its support: a list of \(\tau\geq1\) profile types with positive binary rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has a finite explicitly listed set \(\Lambda_t\subset\mathbb{Q}^p\) of weak preference constraints. Define \(W^1_\Lambda=\{w\in\mathbb{R}^p_{\geq0}:\sum_iw_i=1,\ w\cdot\lambda\geq0\text{ for every }\lambda\in\Lambda\}\), and require \(W^1_{\Lambda_t}\neq\varnothing\).
Each type also has a nonempty compact rational polytope \(R_t\subset\mathbb{R}^p_{>0}\), given by an explicit list of rational linear inequalities; no additional normalization of rescalings is imposed.
Define \(H_\sigma(x)_i=x_i/\sigma_i\), extending this map elementwise to sets, and \(\mathrm{MR}(a,B;W)=\max_{b\in B}\max_{w\in W}w\cdot(b-a)\).
Choose one deterministic recommendation \(a_t\in A\) per type to minimize \(F((a_t)_t)=\sum_t\mu_t\max_{\sigma\in R_t}\mathrm{MR}(H_\sigma(a_t),H_\sigma(A);W^1_{H_\sigma(\Lambda_t)})\). Any minimizing recommendation is allowed when there are ties.
Is this exact optimization problem solvable in polynomial time, or is deciding whether its optimum is at most an input rational threshold \(q\) NP-hard? State running times in \(m,\tau,p,L\), where \(L\) is the total binary input length, including constraints, rescaling inequalities, masses, and \(q\).
For one profile, worst-case regret over rescalings can be computed using the explicitly enumerated extreme points of the normalized preference polytope and one linear minimization per extreme point; the number of extreme points need not be polynomial in the constraint input. [Source](https://doi.org/10.3233/FAIA230571).
No complexity classification for this distribution-of-types problem was verified.
For inputs satisfying the stated hypotheses, deciding whether the optimum is at most \(q\) is \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions, already for \(m=2\) and \(\tau=1\).
Consequently:
For every fixed \(p\), there is an exact algorithm polynomial in \(m,\tau,L\). Explicit running-time bounds appear below.
The degenerate cases \(m=1\) and \(p=1\) have optimum zero. The hardness result concerns variable \(p\), while keeping both \(m\) and \(\tau\) constant.
Write \(P_t=W^1_{\Lambda_t}\), and define the robust regret of alternative \(a\) for type \(t\) by
\( \displaystyle g_t(a)=\max_{\sigma\in R_t}\mathrm{MR}\bigl(H_\sigma(a),H_\sigma(A);W^1_{H_\sigma(\Lambda_t)}\bigr). \)
For any strictly positive \(\sigma\), the map
\( \displaystyle v\longmapsto u,\qquad u_i=\frac{\sigma_i v_i}{\sigma\cdot v} \)
is a bijection from \(P_t\) onto \(W^1_{H_\sigma(\Lambda_t)}\). Indeed, \(u\) is nonnegative, sums to one, and satisfies
\( \displaystyle u\cdot H_\sigma(\lambda)=\frac{v\cdot\lambda}{\sigma\cdot v}\geq0. \)
Conversely, normalize the vector with coordinates \(u_i/\sigma_i\) to recover \(v\in P_t\). The utility difference becomes
\( \displaystyle u\cdot\bigl(H_\sigma(b)-H_\sigma(a)\bigr)=\frac{v\cdot(b-a)}{\sigma\cdot v}. \)
Therefore,
\[ \displaystyle g_t(a)=\max_{\sigma\in R_t}\max_{v\in P_t}\max_{b\in A}\frac{v\cdot(b-a)}{\sigma\cdot v}. \tag{1} \]
These maxima exist. The set \(P_t\) is nonempty and compact, and compactness of \(R_t\subset\mathbb R^p_{>0}\) gives a positive lower bound on every denominator in (1).
Let \(E_t\) denote the vertices of \(P_t\), and put
\( \displaystyle r_a(v)=\max_{b\in A}v\cdot(b-a),\qquad h_t(v)=\min_{\sigma\in R_t}\sigma\cdot v. \)
Here \(r_a(v)\geq0\), because \(b=a\) is allowed, and \(h_t(v)>0\).
To reduce (1) to vertices, fix \(\sigma\) and write \(v=\sum_j\alpha_jv^j\), where \(v^j\in E_t\), \(\alpha_j\geq0\), and \(\sum_j\alpha_j=1\). For each \(b\),
\( \displaystyle \frac{v\cdot(b-a)}{\sigma\cdot v} =\sum_j\frac{\alpha_j\,\sigma\cdot v^j}{\sigma\cdot v}\, \frac{v^j\cdot(b-a)}{\sigma\cdot v^j}. \)
The coefficients are nonnegative and sum to one. Thus this ratio cannot exceed its largest value at a vertex. Since \(E_t\) is finite, maximizing over \(\sigma\) now gives
\[ \displaystyle \boxed{g_t(a)=\max_{v\in E_t}\frac{r_a(v)}{h_t(v)}.} \tag{2} \]
This independently derives the extreme-point formula in Theorem 3 of [Wilson’s cited paper](https://journals.sagepub.com/doi/pdf/10.3233/FAIA230571). Its hypotheses hold here: the preference polytope is nonempty, the rescalings are strictly positive, and their range is compact.
Finally, there is no constraint coupling recommendations for different types. Hence
\[ \displaystyle \boxed{\operatorname{OPT}=\sum_{t=1}^{\tau}\mu_t\min_{a\in A}g_t(a).} \tag{3} \]
To verify equality, every recommendation tuple has objective at least the right-hand side; choosing a minimizing alternative separately for each type attains it.
Let \(\ell_t=|\Lambda_t|\) and \(N_t=p+\ell_t\). These count the inequalities describing \(P_t\), including nonnegativity.
Every vertex of \(P_t\) is the unique solution of the normalization equation together with \(p-1\) linearly independent active inequalities. This remains true when \(P_t\) has lower affine dimension: at a vertex, the normalization equation and active inequality normals must jointly have rank \(p\). Otherwise a nonzero direction preserving all those equalities would permit a sufficiently small feasible displacement in both directions, contradicting extremality.
Thus all vertices can be found by inspecting at most
\( \displaystyle K_t=\binom{N_t}{p-1} \)
subsets, solving the corresponding rational systems, and checking feasibility.
For each vertex \(v\):
The scores require \(O(mp)\) rational arithmetic operations per vertex, rather than a separate comparison of every ordered pair of alternatives.
All vertex coordinates and LP optima have polynomial binary length in \(p,L\). For example, after clearing denominators, Cramer’s rule expresses vertex coordinates as ratios of determinants; the bound \(p!H^p\) for a determinant with entries of magnitude at most \(H\) gives polynomial bit length. Exact rational LP and the arithmetic used above therefore take polynomial time per vertex.
If the vertices are already explicitly supplied, the running time is
\( \displaystyle O\!\left((1+mp)\sum_{t=1}^{\tau}|E_t|\,\operatorname{poly}(p,L)\right). \)
From the specified inequality input, a valid bound is
\[ \displaystyle O\!\left((1+mp)\sum_{t=1}^{\tau}\binom{p+\ell_t}{p-1}\operatorname{poly}(p,L)\right). \tag{4} \]
In particular, a coarser bound in the requested parameters is
\( \displaystyle O\!\left(\tau(1+mp)(L+p)^{p-1}\operatorname{poly}(p,L)\right). \)
This is polynomial for every fixed \(p\), but not a polynomial bound when \(p\) varies.
We give a polynomial-size certificate for the complementary condition \(\operatorname{OPT}>q\).
For every type \(t\) and every alternative \(a\), provide rational vectors \(v_{t,a}\in P_t\), \(\sigma_{t,a}\in R_t\), and an alternative \(b_{t,a}\in A\). Define
\( \displaystyle d_{t,a}=\frac{v_{t,a}\cdot(b_{t,a}-a)}{\sigma_{t,a}\cdot v_{t,a}}. \)
The verifier checks feasibility and checks
\[ \displaystyle \sum_{t=1}^{\tau}\mu_t\min_{a\in A}d_{t,a}>q. \tag{5} \]
By (1), \(d_{t,a}\leq g_t(a)\). Thus (5) implies \(\operatorname{OPT}>q\).
Conversely, suppose \(\operatorname{OPT}>q\). Formula (2) allows each \(g_t(a)\) to be attained at a vertex \(v\) of \(P_t\), an alternative attaining \(r_a(v)\), and a vertex of \(R_t\) minimizing \(\sigma\cdot v\). If the regret is zero, simply choose \(b=a\).
Vertices of both rational polytopes have polynomial binary length by the determinant argument above. Consequently, these \(m\tau\) witnesses form a polynomial-size certificate with \(d_{t,a}=g_t(a)\), so (5) holds.
Verification uses rational arithmetic and the explicitly listed inequalities, in time polynomial in \(m,\tau,p,L\). Therefore the threshold problem belongs to \(\mathrm{coNP}\).
We now prove hardness with one type and two alternatives. We use the NP-completeness of unweighted simple MAX-CUT, established by [Garey, Johnson, and Stockmeyer](https://doi.org/10.1016/0304-3975%2876%2990059-1).
Let \(G\) have vertices \(1,\ldots,n\), edge set \(E\), and \(s=|E|\). Write \(C^*(G)\) for its maximum cut size. Orient each edge from its smaller to its larger endpoint, and set
\( \displaystyle M=s+1,\qquad B=2s+2. \)
For \(x,y\in[0,1]^n\), define
\( \displaystyle C_{\times}(x,y)=\sum_{\{i,j\}\in E,\ i<j}(x_i+y_j-2x_i y_j) \)
and
\( \displaystyle f(x,y)=-C_{\times}(x,y)+M\sum_{i=1}^{n}(x_i+y_i-2x_i y_i). \)
We claim
\[ \displaystyle \boxed{\min_{x,y\in[0,1]^n}f(x,y)=-C^*(G).} \tag{6} \]
First, the minimum is attained at binary \(x,y\). For fixed \(y\), the function is affine in \(x\), so an endpoint can be chosen for each coordinate without increasing its value. After that, for fixed binary \(x\), the same argument makes \(y\) binary without increasing the value.
For binary \(x,y\), each summand in \(C_{\times}\) is either zero or one, so \(0\leq C_{\times}(x,y)\leq s\). Also,
\( \displaystyle \sum_i(x_i+y_i-2x_i y_i)=|\{i:x_i\neq y_i\}|. \)
If \(x\neq y\), then \(f(x,y)\geq M-s=1\). If \(x=y\), the penalty vanishes and \(C_{\times}(x,x)\) is exactly the cut size represented by \(x\). Thus the best diagonal value is \(-C^*(G)\), while every off-diagonal binary value is positive. This proves (6).
For later use, write
\( \displaystyle f(x,y)=c(y)+\sum_i x_i\alpha_i(y), \)
where
\( \displaystyle c(y)=M\sum_i y_i-\sum_{\{i,j\}\in E,\ i<j}y_j \)
and
\[ \displaystyle \alpha_i(y)=M(1-2y_i)-\sum_{\{i,j\}\in E,\ i<j}(1-2y_j). \tag{7} \]
Expanding these expressions gives precisely the preceding definition of \(f\).
Use \(p=3n+1\) coordinates, labeled \(i^+,i^-\), \(z\), and \(r_i\), for \(1\leq i\leq n\).
The preference polytope consists of nonnegative normalized vectors satisfying
\[ \displaystyle v_{r_i}=0,\qquad n(v_{i^+}+v_{i^-})+v_z=1\quad(1\leq i\leq n). \tag{8} \]
These equations have the required homogeneous preference-constraint representation. Include \(-e_{r_i}\) in \(\Lambda\), and include both signs of
\( \displaystyle \lambda_i=n(e_{i^+}+e_{i^-})+e_z-\mathbf1. \)
Nonnegativity forces \(v_{r_i}=0\); normalization converts \(v\cdot\lambda_i=0\) into (8).
Define \(v(x)\), for \(x\in[0,1]^n\), by
\( \displaystyle v(x)_{i^+}=\frac{x_i}{n},\qquad v(x)_{i^-}=\frac{1-x_i}{n},\qquad v(x)_z=v(x)_{r_i}=0. \)
The resulting polytope is
\[ \displaystyle P=\operatorname{conv}\bigl(\{v(x):x\in[0,1]^n\}\cup\{e_z\}\bigr). \tag{9} \]
Indeed, if \(v_z<1\), put \(x_i=nv_{i^+}/(1-v_z)\). Equation (8) ensures \(x_i\in[0,1]\) and \(v=(1-v_z)v(x)+v_z e_z\). If \(v_z=1\), then \(v=e_z\). In particular, the preference polytope is nonempty.
Specify \(R\) through the following linear constraints. Define \(y_i=\sigma_{r_i}-1\), and require
\( \displaystyle 1\leq\sigma_{r_i}\leq2,\qquad \sigma_z=1, \)
\[ \displaystyle \sigma_{i^-}=B+\frac{c(y)}{n},\qquad \sigma_{i^+}=B+\frac{c(y)}{n}+\alpha_i(y). \tag{10} \]
All equalities are encoded by two inequalities. Since \(c\) and \(\alpha_i\) are affine, (10) is an explicit rational linear description.
The coordinates \(y\) range over exactly \([0,1]^n\), and all other coordinates are specified affine functions of \(y\). Hence \(R\) is nonempty and compact.
It is also strictly positive. The coefficient of \(y_i\) in \(c(y)\) is \(M\) minus the number of incoming edges at \(i\), so \(c(y)\geq0\). Moreover,
\( \displaystyle \alpha_i(y)\geq-M-s. \)
Consequently,
\( \displaystyle \sigma_{i^-}\geq B>0,\qquad \sigma_{i^+}\geq B-M-s=1, \)
and the remaining coordinates are at least one.
By (7) and (10),
\( \displaystyle v(x)\cdot\sigma(y) =\frac1n\sum_i\bigl(x_i\sigma_{i^+}+(1-x_i)\sigma_{i^-}\bigr) =B+\frac{f(x,y)}n. \)
Together with (6), this proves
\[ \displaystyle \boxed{\min_{x,y\in[0,1]^n}v(x)\cdot\sigma(y) =B-\frac{C^*(G)}n.} \tag{11} \]
For a positive rational \(K\), take \(A=\{a^0,a^1\}\), where \(a^0=0\) and
\( \displaystyle a^1_{i^+}=a^1_{i^-}=B,\qquad a^1_z=-K,\qquad a^1_{r_i}=0. \)
Use one type, with mass one and the polytopes just constructed.
On the cube face, \(v(x)\cdot a^1=B\); at the apex, \(e_z\cdot a^1=-K\). A fractional linear function on the convex hull (9) cannot exceed its maximum on the generating sets, by the weighted-average argument in Section 1. Thus (1) and (11) give
\[ \displaystyle g(a^0)=\frac{B}{B-C^*(G)/n}=:h_G,\qquad g(a^1)=K. \tag{12} \]
For the second equality, the regret numerator against \(a^0\) is negative on the cube face and equals \(K\) at the apex; the apex denominator is \(\sigma_z=1\).
Since \(0\leq C^*(G)\leq s\) and \(B=2s+2\),
\[ \displaystyle 1\leq h_G\leq\frac{B}{B-s/n}<2. \tag{13} \]
The construction has \(p=3n+1\), polynomially many explicitly listed rational coefficients, and polynomial binary length.
Take a nontrivial MAX-CUT threshold \(k\), with \(1\leq k\leq s\), and set \(K=2\). By (12)–(13), the optimum is \(h_G\).
Choose the rational threshold
\( \displaystyle q_k=\frac{B}{B-(k-\tfrac12)/n}. \)
Its denominator is positive, and its binary length is polynomial. The function \(c\mapsto B/(B-c/n)\) is strictly increasing throughout the relevant interval. Because cut sizes are integers,
\( \displaystyle \operatorname{OPT}\leq q_k \quad\Longleftrightarrow\quad C^*(G)\leq k-1 \quad\Longleftrightarrow\quad\text{there is no cut of size at least }k. \)
This is a polynomial-time many-one reduction from the complement of MAX-CUT. The restrictions \(1\leq k\leq s\) discard only trivially decidable instances.
Therefore the threshold problem is coNP-hard. Section 3 proves membership, so it is \(\mathrm{coNP}\)-complete, already for \(m=2,\tau=1\).
A polynomial-time threshold algorithm would decide MAX-CUT by negating its answer. Hence such an algorithm exists only if \(\mathrm{P}=\mathrm{NP}\).
The preceding value reduction always recommends \(a^0\), so it alone would not establish hardness of returning a recommendation. To establish that separate claim, use the same construction with \(K=q_k\).
Equation (12) now gives \(g(a^0)=h_G\) and \(g(a^1)=q_k\). Integer cut sizes and the half-integer threshold exclude ties:
Thus one call to an algorithm returning any minimizing recommendation decides MAX-CUT. The allowance for arbitrary tie-breaking does not affect this reduction.
Since the threshold problem belongs to \(\mathrm{coNP}\), NP-hardness under many-one reductions would imply \(\mathrm{NP}\subseteq\mathrm{coNP}\), and hence \(\mathrm{NP}=\mathrm{coNP}\). Conversely, if these classes coincide, its coNP-completeness makes it NP-hard.
The fully proved classification is therefore: coNP-complete threshold decision; NP-hard exact value computation and exact recommendation; polynomial-time solvable for every fixed \(p\), with running time (4).
⟨structured verdict parsed — rendered above⟩
The output resolves the task. The rescaling identity, exact algorithm, complement certificate, and hardness reductions are correct. I found no major or minor mathematical issues.
The distinction between coNP-completeness and NP-hardness is essential here: the prover correctly establishes coNP-completeness under many-one reductions for the threshold direction requested, and NP-hardness under Turing reductions. It separately establishes hardness of returning a minimizing recommendation.
The bijection is correct. The denominator \(\sigma\cdot v\) is positive because \(\sigma\) is strictly positive and \(v\) is nonnegative with coordinate sum one. The displayed calculation verifies all transformed preference constraints. The stated inverse recovers a normalized feasible vector and reverses the transformation.
Equation (1) follows correctly. The utility-difference identity accounts for the simultaneous transformation of alternatives and preference constraints. It imposes no sign restriction on alternative coordinates.
Existence of the maxima is justified. The preference polytope is closed and contained in the simplex. Compactness and strict positivity of the rescaling polytope provide a uniform positive denominator bound. Thus each ratio is continuous on the relevant compact product.
The vertex reduction is valid. The displayed coefficients are nonnegative and sum to one, so the ratio at any convex combination is bounded by its largest vertex ratio. This argument remains valid when the numerator is negative.
Equation (2) correctly uses nonnegativity of regret. After maximizing over alternatives, the numerator \(r_a(v)\) is nonnegative because the recommended alternative itself is available. Consequently, maximizing over rescalings amounts to minimizing the positive denominator. This also handles zero regret correctly.
The attribution to Wilson’s Theorem 3 is accurate: the cited theorem gives the same extreme-point formula with one linear denominator minimization per extreme point. The prover also supplies an independent derivation, so this citation is not an unsupported dependency. [Wilson’s paper](https://journals.sagepub.com/doi/pdf/10.3233/FAIA230571).
Equation (3) is correct. Recommendations have no constraints coupling different types, and every finite set of alternative regrets has a minimum. The two inequalities needed for equality are explicitly supplied.
The vertex enumeration argument handles lower-dimensional polytopes correctly. At a vertex, the normalization equation and active constraint normals must jointly have full rank. Otherwise, a sufficiently small displacement in both directions preserves the active constraints and remains feasible for the inactive constraints, contradicting extremality.
Thus enumeration of the stated subsets finds every vertex. Singular systems and infeasible solutions can be discarded. Duplicate discoveries do not affect correctness or the stated upper bound.
The work per candidate is correctly bounded.
The binary-length argument is sufficient. Clearing denominators and using determinant bounds gives polynomial-length coordinates for rational vertices. Linear objectives over the rescaling polytope attain their minima at vertices, so their optimal values likewise have polynomial binary length. The divisions, comparisons, and mass-weighted sum therefore remain exact with polynomial-length rational representations.
The bound
\[
O\!\left((1+mp)\sum_{t=1}^{\tau}
\binom{p+\ell_t}{p-1}\operatorname{poly}(p,L)\right)
\]
correctly includes enumeration and the processing of feasible candidates. The coarser bound in the requested parameters is also valid.
For fixed \(p\), these bounds are polynomial in \(m,\tau,L\). They do not claim polynomial running time for variable \(p\).
Certificate soundness is correct. Every feasible witness satisfies \(d_{t,a}\leq g_t(a)\). Taking minima over alternatives preserves that inequality, and summing with positive masses preserves it again. Hence condition (5) implies \(\operatorname{OPT}>q\).
Certificate completeness is correct. Equation (2) supplies an attaining preference vertex for every type–alternative pair. An alternative attaining the numerator exists because the alternative set is finite. A minimizing rescaling vertex exists because the rescaling set is a nonempty compact polytope. When regret is zero, choosing \(b=a\) gives an attaining zero witness.
The certificate has polynomial size. Both classes of vertices have polynomial-length rational coordinates, and there are \(m\tau\) witnesses. Feasibility and the strict rational comparison can be checked in polynomial time.
This establishes membership of the requested threshold problem in coNP, including negative thresholds and zero-regret cases.
The source problem is appropriate: the cited paper establishes NP-completeness of unweighted Simple MAX-CUT. The reduction uses precisely an unweighted simple graph and an integer cut threshold. [Garey, Johnson, and Stockmeyer](https://doi.org/10.1016/0304-3975%2876%2990059-1).
Equation (6) is correct. Successive endpoint choices for the two affine blocks show that a minimum is attained at a binary pair.
For binary pairs, the cross-edge contribution lies between zero and \(s\), and the penalty counts unequal coordinates. With \(M=s+1\), every off-diagonal binary pair has value at least one. Diagonal pairs have value equal to the negative cut size. This proves the claimed minimum.
Equation (7) expands correctly. The constant term collects the terms involving only \(y\), and each coefficient of \(x_i\) matches the oriented edge contributions and the equality penalty.
The homogeneous constraint encoding is valid. Nonnegativity together with \(-e_{r_i}\) forces each auxiliary preference coordinate to zero. Both signs of \(\lambda_i\), together with normalization, impose exactly equation (8).
Equation (9) describes the complete feasible set. For \(v_z<1\), the stated coordinates \(x_i\) lie in the unit interval and recover the proposed convex combination. At \(v_z=1\), nonnegativity and normalization leave only the apex. No additional feasible preference vectors are omitted.
The description uses allowed input constraints. The functions \(c\) and \(\alpha_i\) are affine, so all equalities in (10) are rational linear constraints and can be encoded by paired inequalities.
Nonemptiness and compactness are established. The auxiliary coordinates parameterize the entire cube, and all remaining coordinates are uniquely specified affine functions of them.
Strict positivity is correctly checked. Each coefficient in \(c\) is nonnegative. The lower bound on \(\alpha_i\) gives
\[
B-M-s=1.
\]
Thus every coordinate is strictly positive, as required by the task.
Equation (11) is correct. Substituting (10) into the dot product gives \(B+f(x,y)/n\), and equation (6) then gives the stated joint minimum.
Both identities in equation (12) are correct. On the cube face, the numerator against \(a^0\) is the positive constant \(B\); at the apex it is negative. Conversely, the numerator against \(a^1\) is negative on the cube face and equals \(K\) at the apex, whose denominator is one.
The previously established weighted-average argument excludes a larger ratio at a mixture of these sets.
Equation (13) has the correct constants and strict inequality. The denominator remains positive, and \(B=2s+2\) ensures the upper bound is strictly below two.
The dimension, number of constraints, and coefficient lengths are polynomial in the source instance size. The construction satisfies every input requirement.
The threshold reduction has the correct direction. With \(K=2\), equation (13) makes \(a^0\) the unique minimizing alternative. The function defining \(h_G\) is strictly increasing in the cut size. The half-integer threshold therefore gives exactly the stated equivalence with the complement of MAX-CUT.
Restricting to \(1\leq k\leq s\) removes only directly decidable cases and does not undermine hardness. Together with Section 3, this proves coNP-completeness.
The recommendation reduction establishes a separate result. Setting \(K=q_k\) changes the second alternative’s regret to the separating threshold. Integer cut sizes exclude ties, and the unique recommendation distinguishes the two MAX-CUT outcomes. Thus the task’s allowance for arbitrary minimizing recommendations does not weaken this reduction.
The complexity-class implications are correct. An exact optimum permits threshold comparison. A threshold oracle decides MAX-CUT by complementing its answer. Many-one NP-hardness of a language in coNP would imply equality of NP and coNP; conversely, their equality would make this coNP-complete language NP-hard.
The stated zero optima for \(m=1\) and \(p=1\) are correct and consistent with the variable-dimension hardness construction.
No additional mathematical clarification 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.