Answer: polynomial-time solvable
Corollary 1 — class: algorithmic
Given a finite support \(T\) of learner types, rational masses \(\mu_t\) summing to \(1\), and for each type \(t\) a nonempty feasible polyhedron \(G_t=\{w\in\mathbb{R}^n: w\cdot\lambda\ge 1\ \forall\lambda\in\Lambda_t,\; w\cdot\theta\ge 0\ \forall\theta\in\Theta_t\}\), where the complete inputs \(\Lambda_t,\Theta_t\) have rational coordinates, determine which types have exactly one rescale-optimal vector, return that vector for each such type, and compute their total mass \(\rho\). Here \(u\) is rescale-optimal in \(G_t\) if some \(\sigma\in\mathbb{R}_{++}^n\) makes \(u\) minimize \(\|\sigma\odot w\|_2\) over \(w\in G_t\).
A society is given by its support: a list \(T\) of \(\tau\) learner types with positive binary rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau=|T|\) is the support size, not the number of possible types.
Let \(m\ge1\) be the feature dimension. Each type supplies finite, explicitly listed sets \(\Lambda_t,\Theta_t\subseteq\mathbb{Q}^m\), with arbitrary signed coordinates; either set may be empty. Assume \(G_t=\{w\in\mathbb{R}^m:w\cdot\lambda\ge1\ \forall\lambda\in\Lambda_t,\ w\cdot\theta\ge0\ \forall\theta\in\Theta_t\}\) is nonempty.
A vector \(u\in G_t\) is rescale-optimal if some \(\sigma\in\mathbb{R}_{++}^m\) makes it minimize \(\|\sigma\odot w\|_2\) over \(G_t\), where \(\mathbb{R}_{++}^m\) denotes strictly positive coordinates and \(\odot\) is coordinatewise multiplication. Uniqueness means exactly one vector is rescale-optimal across all such rescalings.
Identify every type with this uniqueness property, return its unique vector exactly, and compute \(\rho=\sum_{t:\,G_t\text{ has exactly one rescale-optimal vector}}\mu_t\) exactly. Let \(q=\sum_{t\in T}(|\Lambda_t|+|\Theta_t|)\) and let \(L\) be the total binary input length; state running times in \(m,\tau,q,L\).
Is this identification and exact computation problem solvable in polynomial time in \(m,\tau,q,L\), or is it NP-hard?
For a single learner with finite explicit constraints of this form, determining whether there is exactly one rescale-optimal vector and finding it when it exists are polynomial-time solvable. No separate result for the distribution-valued problem is established by the supplied material.
The problem is polynomial-time solvable in \(m,\tau,q,L\). Each explicitly listed type can be processed independently, and the selected rational masses can then be summed exactly.
We prove an explicit criterion that handles arbitrary signed coordinates and empty constraint sets.
Fix a type and write its nonempty feasible polyhedron as \(G\). For any vector \(a\in\mathbb{R}_{++}^m\), define
\(F_a(w)=\sum_{i=1}^m a_iw_i^2.\)
These are precisely the squared rescaled norms: take \(a_i=\sigma_i^2\). Squaring preserves their minimizers.
Every \(F_a\) has exactly one minimizer over \(G\). Indeed, \(G\) is closed, \(F_a\) is continuous and coercive, and a nonempty sublevel set intersected with \(G\) is compact. Thus a minimizer exists. Strict convexity of \(F_a\), together with convexity of \(G\), makes it unique.
For each coordinate \(i\), consider the linear program
\(\displaystyle \min z\quad\text{subject to }w\in G,\quad z\geq w_i,\quad z\geq-w_i.\)
It has \(m+1\) variables and \(|\Lambda|+|\Theta|+2\) inequalities. It is feasible because \(G\) is nonempty, and its objective is bounded below by zero. Consequently, the standard theorem for rational linear programming guarantees an attained optimum and allows an exact rational optimal solution to be found in polynomial time.
Let \(c_i\) be the \(i\)-th coordinate of an optimal solution. Then
\(\displaystyle |c_i|=\min_{w\in G}|w_i|.\)
Moreover, the signed value \(c_i\) is uniquely determined. To see this, let the minimum absolute value be \(d\). If \(d=0\), every optimal solution has \(w_i=0\). If \(d>0\), two different signed optimal values could only be \(d\) and \(-d\). Feasible vectors attaining these values would have a feasible midpoint with \(i\)-th coordinate zero, contradicting minimality of \(d\).
Define \(c=(c_1,\ldots,c_m)\). The coordinates may have been obtained from different feasible vectors, so feasibility of \(c\) requires a separate check.
Criterion. There is exactly one rescale-optimal vector if and only if \(c\in G\). When this holds, that vector is \(c\).
Suppose \(c\in G\). For every \(w\in G\) and every coordinate \(i\), the definition of \(c_i\) gives \(c_i^2\leq w_i^2\). Therefore, for every \(a\in\mathbb{R}_{++}^m\),
\(\displaystyle F_a(c)=\sum_i a_ic_i^2\leq\sum_i a_iw_i^2=F_a(w).\)
Thus \(c\) minimizes every positive diagonal quadratic objective. Each such objective has a unique minimizer, so \(c\) is the only rescale-optimal vector.
Suppose there is exactly one rescale-optimal vector, denoted \(u\). Since every \(F_a\) has a minimizer, that minimizer must be \(u\) for every \(a\in\mathbb{R}_{++}^m\).
Fix a coordinate \(i\) and any \(w\in G\). For each \(M>0\), choose weights \(a_i=M\) and \(a_j=1\) for \(j\ne i\). Optimality of \(u\) gives
\(\displaystyle M(u_i^2-w_i^2)+\sum_{j\ne i}(u_j^2-w_j^2)\leq0.\)
If \(u_i^2>w_i^2\), the left side would be positive for sufficiently large \(M\). Hence \(u_i^2\leq w_i^2\). This holds for every \(w\in G\), so \(u_i\) attains the minimum absolute value in coordinate \(i\).
By the uniqueness of the signed coordinate minimum proved above, \(u_i=c_i\). Applying this to every coordinate yields \(u=c\), and therefore \(c\in G\). This completes the proof of the criterion.
For every listed type \(t\):
The criterion proves both directions of correctness: every selected type has exactly the returned vector as its rescale-optimal vector, and every omitted type has more than one rescale-optimal vector.
This includes the empty-set cases. For example, if \(\Lambda_t\) is empty, the origin is feasible and uniquely minimizes every positive diagonal quadratic objective.
The feasibility check is substantive when \(m\geq2\). For instance, for \(G=\{w\in\mathbb{R}^2:w_1+w_2\geq1\}\), both coordinate minimum absolute values are zero, but their assembled vector is infeasible. Thus this type fails uniqueness.
Let \(q_t=|\Lambda_t|+|\Theta_t|\). The algorithm uses exactly \(m\tau\) rational linear programs, each with \(m+1\) variables and \(q_t+2\) inequalities, followed by checks of all \(q\) original inequalities.
Each linear program has encoding length \(\mathrm{O}(L+m)\). The polynomial-time theorem for exact rational linear programming also guarantees polynomial output length. Consequently, the returned coordinates have polynomial bit length, and checking all inequalities by rational arithmetic takes polynomial time.
For the mass calculation, write each input mass as \(\mu_t=A_t/B_t\), with positive integer numerator and denominator, and set
\(\displaystyle D=\prod_{t\in T}B_t,\qquad N=\sum_{\text{selected }t}A_t(D/B_t).\)
Then the exact answer is \(\rho=N/D\), which may be reduced by computing a greatest common divisor. The binary length of \(D\) is at most one plus the sum of the denominator lengths, hence \(\mathrm{O}(L)\). Since the masses are positive and sum to one, \(0\leq N\leq D\), so \(N\) also has \(\mathrm{O}(L)\) bits. Thus exact summation and reduction take polynomial time; for example, schoolbook arithmetic gives the conservative bound \(\mathrm{O}(\tau L^2+L^3)\).
Combining these bounds, there is a fixed polynomial \(P\) such that the entire computation takes
\(\displaystyle \mathrm{O}\!\left(\tau m\,P(m+q+L)\right)\)
bit operations, including exact output construction and mass summation.
The support is explicitly listed, so only its \(\tau\) members are processed. No enumeration of other possible learner types is needed.
⟨structured verdict parsed — rendered above⟩
The prover’s output resolves the task correctly. The single-type criterion is rigorous, the algorithm handles signed coordinates and empty constraint sets, and processing the explicitly listed support gives a polynomial-time algorithm for identification, exact vector output, and exact mass computation. No major or minor issues were found.
The feasible set \(G\) is nonempty by assumption and is closed and convex because it is an intersection of finitely many closed halfspaces. For strictly positive weights \(a_i\), the objective \(F_a(w)=\sum_i a_iw_i^2\) is continuous, coercive, and strictly convex. The compact-sublevel argument therefore establishes existence, and strict convexity on the convex feasible set establishes uniqueness.
The correspondence \(a_i=\sigma_i^2\) covers exactly all strictly positive weight vectors. Squaring the nonnegative norm preserves its minimizers. Thus these objectives correctly represent all rescalings in the task.
The auxiliary inequalities enforce \(z\geq |w_i|\). Minimizing \(z\) consequently computes the minimum feasible absolute value of coordinate \(i\).
The stated rational linear programming theorem applies: each program has rational data, is feasible because \(G\) is nonempty, and has objective bounded below by zero. Its finite optimum is attained, and an exact rational optimal solution of polynomial encoding length can be obtained in polynomial time. Unboundedness of the feasible region does not invalidate this application.
The signed-value argument is correct. When the minimum absolute value is zero, the coordinate must be zero. When it is positive, different signed optimal values would be opposite values; convexity would then produce a feasible midpoint with zero in that coordinate, contradicting minimality. Thus \(c_i\) is independent of the chosen optimal solution.
The prover correctly distinguishes the individual coordinate values from the assembled vector: the latter need not be feasible.
If \(c\in G\), each coordinate satisfies \(c_i^2\leq w_i^2\) for every feasible \(w\). Multiplication by positive weights and summation establish that \(c\) minimizes every \(F_a\).
Since each objective has exactly one minimizer, every rescale-optimal vector must equal \(c\). This establishes both uniqueness and the claimed exact vector.
If there is exactly one rescale-optimal vector \(u\), existence of a minimizer for every \(F_a\) implies that every such minimizer equals \(u\). This quantifier step is justified by the definition of rescale-optimality.
For a fixed coordinate \(i\) and fixed feasible vector \(w\), the displayed inequality holds for every \(M>0\). The sum over the other coordinates is a finite constant independent of \(M\). If \(u_i^2>w_i^2\), the inequality fails for sufficiently large \(M\). Therefore \(u_i^2\leq w_i^2\) for every feasible \(w\).
Hence \(u_i\) attains the coordinate minimum absolute value. The previously proved uniqueness of its signed value gives \(u_i=c_i\) for every coordinate. Consequently \(u=c\in G\). There is no missing limiting or attainment argument here.
The exact feasibility check implements the criterion in both directions. A rejected type cannot have exactly one rescale-optimal vector; because at least one exists, it must have more than one.
Empty constraint sets cause no difficulty. When \(\Lambda_t\) is empty, the origin satisfies every homogeneous constraint, including when \(\Theta_t\) is also empty, and uniquely minimizes every positive diagonal quadratic objective. The argument also covers \(m=1\) and arbitrary signed rational constraint coordinates.
The example \(w_1+w_2\geq1\) correctly demonstrates that individually attainable coordinate minima need not assemble into a feasible vector.
The count of \(m\tau\) linear programs is correct. Each has \(m+1\) variables and \(q_t+2\) inequalities. The stated encoding bound accounts for the original rational constraints and the added auxiliary variable and inequalities. Polynomial-time exact rational linear programming supplies polynomial-length coordinates, so evaluating all original inequalities exactly takes polynomial time.
The common-denominator computation is valid: every \(D/B_t\) is an integer, and \(N/D\) equals the selected mass sum. The product denominator has \(\mathrm{O}(L)\) bits. Positivity and normalization of the masses imply \(0\leq N\leq D\), including the cases where no types or all types are selected. The claimed conservative schoolbook-arithmetic bound is sufficient.
The final bound \(\mathrm{O}(\tau m\,P(m+q+L))\), for some fixed polynomial \(P\), can include feasibility checks, exact output construction, and mass summation. The explicitly listed support requires no enumeration of unlisted possible types.
No additional clarification is needed to make the argument verifiable.
⟨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.