Computational Complexity of Determining the Assembly Index
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913041550934016 |
|---|---|
| author | Masierak, Piotr |
| author_facet | Masierak, Piotr |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_16302 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Computational Complexity of Determining the Assembly Index Masierak, Piotr Computational Complexity 68Q17 (Primary) 68Q45, 68R15 (Secondary) F.2.2; F.4.3; E.4 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. |
| title | Computational Complexity of Determining the Assembly Index |
| topic | Computational Complexity 68Q17 (Primary) 68Q45, 68R15 (Secondary) F.2.2; F.4.3; E.4 |
| url | https://arxiv.org/abs/2604.16302 |