Answer: \(\mathrm{NP}\)-hard; \(\mathrm{NP}\)-complete under the stated input promises, already with \(\tau=1\) and three affine pieces per alternative.
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe SCSGA problem is NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(K\), rational masses \(\mu_r\) summing to \(1\), \(m\) alternatives, rational continuous piecewise-affine functions \(g_j:[0,1]^{|K|}\to\mathbb{Q}\), and a rational threshold \(q\), does there exist an allocation \(x_{rj}\ge 0\) with \(\sum_{j=1}^{m}x_{rj}=\mu_r\) for each \(r\in K\) and \(\sum_{j=1}^{m}g_j(x_{\cdot j})\ge q\)?
A society is given by its support: a list \(K\) of \(\tau\ge 1\) types with positive binary-rational masses \(\mu_r\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\ge 1\) labeled alternatives. For each alternative, the input specifies a continuous piecewise-affine function \(g_j:[0,1]^\tau\to\mathbb R\) by an explicit finite list of rational polyhedra covering the cube and rational affine formulas agreeing on overlaps. Polyhedra are specified by binary-rational linear inequalities.
Function values may have either sign, and \(g_j(0)\) need not vanish. The threshold \(q\in\mathbb Q\) is given in binary. Let \(L\) be the total input bit length, including all function descriptions.
An allocation consists of real numbers \(x_{rj}\ge 0\) satisfying \(\sum_{j=1}^m x_{rj}=\mu_r\) for every \(r\in K\). Types may be split among alternatives, and alternatives may receive zero mass. Write \(x_{\cdot j}=(x_{rj})_{r\in K}\).
Is deciding whether an allocation satisfies \(\sum_{j=1}^m g_j(x_{\cdot j})\ge q\) solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
Discrete simultaneous coalition structure generation and assignment—partitioning agents among labeled alternatives, allowing empty coalitions, with an additive coalition-to-alternative objective—is stated to be NP-complete in the [verified discrete result](https://ojs.aaai.org/index.php/AAAI/article/download/17349/17156).
No result settling this exact continuous problem was located in the literature search.
Interpreting the question as asking whether there exists an allocation meeting the threshold, the problem is \(\mathrm{NP}\)-hard. Under the stated promises on the function descriptions, it also belongs to \(\mathrm{NP}\).
Hardness already holds with \(\tau=1\), mass \(\mu_1=1\), threshold \(q=0\), and exactly three affine pieces per alternative.
We use the classical \(\mathrm{NP}\)-hardness of Subset Sum with positive integers: given binary-encoded \(w_1,\ldots,w_n\) and a positive target \(B\), decide whether some \(I\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{i\in I}w_i=B\). This positive-integer formulation and its hardness are stated in [Polak, Rohwedder, and Węgrzycki, *Knapsack and Subset Sum with Small Items*](https://arxiv.org/html/2105.04035).
Let \(S=\sum_{i=1}^n w_i\), and choose a power of two \(N=2^k>\max\{S,B\}\). Construct a society with one type of mass \(1\) and \(m=n+1\) labeled alternatives. Define
\(a_i=w_i/N\quad (1\le i\le n),\qquad a_{n+1}=(N-B)/N.\)
Every \(a_j\) is a dyadic rational strictly between \(0\) and \(1\). For each alternative, define
\(g_j(t)=-\min\{t,\lvert t-a_j\rvert\},\qquad 0\le t\le1.\)
The explicit polyhedral description consists of the following three closed intervals and affine formulas:
| Polyhedron | Affine formula |
|---|---|
| \(0\le t\le a_j/2\) | \(-t\) |
| \(a_j/2\le t\le a_j\) | \(t-a_j\) |
| \(a_j\le t\le1\) | \(a_j-t\) |
These intervals cover \([0,1]\). At \(t=a_j/2\), both incident formulas equal \(-a_j/2\); at \(t=a_j\), both equal \(0\). Thus the formulas agree on overlaps and define a continuous piecewise-affine function.
Moreover,
\(g_j(t)\le0,\qquad g_j(t)=0\ \Longleftrightarrow\ t\in\{0,a_j\}.\)
Indeed, both quantities inside the minimum are nonnegative, and their minimum vanishes precisely when \(t=0\) or \(\lvert t-a_j\rvert=0\).
Set \(q=0\). Writing \(x_j=x_{1j}\), allocation feasibility becomes
\(x_j\ge0,\qquad \sum_{j=1}^{n+1}x_j=1.\)
The integer \(k\) is polynomially bounded by the source input length: \(\log_2 S\) is at most the maximum input weight bit length plus \(\log_2 n\). Consequently, all breakpoints and affine coefficients have polynomial bit length.
Each function uses three intervals, each specified by two dyadic linear inequalities. The construction therefore has polynomial total bit length and is computable in polynomial time. It satisfies the input requirements even if “binary-rational” is interpreted specifically as dyadic rational.
Suppose \(I\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{i\in I}w_i=B\). Allocate
\(x_i=a_i\) for \(i\in I\), \(x_i=0\) for \(i\notin I\), and \(x_{n+1}=a_{n+1}\).
The total allocated mass is
\(\sum_{j=1}^{n+1}x_j=B/N+(N-B)/N=1.\)
Every coordinate is a zero of its corresponding function. Hence \(\sum_j g_j(x_j)=0\ge q\).
Conversely, suppose a feasible allocation satisfies \(\sum_j g_j(x_j)\ge0\). Each summand is nonpositive, so every summand must equal zero. Therefore \(x_j\in\{0,a_j\}\) for every \(j\).
The last alternative must receive \(a_{n+1}\). Otherwise,
\(\sum_{j=1}^{n+1}x_j\le\sum_{i=1}^n a_i=S/N<1,\)
contradicting feasibility.
Let \(I=\{i\in\{1,\ldots,n\}:x_i=a_i\}\). The allocation equality now gives
\(\sum_{i\in I}w_i/N+(N-B)/N=1,\)
and thus \(\sum_{i\in I}w_i=B\).
This proves the equivalence and establishes \(\mathrm{NP}\)-hardness. Splitting is fully allowed; the functions force the required discrete choices only for allocations meeting the threshold.
We now prove membership in \(\mathrm{NP}\) for inputs satisfying the stated representation promises.
Suppose a successful real allocation exists. For each alternative \(j\), select one listed polyhedron \(P_j\) containing \(x_{\cdot j}\), and write its affine formula as
\(g_j(z)=c_j^{\mathsf T}z+b_j\quad\text{on }P_j.\)
Such a selection exists because the listed polyhedra cover the cube. Consider the rational linear system
\(x_{rj}\ge0,\qquad \sum_{j=1}^m x_{rj}=\mu_r,\qquad x_{\cdot j}\in P_j,\)
together with
\(\sum_{j=1}^m(c_j^{\mathsf T}x_{\cdot j}+b_j)\ge q.\)
Its feasible set is nonempty because it contains the original allocation. It is bounded because \(0\le x_{rj}\le\mu_r\le1\). It is closed because all constraints are non-strict linear inequalities or equalities. Therefore it is a nonempty rational polytope.
Here is the certificate-size argument explicitly. Put \(D=m\tau\). A nonempty bounded polytope has a vertex: successively minimize each of its \(D\) coordinates over the previously obtained minimizing face. Compactness ensures each minimum exists, and after all coordinates are fixed the resulting singleton is an extreme point.
At a vertex, the active constraint normals span \(\mathbb R^D\). Otherwise, a nonzero vector orthogonal to every active normal would permit sufficiently small movements in both directions while preserving all constraints, contradicting extremality. Thus the vertex is determined by \(D\) independent active equations.
After clearing denominators in each equation, let every integer coefficient and right-hand side have absolute value at most \(2^H\). The value \(H\) is polynomially bounded in \(m,\tau,L\): the selected system has polynomial size, and clearing denominators multiplies only polynomially many binary-encoded denominators.
By Cramer’s rule, each vertex coordinate is a ratio of integer determinants. Each determinant has absolute value at most \(D!\,2^{DH}\), so each coordinate has numerator and denominator bit lengths bounded by \(O(DH+D\log D)\).
Consequently, a certificate consists of the selected polyhedron indices and a polynomial-size rational allocation. Exact rational arithmetic verifies polyhedron membership, all allocation constraints, and the objective inequality in polynomial time. Agreement of formulas on overlaps ensures that the verified affine values are the specified function values.
The reduction can be strengthened. Replace each function by \(h_j(t)=t+g_j(t)\), and set the threshold to \(1\). Its three formulas are respectively \(0\), \(2t-a_j\), and \(a_j\). Hence \(h_j\) is continuous, nonnegative, nondecreasing, and satisfies \(h_j(0)=0\).
For every feasible allocation,
\(\sum_j h_j(x_j)=1+\sum_j g_j(x_j).\)
Thus the new threshold is met exactly when the original threshold is met.
The requested decision problem is therefore \(\mathrm{NP}\)-hard, with polynomially checkable certificates under its representation promises. A polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The argument establishes the intended existential decision problem’s \(\mathrm{NP}\)-hardness and membership in \(\mathrm{NP}\) under the stated representation promises. I found no false mathematical step or major gap. There is one minor omission in specifying the polynomial-size reduction.
The prover explicitly interprets the task as deciding whether there exists a feasible allocation meeting the threshold. This is the evidently intended optimization decision question.
The source problem is stated precisely: positive binary-encoded integer weights and a positive target, with the question whether a subset sums exactly to the target. The cited [paper](https://arxiv.org/html/2105.04035) defines Subset Sum using positive integers and states its weak \(\mathrm{NP}\)-hardness. Weak hardness is sufficient for the requested conclusion; strong hardness is neither needed nor claimed.
Given \(N>\max\{S,B\}\), the assertions
\(0<a_i<1\) and \(0<a_{n+1}<1\) are correct. All constructed coefficients and breakpoints are dyadic rationals.
The three formulas correctly represent
\(g_j(t)=-\min\{t,|t-a_j|\}\):
The boundary calculations are correct. The closed intervals cover the domain, and their formulas agree on every overlap. Thus the construction satisfies the continuity and explicit polyhedral representation promises.
The nonpositivity assertion and zero-set characterization are also correct:
\(g_j(t)=0\) exactly at \(t=0\) and \(t=a_j\).
Minor issue — selection of \(N\). The instruction “choose a power of two” gives only a lower bound on \(N\), whereas the encoding argument subsequently asserts a polynomial upper bound on its exponent \(k\). That upper bound does not hold for an arbitrarily chosen qualifying power. Moreover, the displayed discussion bounds \(S\) but does not explicitly account for \(B\).
Minimum clarification needed: specify that \(N\) is the least power of two exceeding \(\max\{S,B\}\), and include the binary length of \(B\) in the exponent bound. This is an expositional repair requiring no new mathematics.
With that clarification, the polynomial construction and encoding-size claim stand.
The proposed allocation is nonnegative and has total mass
\(B/N+(N-B)/N=1\). Consequently, all coordinates lie in the functions’ domains.
Every coordinate belongs to its corresponding zero set, so the objective equals the threshold \(0\). The forward implication is correct.
A finite sum of nonpositive terms can be nonnegative only if every term is zero. Therefore every coordinate of a successful allocation must belong to \(\{0,a_j\}\).
If the final coordinate were zero, the total allocated mass would be at most \(S/N<1\), contradicting feasibility. Hence it equals \(a_{n+1}\).
The ensuing allocation equality gives precisely
\(\sum_{i\in I}w_i=B\). This proves the reverse implication.
The argument also handles \(B>S\): a successful allocation would still imply a subset summing to \(B\), which cannot exist. There is no missing restriction requiring \(B\le S\).
Allowing arbitrary real splitting creates no loophole, because the objective threshold forces every successful coordinate into the explicitly identified zero set.
The certificate argument is valid under the input promises.
For any successful real allocation, each alternative has at least one listed polyhedron containing its column. Selecting those polyhedra produces a rational linear system containing the original allocation.
The resulting feasible set is closed and bounded. The allocation constraints imply
\(0\le x_{rj}\le\mu_r\le1\), so no separate cube constraints are needed.
The vertex-existence argument is sound: successive coordinate minimization produces nested nonempty compact faces and ultimately a singleton, which is an extreme point.
The active-normal argument is also sound, including for lower-dimensional polytopes. If the active normals failed to span the ambient space, a nonzero orthogonal direction would preserve active constraints, and sufficiently small movements in both directions would preserve all finitely many inactive constraints. That contradicts extremality.
Selecting \(D\) independent active equations and applying Cramer’s rule is justified. The denominator-clearing bound is polynomial in the stated parameters, and the determinant estimate
\(D!\,2^{DH}\) is correct. It yields polynomial-bit rational coordinates.
Finally, the selected indices and rational allocation can be checked using polynomial-time exact rational arithmetic. Agreement on overlaps ensures that the selected affine formulas give the actual function values. The prover correctly limits this membership conclusion to promised inputs; it does not claim to verify the representation promises.
The formulas for \(h_j(t)=t+g_j(t)\) are correct. Their slopes are \(0\), \(2\), and \(0\), their boundary values agree, and their values are nonnegative throughout the domain.
The identity
\(\sum_j h_j(x_j)=1+\sum_j g_j(x_j)\)
follows directly from allocation feasibility. Thus threshold \(1\) gives exactly the same successful allocations. This additional hardness claim is established.
The reduction and certificate argument resolve the target. The only requested revision is an explicit polynomial-size choice of \(N\); no substantive proof 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.