EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

On the "Assembly Theory and its Relationship with Computational Complexity"

Szymon Łukaszyk

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →