Teoria dell'assemblaggio caratterizza la complessità di un oggetto, definito non come un insieme di particelle nello spazio, ma in base alla sua storia di assemblaggio. Applicata alla complessità dei composti chimici, è la prima tecnica che può essere verificata sperimentalmente, a differenza di altri algoritmi che non hanno una verifica sperimentale.

La teoria dell'assemblaggio è stata sviluppata nel 2017 da un team guidato dal chimico Leroy Cronin presso l'Università di Glasgow.

Nella teoria dell'assemblaggio, gli oggetti sono definiti non come insiemi di particelle nello spazio, ma in base alla loro possibile storia di formazione. Per calcolare la complessità di un oggetto, questo viene suddiviso ricorsivamente nelle sue parti componenti, con lo "spazio di assemblaggio" di quell'oggetto definito come il percorso attraverso il quale un dato oggetto può essere assemblato a partire dalle sue parti elementari.

Un "indice di assemblaggio" è definito come il numero minimo di passaggi necessari per assemblare un oggetto a partire da parti elementari e oggetti che potrebbero essere esistiti in passato e quindi essere entrati nel pool di assemblaggio. Nel caso di un tale percorso minimo, lo spazio di assemblaggio corrisponde alla memoria minima, ovvero al numero minimo di operazioni necessarie per assemblare un dato oggetto. Indipendentemente dal numero di parti elementari, l'indice di assemblaggio minimo di un oggetto costituito da tali parti è dato dalla catena di addizione più breve (sequenza OEIS A003313). L'indice di assemblaggio massimo dipende dal numero di parti elementari . Inoltre, la determinazione dell'indice di assemblaggio è un problema NP-completo .

Uno "spazio di assemblaggio" può essere definito come un grafo orientato aciclico di stringhe, in cui tutte le stringhe di lunghezza unitaria (parti elementari) sono vertici sorgente inaccessibili e le stringhe rimanenti sono vertici di secondo grado entrante, corrispondenti ai passi di assemblaggio. I vertici sono indicizzati indipendentemente dalle stringhe che portano, sicché due vertici distinti possono portare la stessa stringa se hanno storie di formazione diverse. La nozione di spazio di assemblaggio può essere estesa a uno spazio di assemblaggio congiunto, in cui insiemi di oggetti vengono assemblati simultaneamente. Sono stati distinti tre spazi di assemblaggio congiunti non equivalenti: quello singolarmente ottimale, in cui ogni obiettivo è assemblato in modo ottimale e ogni stringa compare una sola volta; quello ottimale in molteplicità, in cui ogni obiettivo è assemblato in modo ottimale, ma una stessa stringa può essere portata da più vertici con storie di formazione diverse; e quello collettivamente ottimale, che minimizza la dimensione dell'intero spazio anche al costo di assemblare qualche obiettivo con un piano non ottimale. Lo spazio collettivamente ottimale non è più grande di quello ottimale in molteplicità, e quest'ultimo non è più grande di quello singolarmente ottimale, benché le tre dimensioni possano differire. I problemi di decisione per queste tre grandezze hanno complessità diverse: per lo spazio collettivamente ottimale il problema è NP-completo, mentre per gli altri due è NP-arduo, e la sua appartenenza alla classe NP resta aperta. Allo spazio di assemblaggio si può inoltre associare un'energia di Dirichlet discreta, essendo l'indice di assemblaggio, la profondità del percorso e l'energia di Dirichlet mutuamente indipendenti.

,

è definito come la selezione totale (applicata da un meccanismo basato sull'informazione, ad esempio, selezione biologica o tecnologica) necessaria per produrre un assemblaggio contenente oggetti, di cui sono oggetti unici, dove gli oggetti di tipo ricorre volte e ha un indice di assemblaggio .

Ad esempio, la stringa "abrakadabra" contiene cinque lettere univoche (a, b, k, d e r) ed è formata da undici lettere. Può essere composta dai suoi componenti come a + b --> ab + r --> abr + a --> abra + k --> abrak + a --> abraka + d --> abrakad + abra --> abrakadabra, che richiede sette passaggi perché "abra" è già stata composta in una fase precedente. Una stringa simile, "abrakadrbaa", della stessa lunghezza, non presenta ripetizioni, quindi il suo indice di assemblaggio è 10.

Ad esempio, due stringhe binarie e hanno la stessa lunghezza bit e la stessa entropia . Tuttavia, l'indice di assemblaggio della stringa e ((1.) compone "01" inserendolo nel pool di assemblaggio, (2.) combina "01" con "01" dal pool di assemblaggio inserendo "0101" nel pool di assemblaggio e (3.) combina "0101" composto nel secondo passaggio con "0101" preso dal pool di assemblaggio), mentre l'indice di assemblaggio della stringa e , perché solo "01" può essere riutilizzato dal pool di assemblaggio.

Note

Categoria:Teoria dei grafi Categoria:Teoria della computazione Categoria:Compressione dei dati Categoria:Termodinamica