Answer: \(\mathrm{P}\): polynomial-time solvable, with exact bit complexity \(O\!\left(L+(1+mN+CN+C+\tau)L^2\right)\).
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe optimization problem OPTs(RAs, As, T As, Os) is NP-complete. The theorem’s proof is a straightforward reduction from the 0-1 Knapsack problem. Thus, we propose a greedy algorithm to handle this computationally costly optimization problem.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given complete seller-state types \(h\) with rational masses \(\mu_h\) summing to \(1\), and each type’s resources, costs, agreements, incoming offers, and feasible integral configurations \(Z_h\), choose \(x_{hz}\geq 0\) with \(\sum_{z\in Z_h}x_{hz}=\mu_h\) to maximize \(\sum_{h\in H}\sum_{z\in Z_h}\pi_{hz}x_{hz}\), where \(\pi_{hz}\) is the seller utility of configuration \(z\). What is the complexity of finding an optimal mass allocation?
A society is given by its support: a list \(H\) of \(\tau\) complete seller-state types with positive binary rational masses \(\mu_h\) summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Each type has capacities \(Q_{hr}\in\mathbb Z_{\geq0}\) for \(m\geq1\) resource types, nonnegative rational unit-time costs \(c_{hr}\), and disjoint lists of running contracts \(D_h\), unstarted final agreements \(A_h\), tentative agreements \(T_h\), and acceptable incoming offers \(O_h\). The current state is capacity-feasible.
Each agreement or offer \(o\) specifies a nonzero vector of nonnegative integer resource demands \(q_{or}\), a positive rational duration \(d_o\), nonnegative rational price \(p_o\) and decommitment penalty \(e_o\), and rational timing data. Existing agreements have fixed start times; an accepted offer receives a start time \(s_o\in[a_o,b_o]\), where \(a_o\leq b_o\). Unstarted final agreements may be abandoned only before their start time; running contracts must continue. Tentative agreements may be canceled without penalty.
For each type, the complete finite list \(Z_h\) of feasible integral configurations is explicitly supplied, including rational schedules. A configuration chooses subsets \(K_h\subseteq A_h\), \(J_h\subseteq T_h\), and \(B_h\subseteq O_h\), keeping, respectively, final agreements, tentative agreements, and incoming offers. Each agreement is kept or rejected in its entirety. Together with \(D_h\), the chosen agreements must respect each resource capacity at every time, using half-open service intervals \([s_o,s_o+d_o)\).
Set \(\operatorname{cost}_h(o)=d_o\sum_{r=1}^{m}c_{hr}q_{or}\) and \(\pi_{hz}=\sum_{o\in K_h\cup J_h\cup B_h}(p_o-\operatorname{cost}_h(o))-\sum_{o\in A_h\setminus K_h}e_o\). Contributions from running contracts are fixed and omitted.
Choose nonnegative rational masses \(x_{hz}\) satisfying \(\sum_{z\in Z_h}x_{hz}=\mu_h\) to maximize \(\sum_{h\in H}\sum_{z\in Z_h}\pi_{hz}x_{hz}\). There are no constraints coupling different seller types. Let \(N\) be the total number of listed agreements and offers, \(C=\sum_h|Z_h|\), and \(L\) the total input bit length.
Is finding an optimal mass allocation solvable in polynomial time, or is it NP-hard, with running times stated in \(m,\tau,N,C,L\)?
The discrete seller decision problem, given resources and agreements without an explicit configuration list, is reported NP-complete via a reduction from 0–1 Knapsack. [An et al.](https://personal.ntu.edu.sg/boan/papers/bo-an_aamas10a.pdf)
No result for exactly the mass-allocation problem specified here was located.
The specified mass-allocation problem is polynomial-time solvable. An optimum assigns each seller type’s entire mass to one of its highest-profit listed configurations.
A sufficient exact bit-complexity bound is
\(O\!\left(L+(1+mN+CN+C+\tau)L^2\right)\).
The number of arithmetic operations needed for profit evaluation and optimization is
\(O(mN+CN+C+\tau)\).
These bounds include processing the explicitly supplied configurations; they do not include generating that list from a succinct seller-state description.
Feasibility and completeness of each supplied list \(Z_h\) are input promises. Keeping the current agreements and accepting no incoming offers gives a feasible configuration, so current-state feasibility and completeness imply \(Z_h\ne\varnothing\).
For each \(h\in H\), define
\(M_h=\max_{z\in Z_h}\pi_{hz}\),
and choose any maximizing configuration \(z_h^\star\).
For every feasible mass allocation, nonnegativity of the masses gives
\(\displaystyle \sum_{z\in Z_h}\pi_{hz}x_{hz}\leq \sum_{z\in Z_h}M_hx_{hz} =M_h\mu_h.\)
This inequality holds even when \(M_h\) is negative. Summing over types yields
\(\displaystyle \sum_{h\in H}\sum_{z\in Z_h}\pi_{hz}x_{hz} \leq \sum_{h\in H}\mu_hM_h.\)
Now define \(x^\star_{h,z_h^\star}=\mu_h\), and set every other coordinate to zero. These masses are nonnegative rational numbers and satisfy every type’s mass constraint. Because there are no constraints coupling types, this allocation is feasible. Its objective value equals the upper bound.
Consequently, the exact optimal value is
\(\displaystyle V^\star=\sum_{h\in H}\mu_h\max_{z\in Z_h}\pi_{hz}.\)
There is an optimum with exactly one positive coordinate per type. More generally, an allocation is optimal precisely when it assigns positive mass only to maximizing configurations: the difference from the optimal value is
\(\displaystyle V^\star-\sum_{h,z}\pi_{hz}x_{hz} =\sum_{h,z}(M_h-\pi_{hz})x_{hz},\)
a sum of nonnegative terms.
Write \(C_h=|Z_h|\) and
\(n_h=|A_h|+|T_h|+|O_h|\).
Thus \(\sum_h n_h\leq N\) and \(\sum_h C_h=C\).
First, for every agreement or offer whose contribution is variable, compute
\(\displaystyle w_{ho}=p_o-d_o\sum_{r=1}^{m}c_{hr}q_{or}.\)
This takes \(O(mN)\) arithmetic operations. Running-contract contributions require no evaluation because they are omitted from the objective.
Next, precompute \(E_h=\sum_{o\in A_h}e_o\). The configuration profit can then be evaluated as
\(\displaystyle \pi_{hz} =-E_h +\sum_{o\in K_h}(w_{ho}+e_o) +\sum_{o\in J_h\cup B_h}w_{ho}. \)
This identity follows by expanding the penalty for rejected final agreements:
\(-\sum_{o\in A_h\setminus K_h}e_o=-E_h+\sum_{o\in K_h}e_o\).
Evaluating one configuration requires \(O(1+n_h)\) arithmetic operations. Evaluating all configurations and retaining a maximizing index for every type therefore requires
\(\displaystyle O\!\left(C+\tau+\sum_h C_hn_h\right) \subseteq O(C+\tau+CN) \)
operations. Finally, output the allocation proved optimal above.
The total arithmetic-operation count is therefore
\(O(mN+CN+C+\tau)\).
Schedules and capacities need no further optimization: their role is already represented by the promised feasible configuration lists.
An arithmetic-operation bound alone does not establish polynomial time for binary rational inputs. Here the numerical sizes also remain polynomially bounded.
Let \(D\) be the product of all positive denominators appearing in the rational input fields, and set \(S=D^3\). Since the sum of those denominators’ binary lengths is at most \(L\), both \(D\) and \(S\) have \(O(L)\) bits.
Every elementary profit term is either a price, a penalty, or a product \(d_oc_{hr}q_{or}\). Its denominator divides \(D^2\), hence divides \(S\). All configuration profits can therefore be evaluated as integers \(P_{hz}=S\pi_{hz}\), using exact division, multiplication, and addition. Because \(S>0\), comparing these integers gives exactly the same maximizing configurations as comparing the original rational profits.
For example, if \(d_o=u/v\) and \(c_{hr}=a/b\), the scaled cost term is the integer
\(\displaystyle \frac{S}{vb}\,ua q_{or}.\)
The division is exact because \(vb\) divides \(D^2\).
Every input number has at most \(L\) bits. Each elementary numerical term has magnitude at most \(2^{O(L)}\), and each profit sums at most \(O(mN+N)\) such terms. Multiplication by \(S\) still leaves every intermediate integer with \(O(L)\) bits, since the explicitly encoded parameters satisfy \(m,N\leq O(L)\).
Schoolbook multiplication and long division on these integers take \(O(L^2)\) bit operations; addition and comparison take \(O(L)\). Constructing \(D\) also takes \(O(L^2)\) bit operations: multiplying denominators successively has total schoolbook cost bounded by the square of their total bit length.
Including input processing and output, a sufficient bound is thus
\(\displaystyle O\!\left(L+(1+mN+CN+C+\tau)L^2\right).\)
This is polynomial in the total input length. The output masses introduce no numerical growth: each nonzero mass is an input mass \(\mu_h\).
[An et al., Theorem 1](https://personal.ntu.edu.sg/boan/papers/bo-an_aamas10a.pdf) reports hardness for selecting feasible seller agreements from resources and agreement data. The supplied configuration list changes the input representation: all feasible alternatives are already available for direct comparison.
The distinction also follows from a direct reduction for the version without an explicit configuration list. Given a binary Knapsack instance with positive integer weights \(w_i\), nonnegative integer values \(v_i\), capacity \(W\), and target \(V\), construct one seller type with:
Every accepted offer occupies the same half-open interval \([1,2)\). A subset is therefore feasible exactly when its total weight is at most \(W\), and its profit is exactly its total value.
Moreover, mixing feasible subsets cannot produce a profit exceeding the highest-profit subset, by the same inequality proved in Section 1. Hence the implicit version has optimal value at least \(V\) exactly when the Knapsack instance is a yes-instance.
That establishes hardness for the implicit representation. It does not supply a polynomial-size explicit configuration list. Indeed, when every subset is feasible, even these fixed-schedule instances have \(2^N\) distinct subset configurations. Polynomial time in \(C\) and \(L\) can therefore be exponential in the size of the description before configurations are listed.
The requested problem, with its explicit lists and independent type constraints, is completely resolved by the algorithm above.
⟨structured verdict parsed — rendered above⟩
The prover resolves the specified problem: optimal mass allocation is polynomial-time solvable when the feasible configurations are explicitly supplied. The optimality argument and stated complexity bounds are correct. There is one minor omission in the supplementary reduction for the implicit representation; it does not affect the requested result.
The argument that \(Z_h\neq\varnothing\) is valid under the input promises. Keeping the current agreements and accepting no incoming offers preserves the promised capacity feasibility. Completeness of the supplied list therefore ensures a listed feasible configuration.
Since each \(Z_h\) is finite and nonempty, \(M_h=\max_{z\in Z_h}\pi_{hz}\) exists. No assumption that profits are nonnegative is needed.
For any feasible allocation, the inequality
\(\sum_{z\in Z_h}\pi_{hz}x_{hz}\leq M_h\sum_{z\in Z_h}x_{hz}=M_h\mu_h\)
follows directly from \(x_{hz}\geq0\) and \(\pi_{hz}\leq M_h\). It remains valid for negative \(M_h\).
Assigning mass \(\mu_h\) to a maximizing configuration and zero to every other configuration satisfies all constraints. The masses are rational because the input masses are rational. Independence of the type constraints justifies combining these choices across all types.
The resulting objective attains the stated upper bound. Thus the formula for \(V^\star\) is correct.
The characterization of optimal feasible allocations is also correct: every term in the displayed objective difference is nonnegative, so the difference vanishes exactly when every positive coordinate belongs to a maximizing configuration. Since \(\mu_h>0\), the constructed optimum has exactly one positive coordinate per type.
The penalty rearrangement is correct:
\(-\sum_{o\in A_h\setminus K_h}e_o=-E_h+\sum_{o\in K_h}e_o\).
The disjoint agreement lists prevent double counting in the rewritten profit expression.
Computing the variable agreement contributions requires \(O(mN)\) arithmetic operations. Computing the penalty sums fits within this bound because \(m\geq1\). Evaluating configurations and selecting maxima requires
\(O(C+\tau+\sum_h C_hn_h)\) operations, and
\(\sum_h C_hn_h\leq C\sum_h n_h\leq CN\).
Consequently, \(O(mN+CN+C+\tau)\) is a valid arithmetic-operation bound. Ignoring schedule optimization and feasibility checking is justified by the supplied-list promises; the algorithm need not establish those promises.
The common-denominator argument is sound.
The product \(D\) has \(O(L)\) bits because the total encoded denominator length is at most \(L\). Cubing it preserves that bit-length order.
Prices and penalties have denominators dividing \(D\). Each cost product \(d_oc_{hr}q_{or}\) has denominator dividing \(D^2\), because the demand is integral. Hence scaling by \(S=D^3\) makes every profit term integral. In particular, the displayed division by \(vb\) is exact.
The magnitude bounds also hold: elementary terms have \(O(L)\)-bit magnitudes, and summing polynomially many such terms adds only \(O(\log L)\) bits. Scaling by \(S\) preserves an \(O(L)\) bound on intermediate integer lengths.
The claimed schoolbook multiplication and division costs therefore apply. The bound for constructing \(D\) is consistent with the total denominator bit length.
Input processing and allocation output fit within the stated bound. Nonzero output masses are copied from the input, and an explicit allocation has \(C\) coordinates.
Thus
\(O\!\left(L+(1+mN+CN+C+\tau)L^2\right)\)
is a sufficient exact bit-complexity bound. Under explicit encoding, the listed parameters are bounded by the input length, so this establishes polynomial time in \(L\).
The citation accurately describes the paper’s reported hardness claim: its Theorem 1 concerns selecting seller agreements from agreement and resource data and attributes the result to a Knapsack reduction. The requested polynomial-time conclusion does not rely on that theorem. [An et al., Theorem 1](https://personal.ntu.edu.sg/boan/papers/bo-an_aamas10a.pdf)
The supplementary reduction correctly makes all selected offers occupy \([1,2)\), so feasibility matches the Knapsack weight constraint and profit matches total item value. The earlier averaging inequality correctly rules out improving the optimum through mixing.
The exponential configuration-count example is also correct. It explains why this implicit hardness result does not contradict polynomial time in the explicitly supplied list size.
Minor issue: The reduction does not specify the incoming offers’ decommitment penalties, although the input format requires that field. These penalties do not appear in the objective for incoming offers, so the omission does not affect the reduction’s substance.
Minimum clarification: Specify a permitted value for each offer’s penalty, such as \(e_i=0\). No further mathematical argument 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.