Answer: polynomial-time solvable
Proposition 5 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet xi ∈V of type tj. (1) Algorithm 2 computes Δi IC∗(K∗) in O(nj|V|) time. (2) There exists a formula φ of L such that Si(φ) = Δi IC∗(K∗). We omit the proof of this proposition for space reasons.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given typed real variables with axis-aligned domains and Manhattan metrics, \(\tau\) source types represented by \(I\)-consistent cube bases \(K_t\) with rational bounds, a nonempty cube integrity constraint \(IC^*\), and positive rational masses \(\mu_t\) summing to \(1\), compute the exact set \(\operatorname*{arg\,min}_{\omega\in\overline{\operatorname{Mod}_I(IC^*)}} \sum_{t=1}^{\tau}\mu_t\inf_{\eta\models_I K_t} d(\omega,\eta)\), represented as a formula or as a product of coordinate intervals.
There are \(m\) real coordinates, possibly grouped into typed vector variables. Each variable's domain is a nonempty closed axis-aligned cuboid, possibly unbounded; all finite bounds are binary rationals. Let \(W\) be the product of these domains, equipped with the Manhattan metric \(d\).
A cube is a conjunction of coordinate inequalities with rational thresholds, each strict or weak. Satisfaction is evaluated within \(W\); write \(\operatorname{Mod}_I(K)\) for the satisfying assignments. Each source cube \(K_t\) and the integrity cube \(IC^*\) must have nonempty model sets.
A society is given by its support: the list of the \(\tau\) source types with positive binary-rational masses \(\mu_t\), where \(\sum_{t=1}^{\tau}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; a source type specifies its cube \(K_t\).
Compute the exact set \(A=\operatorname*{arg\,min}_{\omega\in\overline{\operatorname{Mod}_I(IC^*)}}\sum_{t=1}^{\tau}\mu_t\inf_{\eta\in\operatorname{Mod}_I(K_t)}d(\omega,\eta)\), with closure taken in \(W\), represented as a formula of coordinate inequalities or a Cartesian product of intervals. Let \(L\) be the total binary input length, including all bounds, inequalities, and masses.
Is exact computation of \(A\) possible in polynomial time in \(m,\tau,L\), or is this problem NP-hard?
For a finite multiset of equally weighted cube sources, a polynomial-time algorithm computing the entire minimizing set and expressing it by a formula is established in the [finite-profile result](https://www.cril.univ-artois.fr/~marquis/condotta-kaci-marquis-schwind-ecai10.pdf). Its assignments already range over real spaces. No result for exactly the binary-rational mass formulation was located in the search.
The entire minimizing set \(A\) can be computed exactly in polynomial time in \(m,\tau,L\). It is a nonempty Cartesian product of closed, possibly unbounded intervals. Every finite endpoint in the output is an endpoint selected from the input bounds or thresholds.
The coordinate decomposition also appears in Section 4 of the cited [finite-profile result](https://www.cril.univ-artois.fr/~marquis/condotta-kaci-marquis-schwind-ecai10.pdf). The proof below handles binary-rational masses directly and establishes polynomial bit complexity.
Flatten the typed vector variables into coordinates \(x_1,\ldots,x_m\). Because all domains are axis-aligned cuboids, write \(W=\prod_{j=1}^m W_j\), where each \(W_j\) is a nonempty closed interval, possibly unbounded.
Each cube contains only inequalities on individual coordinates. Consequently, for every source \(t\),
\( \operatorname{Mod}_I(K_t)=\prod_{j=1}^m S_{tj}, \)
where \(S_{tj}\) is the intersection of \(W_j\) with the inequalities of \(K_t\) on coordinate \(j\). The promised nonemptiness of the source model set implies that every \(S_{tj}\) is a nonempty interval.
Let \(a_{tj}\) be its greatest lower bound and \(b_{tj}\) its least upper bound, using infinite endpoints when appropriate. Then
\( B_{tj}:=\overline{S_{tj}}=[a_{tj},b_{tj}]. \)
Throughout, an interval with an infinite endpoint denotes a subset of the real line; infinity is not an element of the interval.
These endpoints are obtained by taking the maximum of all lower bounds and the minimum of all upper bounds, including domain bounds. Strict inequalities affect endpoint inclusion in \(S_{tj}\), but not its closure. Nonemptiness is essential here: it ensures that the resulting closed interval is precisely the closure.
Likewise, write
\( C:=\overline{\operatorname{Mod}_I(IC^*)}=\prod_{j=1}^m C_j,\qquad C_j=[c_j,d_j]. \)
These are closures in \(W\). Since \(W\) is closed in real coordinate space, they agree with ambient closures. Closure commutes with these finite products: coordinatewise convergent sequences prove that every point of the product of the coordinate closures lies in the closure of the original product, and continuity of coordinate projections proves the reverse inclusion.
Thus normalization requires only rational comparisons, and every finite normalized endpoint comes from the input.
For a nonempty closed interval \(B=[a,b]\), define its distance function by
\( \delta_B(x)=\sum_{\substack{\text{lower endpoint }a\\a\text{ finite}}}\max\{a-x,0\}+\sum_{\substack{\text{upper endpoint }b\\b\text{ finite}}}\max\{x-b,0\}. \)
Here each sum has either one term or no terms. This is exactly the distance from \(x\) to \(B\): it is zero inside the interval and the distance to the nearest endpoint outside it.
For any nonempty set \(S\), taking its closure does not change the infimum of distances to it. Indeed, \(S\subseteq\overline S\) gives one inequality; approximating any point of \(\overline S\) by points of \(S\), and using continuity of distance, gives the other.
For the closed product \(B_t=\prod_j B_{tj}\), Manhattan distance gives
\( \inf_{\eta\in\operatorname{Mod}_I(K_t)}d(\omega,\eta)=\inf_{\eta\in B_t}\sum_{j=1}^m|\omega_j-\eta_j|=\sum_{j=1}^m\delta_{B_{tj}}(\omega_j). \)
The last equality holds because each summand bounds the corresponding coordinate distance from below, while choosing a nearest point in each interval attains all these bounds simultaneously. Nearest points exist even for unbounded closed intervals.
Define
\( f_j(x)=\sum_{t=1}^{\tau}\mu_t\delta_{B_{tj}}(x). \)
The original objective is therefore \(F(\omega)=\sum_{j=1}^m f_j(\omega_j)\), and its feasible set is \(\prod_j C_j\).
We next compute the complete minimizing set of each \(f_j\) on \(C_j\).
Fix a coordinate and suppress its index. Write the source intervals as \(B_t=[a_t,b_t]\), and let
\( T=\sum_{t:\,a_t\text{ finite}}\mu_t. \)
Create an endpoint event of weight \(\mu_t\) at every finite \(a_t\), and another of weight \(\mu_t\) at every finite \(b_t\). If \(a_t=b_t\), both events occur at that point.
Sort and combine events at equal locations. Let the distinct event locations be \(z_1<\cdots<z_r\), with combined positive weights \(e_1,\ldots,e_r\). Define
\( E_0=0,\qquad E_k=\sum_{h=1}^k e_h\quad(1\leq k\leq r). \)
For every point \(x\) outside the event locations, direct differentiation gives
\( f'(x)=-T+\sum_{h:\,z_h<x}e_h. \)
To verify this calculation, a finite lower endpoint contributes slope \(-\mu_t\) before that endpoint and zero afterwards; a finite upper endpoint contributes zero before that endpoint and \(+\mu_t\) afterwards. Thus every event increases the slope by its weight.
Also,
\( E_r=T+\sum_{t:\,b_t\text{ finite}}\mu_t,\qquad 0\leq T\leq E_r. \)
If there are no events, every source interval is the whole real line, so \(f\) is identically zero and its minimizing set is the whole real line.
Otherwise define the extended endpoints \(\ell,u\) as follows:
The required indices exist by \(0\leq T\leq E_r\). Moreover, \(\ell\leq u\).
Claim. The complete unconstrained minimizing set is \(M=[\ell,u]\).
Proof. Before \(\ell\), every slope is strictly negative, because the corresponding prefix weight is less than \(T\). After \(u\), every slope is strictly positive, because the corresponding prefix weight is greater than \(T\).
If \(\ell<u\), the slope between them is zero. For finite distinct endpoints, this follows because the first prefix reaching \(T\) equals \(T\), and the next prefix exceeding \(T\) occurs at \(u\). The same calculation handles the initial ray when \(T=0\) and the final ray when \(T=E_r\).
The function is continuous and piecewise affine. Hence it is constant on \([\ell,u]\), strictly decreasing to that interval whenever there are points to its left, and strictly increasing after it whenever there are points to its right. These statements follow by summing slope times length over the finitely many affine pieces between any two points. They prove the claim. \(\square\)
In particular, the minimum exists without any boundedness assumption.
Restore the coordinate index. Let \(M_j=[\ell_j,u_j]\) be the unconstrained minimizing interval and \(C_j=[c_j,d_j]\) the integrity interval.
Its constrained minimizing set \(A_j\) is obtained by these exhaustive cases:
In the second case, \(d_j\) is finite and \(f_j\) is strictly decreasing throughout \(C_j\), so its unique constrained minimizer is \(d_j\). In the third case, \(c_j\) is finite and strict increase gives the analogous conclusion. In the first case, precisely the feasible unconstrained minimizers attain the global minimum.
Thus each \(A_j\) is a nonempty closed interval. Finally,
\( A=\prod_{j=1}^m A_j. \)
To justify this equality, let \(v_j=\min_{x\in C_j}f_j(x)\). Every feasible assignment satisfies \(F(\omega)\geq\sum_j v_j\), and choosing each coordinate in \(A_j\) attains equality. Conversely, equality forces every nonnegative difference \(f_j(\omega_j)-v_j\) to vanish. Therefore every minimizing assignment belongs to the displayed product.
Writing \(A_j=[\alpha_j,\beta_j]\), the requested formula consists of \(x_j\geq\alpha_j\) for each finite lower endpoint and \(x_j\leq\beta_j\) for each finite upper endpoint. It uses at most \(2m\) inequalities.
The endpoint procedure operates on the support directly.
Write each mass as \(\mu_t=p_t/q_t\), with positive binary integers \(p_t,q_t\). Set
\( Q=\prod_{t=1}^{\tau}q_t,\qquad n_t=p_t(Q/q_t). \)
The bit length of \(Q\) is at most a constant plus the sum of the denominator bit lengths, hence is \(O(L)\). Each \(n_t\) is an integer, and normalization gives
\( \sum_{t=1}^{\tau}n_t=Q. \)
Replace the masses by these integer weights in every endpoint sweep. This multiplies the objective by \(Q\) and preserves its minimizing set.
Each coordinate has at most \(2\tau\) events. Their total integer weight is at most \(2Q\), so all event weights, prefix sums, and target weights have \(O(L)\) bits. Equality and inequality comparisons with the target are therefore exact polynomial-time integer operations.
Normalization scans the input inequalities and compares rational endpoints. Per coordinate, sorting requires \(O(\tau\log(\tau+1))\) rational comparisons, followed by \(O(\tau)\) additions and comparisons. Rational comparisons are polynomial-time by integer cross multiplication, since every finite endpoint has at most \(L\) bits. Computing \(Q\) and the integer weights also takes polynomial time.
Every finite output endpoint is selected from the normalized source or integrity endpoints, hence ultimately from the input. The output has polynomial length.
This proves an exact polynomial-time algorithm for the complete set \(A\), including strict inequalities, singleton domains, unbounded intervals, and binary-rational masses.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the exact binary-rational mass formulation in USER_TASK. The argument establishes a polynomial-time algorithm computing the entire minimizing set. I found no major or minor mathematical issues requiring repair.
Coordinate inequalities and axis-aligned domains imply the stated product representation of each model set. The nonemptiness promises ensure that every coordinate interval is nonempty, so replacing its endpoint inclusion conventions by closed endpoints gives exactly its closure.
The argument correctly distinguishes infinite endpoints from real elements. Its justification that closure commutes with finite products is sufficient. Since \(W\) is closed in the ambient real space, the relative and ambient closures agree for the sets considered.
Taking maxima of lower bounds and minima of upper bounds selects finite endpoints from the input. Strict inequalities do not invalidate this normalization under the nonemptiness promises.
The stated interval distance function handles bounded intervals, singletons, half-lines, and the whole real line correctly. Because the interval is nonempty, its lower and upper violation terms cannot both be positive.
The proof that closure preserves the infimum of distances is valid by continuity. For the closed product, coordinatewise nearest points exist, including for unbounded intervals. Their simultaneous selection justifies the equality between the product distance and the sum of coordinate distances.
Consequently, both the objective and the integrity feasible set separate by coordinate exactly as claimed.
The slope calculation is correct: a finite lower endpoint contributes slope \(-\mu_t\) before its location, and a finite upper endpoint contributes slope \(+\mu_t\) after its location. Each endpoint event therefore increases the slope by its weight. A singleton correctly produces two events at the same location.
The identity for the total event weight and the bounds \(0\leq T\leq E_r\) hold. Positive masses ensure that combined event weights are positive and that the prefix weights strictly increase.
The two endpoint rules correctly distinguish the first prefix reaching \(T\) from the first prefix exceeding \(T\). This distinction captures an entire flat minimizing interval when a prefix equals \(T\), and a singleton when an event jumps across \(T\).
The exceptional cases are also correct:
The continuity and finite piecewise-affine argument establishes constancy on the claimed interval and strict monotonicity outside it. It also establishes attainment without requiring bounded domains.
The three cases are exhaustive for nonempty closed real intervals. When the intervals intersect, precisely their intersection minimizes the constrained objective.
When the integrity interval lies strictly to the left or right, the cited strict monotonicity gives the claimed unique endpoint minimizer. The selected integrity endpoint must be finite in each such case, so no infinite “assignment” is introduced.
Singleton integrity intervals and contact at an endpoint are covered.
Each coordinate minimum exists by the preceding analysis. The lower bound obtained by summing these minima is attained by selecting coordinate minimizers independently.
Conversely, the proof correctly uses nonnegative coordinate excesses: equality of the total objective with the sum of coordinate minima forces every coordinate excess to vanish. Thus the displayed product includes all minimizers and excludes every other feasible assignment.
The proposed conjunction of at most \(2m\) weak inequalities represents this product exactly, with infinite bounds omitted.
The product denominator \(Q\) may be numerically large, but its binary length is \(O(L)\), as stated. Each \(Q/q_t\) is an exact integer, and the normalization of masses gives \(\sum_t n_t=Q\).
Hence every integer source weight is at most \(Q\), and the total event weight for a coordinate is at most \(2Q\). All sweep arithmetic therefore uses integers of \(O(L)\) bits.
There are at most \(2\tau\) events per coordinate. Sorting rational endpoints, combining events, and comparing exact prefix weights require polynomially many operations on polynomial-length numbers. Computing the integer weights also takes polynomial time.
Every finite output endpoint comes from the input, and there are at most two per coordinate. The output length is consequently polynomial. The algorithm operates on the support without expanding masses into repeated sources.
Section 4 of the [cited finite-profile paper](https://www.cril.univ-artois.fr/~marquis/condotta-kaci-marquis-schwind-ecai10.pdf) does describe coordinate projection, interval minimization, and Cartesian-product reconstruction under the Manhattan metric. The prover’s attribution is accurate.
The submitted proof independently establishes the weighted algorithm and its bit complexity; it does not rely on an unstated extension of the finite-profile theorem.
Actionable feedback: No additional mathematical clarification or 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.