Answer: \(\mathrm{NP}\)-complete, already for \(\tau=1\).
Theorem 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIf all transformations are multi-output tools, then WINDET is NP-complete, even for the single-unit re- striction.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite goods set \(G\), a catalogue \(T\) of multi-output tools, and a finite support of cell types \(r=(U_{\rm in}^r,U_{\rm out}^r)\) with rational masses \(\mu_r>0\) summing to \(1\), where all specified bundles are single-unit, decide whether there are legal sequences \(\Sigma\) for each type and fractions \(\lambda_{r,\Sigma}\ge 0\) such that \(\sum_{\Sigma}\lambda_{r,\Sigma}=1\) for every \(r\), and \(\sum_r\mu_r\sum_{\Sigma}\lambda_{r,\Sigma}|\Sigma|\le K\). Each cell executes its own sequence under the paper’s goods-update rules; the question is whether the population’s average action load is at most \(K\).
Let \(G\) be a finite goods set, with \(m=|G|\). A catalogue \(T\) explicitly lists multi-output tools \(t=(a,O)\), where \(a\in G\) and \(O\subseteq G\setminus\{a\}\); each application requires possession of \(a\), consumes nothing, and adds one copy of every good in \(O\). Tools may be reused without limit, and produced goods may themselves serve as tools.
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here a type is \(r=(U_{\rm in}^r,U_{\rm out}^r)\), with both bundles subsets of \(G\), and the masses satisfy \(\mu_r>0\) and \(\sum_r\mu_r=1\). The parameter \(\tau\) is the support size, not the number of possible types.
For a finite sequence \(\Sigma=((a_i,O_i))_{i=1}^{\ell}\) from \(T\), start with the multiset \(M_0=U_{\rm in}^r\). Legality requires \(a_i\in M_{i-1}\), and the update is \(M_i=M_{i-1}\uplus O_i\), where \(\uplus\) denotes multiset addition. Intermediate bundles may contain multiple copies. A sequence succeeds for \(r\) if \(U_{\rm out}^r\subseteq M_\ell\); surplus goods are permitted, and the empty sequence is allowed.
Let \(\mathcal S_r\) contain all finite legal sequences succeeding for \(r\). Cells act independently, with no transfer of goods or shared limit on tool use. Given a nonnegative binary rational \(K\), decide whether nonnegative real weights \(\lambda_{r,\Sigma}\) exist satisfying \(\sum_{\Sigma\in\mathcal S_r}\lambda_{r,\Sigma}=1\) for every \(r\) and \(\sum_r\mu_r\sum_{\Sigma\in\mathcal S_r}\lambda_{r,\Sigma}|\Sigma|\le K\).
State running times in \(m\), \(\tau\), \(|T|\), and the total binary input length \(L\).
Is this distributional average-action decision problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For a single discrete cell, bounded-length winner determination with multi-output tools is \(\mathrm{NP}\)-complete even when all specified bundles are single-unit. Without the action bound, feasibility with multi-output tools is solvable in polynomial time. No result for the distributional problem is supplied.
The problem is \(\mathrm{NP}\)-complete, already when the support size is \(\tau=1\). The averaging constraint does not reduce the minimum achievable action count.
For each type \(r\), define \(d_r=\min_{\Sigma\in\mathcal S_r}|\Sigma|\) if \(\mathcal S_r\) is nonempty, and \(d_r=\infty\) otherwise. Whenever \(\mathcal S_r\) is nonempty, this minimum exists and is attained because sequence lengths are nonnegative integers.
The catalogue is finite, so its finite sequences form a countable set. Thus the sums in the question are well-defined nonnegative series, possibly infinite.
Suppose feasible weights exist. Every \(\mathcal S_r\) must be nonempty, since otherwise its weights cannot sum to \(1\). Moreover, for every type \(r\),
\(\displaystyle \sum_{\Sigma\in\mathcal S_r}\lambda_{r,\Sigma}|\Sigma|\ \geq\ d_r\sum_{\Sigma\in\mathcal S_r}\lambda_{r,\Sigma}=d_r.\)
Consequently, feasibility implies \(\sum_r\mu_r d_r\leq K\).
Conversely, suppose every \(d_r\) is finite and \(\sum_r\mu_r d_r\leq K\). For each type, choose a sequence of length \(d_r\) and assign it weight \(1\), assigning all other sequences weight \(0\). These weights satisfy every constraint.
We have therefore proved the exact characterization:
\(\displaystyle \text{The instance is feasible}\quad\Longleftrightarrow\quad \text{every }d_r<\infty\text{ and }\sum_r\mu_r d_r\leq K.\)
For a multiset \(M\), let its support be the set of goods occurring with positive multiplicity. If \(S_i\) is the support after step \(i\), legality and evolution are exactly
\(\displaystyle a_i\in S_{i-1},\qquad S_i=S_{i-1}\cup O_i.\)
This follows because tools consume nothing, require only possession, and success requires only possession of the specified goods.
Consider a shortest successful sequence for a feasible type \(r\). No step can satisfy \(O_i\subseteq S_{i-1}\): such a step leaves the support unchanged, so deleting it preserves the legality of every subsequent step and preserves success, contradicting minimality.
Every step therefore adds at least one previously absent good. Hence its length is at most \(m-|U_{\rm in}^r|\).
Furthermore, a tool cannot occur twice in this sequence. After its first application, all its outputs remain present, so a second application would leave the support unchanged. Thus
\(\displaystyle d_r\leq \min\{m-|U_{\rm in}^r|,\ |T|\}\leq b,\qquad b=\min\{m,\ |T|\}.\)
A certificate specifies one catalogue sequence of length at most \(b\) for every supported type. The verifier checks each sequence’s legality and success, and then checks whether their weighted total length is at most \(K\).
Section 1 proves that every feasible instance admits such a certificate; Section 2 bounds its size. Conversely, any accepted certificate gives feasible weights by placing weight \(1\) on each certified sequence.
Using Boolean arrays for possession, sequence verification takes \(O(\tau m(b+1))\) operations after reading the catalogue. The certificate uses \(O(\tau(b+1)\log(|T|+2))\) bits.
The weighted comparison can be performed exactly. Write \(\mu_r=p_r/q_r\) and \(K=p_K/q_K\), with positive denominators, and set \(D=q_K\prod_r q_r\). If the certified lengths are \(\ell_r\), compare the integers
\(\displaystyle \sum_r p_r\ell_r(D/q_r)\quad\text{and}\quad p_K(D/q_K).\)
These integers have \(O(L)\) bits: the denominator bit lengths are part of the input, and \(\ell_r\leq m\), with the goods set explicitly represented. Using schoolbook integer arithmetic gives the conservative verifier bound
\(\displaystyle O\!\left(L+\tau m(b+1)+\tau L^2\right).\)
This is polynomial in the input size, establishing membership in \(\mathrm{NP}\).
For completeness, an exact deterministic algorithm performs breadth-first search over possession subsets separately for each type. Its vertices are subsets \(S\subseteq G\), with a transition to \(S\cup O\) whenever \((a,O)\in T\) and \(a\in S\). The first reached subset containing \(U_{\rm out}^r\) determines \(d_r\). There are at most \(2^m\) vertices, giving the conservative running-time bound
\(\displaystyle O\!\left(L+\tau\,2^m(|T|+1)(m+1)+\tau L^2\right).\)
Use the single-cell bounded-length winner problem stated in the question to be \(\mathrm{NP}\)-complete.
Given such an instance with goods \(G\), catalogue \(T\), input and output bundles, and nonnegative action bound \(k\), construct a society with exactly that one type, mass \(\mu_1=1\), and threshold \(K=k\). This copies the original data and adds only a constant amount of information, so the transformation takes time linear in the source input length.
By Section 1, the resulting distributional instance is feasible exactly when the cell has a successful sequence of length at most \(k\). Thus this is a polynomial-time many-one reduction. It preserves the single-unit bundle restriction and has \(\tau=1\).
Together with Section 3, this proves \(\mathrm{NP}\)-completeness.
⟨structured verdict parsed — rendered above⟩
The prover’s argument is correct and resolves the task: the distributional average-action problem is \(\mathrm{NP}\)-complete, already for \(\tau=1\). No major or minor mathematical gaps were found.
The definition of \(d_r\) is valid. A nonempty set of finite sequence lengths is a nonempty subset of the nonnegative integers, so it has an attained minimum.
The countability claim is also correct: finite sequences over a finite catalogue form a countable set. All summands are nonnegative, so the infinite sums are unambiguously defined, including when their value is infinite.
For feasible weights, an empty \(\mathcal S_r\) would make the normalization constraint impossible. For each nonempty \(\mathcal S_r\), the inequality
\[
\sum_{\Sigma\in\mathcal S_r}\lambda_{r,\Sigma}|\Sigma|
\geq d_r\sum_{\Sigma\in\mathcal S_r}\lambda_{r,\Sigma}
=d_r
\]
is justified term by term. Summing over the finite support with positive masses establishes the necessary weighted minimum bound.
The converse uses attained minima and places all weight on one minimizing sequence per type. Independence of cells and unlimited tool reuse ensure that these choices introduce no additional compatibility constraints.
Thus the characterization in Section 1 is fully established.
Passing from multisets to their supports preserves both legality and success under the stated rules: no action consumes goods, tool prerequisites require only possession, and target bundles are sets.
The deletion argument is valid. If a step adds no new support element, deleting it preserves the support available at every subsequent step, hence preserves legality and final success. A shortest successful sequence therefore introduces at least one previously absent good at every step, proving the bound \(m-|U_{\rm in}^r|\).
The bound by \(|T|\) is also justified: after a tool’s first application, all its outputs remain present, so any later application of that same tool introduces no new support element.
These arguments cover empty sequences, initially satisfied targets, empty-output tools, empty catalogues, and an empty goods set.
The certificate need not establish that its sequences are shortest. Its verifier only needs to establish legality, success, and the weighted length bound. An accepted certificate directly yields feasible point-mass weights; conversely, Sections 1 and 2 guarantee a bounded certificate for every feasible instance.
The certificate-size bound accounts for catalogue indices and sequence lengths. Boolean support tracking gives the stated \(O(\tau m(b+1))\) operation bound.
The exact rational comparison is correct because \(D\) is a positive common multiple of every denominator. Multiplication by \(D\) preserves the inequality.
The \(O(L)\) integer-size claim is justified: denominator bit lengths sum to at most the input length, and numerator sizes, certified lengths, and summation growth contribute only \(O(L)\) additional bits. Consequently, the stated conservative schoolbook-arithmetic verifier bound is polynomial.
The subset graph exactly represents support evolution. Every edge corresponds to a legal application, and every legal sequence induces a graph walk. Breadth-first search therefore computes the minimum action count by reaching a subset containing the target.
There are at most \(2^m\) states; examining all catalogue tools and constructing successor supports fits the stated conservative bound. If no target-containing state is reachable, the type is infeasible. The resulting algorithm is correct, though exponential in \(m\), and does not assert polynomial-time solvability.
The reduction legitimately invokes the bounded-length single-cell problem supplied by the task, under the same tool and success semantics.
With one type of mass \(1\) and \(K=k\), Section 1 gives exact equivalence between distributional feasibility and existence of a successful sequence of length at most \(k\). The construction copies the source data, has linear size, and preserves the stated bundle restriction.
The reduction proves \(\mathrm{NP}\)-hardness; Section 3 supplies membership in \(\mathrm{NP}\). The claimed completeness result follows.
No additional clarification or repair is required.
⟨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.