La teoría de ensamblajes caracteriza la complejidad de un objeto, definida no como un conjunto de partículas en el espacio, sino por su historial de ensamblaje. Aplicada a la complejidad de los compuestos químicos, es la primera técnica que puede verificarse experimentalmente, a diferencia de otros algoritmos que no requieren verificación experimental .
La teoría de ensamblajes fue desarrollada en 2017 por un equipo dirigido por el químico Leroy Cronin en la Universidad de Glasgow.
En la teoría de ensamblajes, los objetos se definen no como conjuntos de partículas en el espacio, sino por su posible historia de formación. Para calcular la complejidad de un objeto, este se divide recursivamente en sus partes componentes, definiendo el "espacio de ensamblaje" de dicho objeto como la ruta por la cual un objeto dado puede ensamblarse a partir de sus partes elementales.
Un "índice de ensamblaje" se define como el número mínimo de pasos necesarios para ensamblar un objeto a partir de partes elementales y de objetos que pudieron haber existido en el pasado y, por lo tanto, ingresaron al conjunto de ensamblajes. En el caso de dicha ruta más corta, el espacio de ensamblaje corresponde a la memoria mínima, es decir, al número mínimo de operaciones necesarias para ensamblar un objeto dado. Independientemente del número de partes elementales, el índice de ensamblaje mínimo de un objeto compuesto por dichas partes viene dado por la cadena de adición más corta para (secuencia OEIS OEIS A003313). El índice de ensamblaje máximo depende del número de partes elementales . Además, determinar el índice de ensamblaje es un problema NP-completo .
Un "espacio de ensamblaje" puede definirse como un grafo acíclico dirigido de cadenas, donde todas las cadenas de longitud unitaria (partes elementales) son vértices fuente inaccesibles y las cadenas restantes son vértices de grado de entrada dos, correspondientes a los pasos de ensamblaje. Los vértices se indexan con independencia de las cadenas que portan, de modo que dos vértices distintos pueden portar la misma cadena si tienen historias de formación diferentes. La noción de espacio de ensamblaje puede extenderse a un espacio de ensamblaje conjunto, en el que se ensamblan simultáneamente conjuntos de objetos. Se han distinguido tres espacios de ensamblaje conjuntos no equivalentes: el óptimo individualmente, en el que cada objetivo se ensambla de forma óptima y cada cadena aparece una sola vez; el óptimo en multiplicidad, en el que cada objetivo se ensambla de forma óptima, pero una misma cadena puede ser portada por varios vértices con historias de formación distintas; y el óptimo colectivamente, que minimiza el tamaño de todo el espacio incluso a costa de ensamblar algún objetivo mediante un plan no óptimo. El espacio óptimo colectivamente no es mayor que el óptimo en multiplicidad, y este no es mayor que el óptimo individualmente, si bien los tres tamaños pueden diferir. Los problemas de decisión correspondientes a estas tres magnitudes tienen complejidades distintas: para el espacio óptimo colectivamente el problema es NP-completo, mientras que para los otros dos es NP-difícil, y su pertenencia a la clase NP permanece abierta. Al espacio de ensamblaje también puede asociarse una energía de Dirichlet discreta, siendo el índice de ensamblaje, la profundidad de la ruta y la energía de Dirichlet mutuamente independientes.
El ensamblaje
,
se define como la selección total (impuesta por un mecanismo basado en información, p. ej., selección biológica o tecnológica) necesaria para producir un ensamblaje que contenga objetos, de los cuales son objetos únicos, donde los objetos de tipo aparecen veces y tienen un índice de ensamblaje .
Por ejemplo, la cadena "abrakadabra" contiene cinco letras únicas (a, b, k, d y r) y tiene once letras. Se puede ensamblar a partir de sus componentes como a + b --> ab + r --> abr + a --> abra + k --> abrak + a --> abraka + d --> abrakad + abra --> abrakadabra, lo que requiere siete pasos porque "abra" ya se ha ensamblado en un paso anterior. Una cadena similar, "abrakadrbaa", de la misma longitud, no tiene repeticiones, por lo que su índice de ensamblaje es 10.
Por ejemplo, dos cadenas binarias y tienen la misma longitud bits y la misma entropía . Sin embargo, el índice de ensamblaje de la cadena y ((1.) compone "01" insertándolo en el conjunto de ensamblajes, (2.) combina "01" con "01" del conjunto de ensamblajes insertando "0101" en el conjunto de ensamblajes, y (3.) combina "0101" compuesto en el segundo paso con "0101" tomado del conjunto de ensamblajes), mientras que el índice de ensamblaje de la cadena y , porque solo "01" del conjunto de ensamblajes puede reutilizarse.
Referencias
Categoría:Teoría de grafos Categoría:Compresión de datos Categoría:Termodinámica