Computational Complexity of Determining the Assembly Index

Piotr Masierak

doi:10.59973/ipil.315

Authors

Piotr Masierak Łukaszyk Patent Attorneys, ul. Głowackiego 8, 40-052 Katowice, Poland https://orcid.org/0009-0008-9895-5329

DOI:

https://doi.org/10.59973/ipil.315

Keywords:

Assembly theory, Assembly index, Grammar-based-compression, Computational complexity, Information theory, Complexity measures, NP-completeness

Abstract

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.

Author Biography

Piotr Masierak, Łukaszyk Patent Attorneys, ul. Głowackiego 8, 40-052 Katowice, Poland

M.Eng. studies at the Silesian University of Technology, faculty of Electrical Engineering.

ORCID: 0009-0008-9895-5329

References

Marshall SM, Murray ARG, Cronin L. A probabilistic framework for identifying biosignatures using Pathway Complexity. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences. 2017 Dec; 375 (2109): 20160342. Available from: https://royalsocietypublishing.org/doi/10.1098/rsta.2016.0342.

Marshall SM, Moore DG, Murray ARG, Walker SI, Cronin L. Formalising the Pathways to Life Using Assembly Spaces. Entropy. 2022 Jun;24(7):884. Available from: https://www.mdpi.com/1099-4300/24/7/884.

Sharma A, Cz´egel D, Lachmann M, Kempes CP, Walker SI, Cronin L. Assembly theory explains and quantifies selection and

evolution. Nature. 2023 Oct;622(7982):321-8. Available from: https://www.nature.com/articles/s41586-023-06600-9.

Łukaszyk S, Bieniawski W. Assembly Theory of Binary Messages. Mathematics. 2024 May;12(10):1600. Available from: https:

//www.mdpi.com/2227-7390/12/10/1600

Kempes CP, Lachmann M, Iannaccone A, Matthew Fricke G, Redwan Chowdhury M, Walker SI, et al. Assembly theory and its

relationship with computational complexity. npj Complexity. 2025 Sep;2(1):27. Available from: https://www.nature.com/articles/s44260-025-00049-9

Łukaszyk S. On the ”Assembly Theory and its Relationship with Computational Complexity”. IPI Letters. 2025 Jan:1-6. Available from: https://ipipublishing.org/index.php/ipil/article/view/157

Charikar M, Lehman E, Liu D, Panigrahy R, Prabhakaran M, Sahai A, et al. The smallest grammar problem. IEEE Transactions

on Information Theory. 2005;51(7):2554-76. Available from: https://web.cs.ucla.edu/œsahai/work/web/2005%20Publications/

TransOnInfoTheory2005.pdf

Rytter W. Application of Lempel–Ziv factorization to the approximation of grammarbased compression. Theoretical Computer Science. 2003 Jun;302(1-3):211-22. Available from: https://linkinghub.elsevier.com/retrieve/pii/S0304397502007776

Casel K, Fernau H, Gaspers S, Gras B, Schmid ML. On the Complexity of the Smallest Grammar Problem over Fixed Alphabets. Theory of Computing Systems. 2021 Feb; 65(2):344-409. Available from: http://link.springer.com/10.1007/s00224-020-10013-w