A teoria da montagem caracteriza a complexidade de um objeto, definida não como uma coleção de partículas no espaço, mas por sua história de montagem. Aplicada à complexidade de compostos químicos, é a primeira técnica que pode ser verificada experimentalmente, ao contrário de outros algoritmos que não requerem verificação experimental .

A teoria da montagem foi desenvolvida em 2017 por uma equipe liderada pelo químico Leroy Cronin na Universidade de Glasgow.

Na teoria da montagem, os objetos são definidos não como coleções de partículas no espaço, mas por sua possível história de formação. Para calcular a complexidade de um objeto, ele é dividido recursivamente em suas partes componentes, definindo o "espaço de montagem" desse objeto como o caminho pelo qual um determinado objeto pode ser montado a partir de suas partes elementares.

Um "índice de montagem" é definido como o número mínimo de etapas necessárias para montar um objeto a partir de partes elementares e objetos que podem ter existido no passado e, portanto, entrado no conjunto de montagem. No caso deste caminho mais curto, o espaço de montagem corresponde à memória mínima, ou seja, ao número mínimo de operações necessárias para montar um determinado objeto. Independentemente do número de partes elementares, o índice de montagem mínimo de um objeto composto por tais partes é dado pela cadeia de adição mais curta para (sequência OEIS A003313). O índice de montagem máximo depende do número de partes elementares . Além disso, determinar o índice de montagem é um problema NP-completo.

Um «espaço de montagem» (ing. assembly space) pode ser definido como um grafo acíclico direcionado de cadeias, onde todas as cadeias de comprimento unitário (partes elementares) são vértices de origem inacessíveis e as cadeias restantes são vértices de grau de entrada dois, correspondentes às etapas de montagem. Os vértices são indexados independentemente das cadeias que carregam, de modo que dois vértices distintos podem carregar a mesma cadeia desde que tenham histórias de formação diferentes.

A noção de espaço de montagem pode ser estendida a um espaço de montagem conjunto, no qual conjuntos de objetos são montados simultaneamente. Foram distinguidos três espaços de montagem conjuntos não equivalentes: o individualmente ótimo, no qual cada alvo é montado de forma ótima e cada cadeia ocorre uma única vez; o ótimo em multiplicidade, no qual cada alvo é montado de forma ótima, mas uma mesma cadeia pode ser carregada por vários vértices com histórias de formação distintas; e o coletivamente ótimo, que minimiza o tamanho de todo o espaço mesmo ao custo de montar algum alvo por um plano não ótimo. O espaço coletivamente ótimo não é maior que o ótimo em multiplicidade, e este não é maior que o individualmente ótimo, embora os três tamanhos possam diferir. Os problemas de decisão correspondentes a essas três grandezas têm complexidades distintas: para o espaço coletivamente ótimo o problema é NP-completo, enquanto para os outros dois é NP-difícil, e sua pertença à classe NP permanece em aberto.

Ao espaço de montagem também se pode associar uma energia de Dirichlet discreta, sendo o índice de montagem, a profundidade do caminho e a energia de Dirichlet mutuamente independentes.

Montagem

，

é definida como a seleção total (imposta por um mecanismo baseado em informação, por exemplo, seleção biológica ou tecnológica) necessária para produzir uma montagem contendo objetos, onde são objetos únicos, objetos do tipo aparecem vezes e possuem um índice de montagem .

Por exemplo, a string "abrakadabra" contém cinco letras únicas (a, b, k, d e r) e possui onze letras. Ela pode ser montada a partir de seus componentes como a + b --> ab + r --> abr + a --> abra + k --> abrak + a --> abraka + d --> abrakad + abra --> abrakadabra, o que requer sete etapas porque "abra" já foi montada em uma etapa anterior. Uma cadeia semelhante, "abrakadrbaa", do mesmo comprimento, não possui repetições, portanto seu índice de montagem é 10.

Por exemplo, duas cadeias binárias e têm o mesmo comprimento bits e a mesma entropia . No entanto, o índice de montagem da cadeia é ((1.) compõe "01" inserindo-o no conjunto de montagem, (2.) combina "01" com "01" do conjunto de montagem inserindo "0101" no conjunto de montagem e (3.) combina "0101" composto na segunda etapa com "0101" retirado do conjunto de montagem), enquanto o índice de montagem da cadeia é , porque apenas "01" do conjunto de montagem pode ser reutilizado.

Categoria:Teoria dos grafos Categoria:Compressão de dados Categoria:Termodinâmica Categoria:Campos interdisciplinares