The assembly index of assembly theory quantifies the minimal number of composition steps required to construct an object from elementary components. The study proves that the decision version of the assembly index problem is NP-complete, through an explicit correspondence between assembly plans and straight-line grammars. This correspondence implies that the optimization version of the assembly index problem inherits NP- and APX-hardness from the classical smallest grammar problem. The study provides complete, self-contained proofs for both decision and optimization variants of the assembly index problem. These results establish that computing or approximating the assembly index is computationally intractable, placing it within the same complexity class as grammar-based compression.

Assembly theory defines structural complexity as the minimum number of steps required to construct an object in an assembly space. We formalize the assembly space as an acyclic digraph of strings. Key results include analytical bounds on the minimum and maximum assembly indices as functions of string length and alphabet size, and relations between the assembly index (ASI), assembly depth, depth index, Shannon entropy, and expected waiting times for strings drawn from uniform distributions. We identify patterns in minimum- and maximum-ASI strings and provide construction methods for the latter. While computing ASI is NP-complete, we develop efficient implementations that enable ASI computation of long strings. We establish a counterintuitive, inverse relationship between a string ASI and its expected waiting time. Geometric visualizations reveal that ordered decimal representations of low ASI bitstrings of even length N naturally cluster on diagonals and oblique lines of the squares with sides equal to 2^N/2. Comparison with grammar-based compression (Re-Pair) shows that ASI provides superior compression by exploiting global combinatorial patterns. These findings advance complexity measures with applications in computational biology (where DNA sequences must violate Chargaff's rules to achieve minimum ASI), graph theory, and data compression.

We study the canonical string-based Assembly Index (ASI), defined as the minimum number of binary concatenations needed to construct a target word under full reuse. NP-completeness of ASI-DEC over general finite alphabets and an equivalence between ASI plans and straight-line programs (SLPs) under the same size convention has been established. We emphasize that all transfers between decision variants are effected by explicit polynomial-time mappings and (where needed) an explicit reparameterization of the threshold by an absolute constant or a simple affine function. The remaining technical obstacle for the binary alphabet is that a naive encoding reduction may allow an optimizer to exploit “cross-boundary” substrings created by overlaps of codewords. We give a fully self-contained binary-alphabet proof: we construct an explicit self-synchronizing (comma-free) codebook of 17 fixed-length binary codewords and prove a boundary-normalization lemma showing that optimal plans can be assumed aligned to codeword boundaries. This yields a polynomial reduction from fixed-alphabet ASI-DEC to binary ASI-DEC, proving NP-completeness over {0, 1}. Using the recalled ASI–SLP equivalence (with a short proof for completeness), we obtain NP-completeness of binary SLP-DEC. We additionally provide an explicit, fully formal translation between our binary-rule counting convention and the standard SGP size measure (sum of right-hand side lengths), showing that the NP-completeness classification transfers to common one-string SGP/SLP decision variants over {0, 1}.

Assembly theory measures a string by the shortest history that builds it. We sharpen this picture in two directions. First, we attach a discrete Dirichlet energy to an assembly space and show that it splits into the size of the space and a secondary energy charging each step vertex the square of its secondary (pathway depth) increment. The assembly index does not imply minimum energy, and the assembly depth and the energy are independent complexity measures. Second, we ask how an ensemble T of strings co-assembles within a single space. Individuating step vertices by their formation histories rather than by the strings they carry yields three joint assembly spaces: the collectively (\( \omega_T \)), multiplicity (\( \mu_T \)), and singly (\( \pi_T \)) optimal ones, where the latter need not exist for certain ensembles and \( |\omega_T| \le |\mu_T| \le |\pi_T| \). All three sizes can differ, and multiplicity can lower the singly optimal size only for ensembles with \( |\pi_T| - |\omega_T| \ge 2 \). Collective optimization is NP-complete, while singly and multiplicity optimizations are NP-hard and lie a priori in the second level of the polynomial hierarchy.

Assembly theory measures a string by the shortest history that builds it. We sharpen this picture in two directions. First, we attach a discrete Dirichlet energy to an assembly space and show that it splits into the size of the space and a secondary energy, charging each step vertex the square of its secondary (pathway depth) increment. The assembly index does not imply minimum energy, and the assembly depth and the energy are independent complexity measures. Second, we ask how an ensemble T of strings co-assembles within a single space. Individuating step vertices by their formation histories rather than by the strings they carry yields three joint assembly spaces: the collectively (${\omega }_T$), multiplicity (${\mu }_T$), and singly (${\pi }_T$) optimal ones, where the latter need not exist for certain ensembles and $\mid {\omega }_T\mid \le \mid {\mu }_T\mid \le \mid {\pi }_T\mid$. All three sizes can differ, and multiplicity can lower the singly optimal size only for ensembles with $\mid {\pi }_T\mid - \mid {\omega }_T\mid \ge 2$. Collective optimization is NP-complete, while singly and multiplicity optimizations are NP-hard and lie in the second level of the polynomial hierarchy.

Assembly Theory, as developed by Cronin and co-workers, assigns to an object an assembly index: the minimal number of binary join operations required to build at least one copy of the object from a specified set of basic building blocks, allowing reuse of intermediate components. For strings over a finite alphabet, the canonical assembly index can be defined in the free semigroup (Σ+, ·) with universal binary concatenation and a “no-trash” condition, and its exact computation has been shown to be NP-complete. In this paper we propose an extension of the canonical, string-based formulation which augments pure concatenation with templated assembly steps. Intermediate objects may contain a distinguished wildcard symbol ∗ that represents a compressible block. Templates are restricted to block-compressed substrings of the target string and can be instantiated by inserting previously assembled motifs into one or many wildcard positions, possibly in parallel. This yields a new complexity measure, the templated assembly index, which strictly generalises the canonical index while preserving its operational character. We formalise the model, clarify its relation to the canonical assembly index and to classical problems such as the smallest grammar problem, and discuss the computational complexity of determining the templated assembly index. Finally, we sketch potential applications in sequence analysis, modularity detection, and biosignature design.