On the "Assembly Theory and its Relationship with Computational Complexity"
IPI Letters · 2025
DOI: 10.59973/ipil.157 ↗Kurz gefasst
Fachartikel in der Zeitschrift IPI Letters, 2025. Verfasst von Szymon Łukaszyk. Die Arbeit nennt 7 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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.
Zitieren
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