On the "Assembly Theory and its Relationship with Computational Complexity"
IPI Letters · 2025
DOI: 10.59973/ipil.157 ↗At a glance
Journal article in IPI Letters, 2025. Written by Szymon Łukaszyk. 7 references. The full text is freely available (open access, CC BY 4.0).
Abstract (original language)
The study provides an alternative definition of the assembly space as an acyclic, 2-in-regular digraph of strings provided with an edge labeling map that preserves the commutativity of an assembly step but defines the order of concatenation of strings in this step. Remarkably, the uniqueness of each vertex is the sufficient criterion to establish if an assembly step is allowed and to introduce the notion of an assembly pool: unit-length strings cannot be assembled from shorter strings and, hence, are inaccessible, forming the initial assembly pool, and strings present in the assembly space can not be assembled again, possibly using different pathways, as they would not be unique. What is allowed is the evolution of assembly pathways to make them shorter. We also comment on certain results of [ARXIV.2406.12176], showing that the Assembly Steps Problem, not the Assembly Index Problem, has been proved in the referenced study to be NP-complete.
Cite
APA
Łukaszyk, S. (2025). On the "Assembly Theory and its Relationship with Computational Complexity". IPI Letters. https://doi.org/10.59973/ipil.157
Vancouver
Łukaszyk S. On the "Assembly Theory and its Relationship with Computational Complexity". IPI Letters. 2025. doi:10.59973/ipil.157
BibTeX
@article{ukaszyk2025,
author = {Łukaszyk, Szymon},
title = {On the "Assembly Theory and its Relationship with Computational Complexity"},
journal = {IPI Letters},
year = {2025},
doi = {10.59973/ipil.157}
}
EUVIMED