Computational Complexity of Determining the Assembly Index
For researchers in assembly theory and complexity theory, it formally characterizes the difficulty of a key measure, but the result is incremental as it follows from known grammar problems.
The paper proves that computing the assembly index is NP-complete and its optimization version is NP- and APX-hard, establishing computational intractability.
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.