Теория сборки характеризует сложность объекта, определяемую не как совокупность частиц в пространстве, а как история его сборки. Применительно к сложности химических соединений, это первый метод, который может быть экспериментально подтвержден, в отличие от других алгоритмов, для которых отсутствуют возможности экспериментальной проверки .
Теория сборки была разработана в 2017 году группой под руководством химика Лероя Кронина в Университете Глазго.
В теории сборки объекты определяются не как наборы частиц в пространстве, а по их возможной истории формирования. Для вычисления сложности объекта его рекурсивно делят на составляющие части, определяя «пространство сборки» этого объекта как путь, по которому данный объект может быть собран из его элементарных частей.
«Индекс сборки» определяется как минимальное количество шагов, необходимых для сборки объекта из элементарных частей и объектов, которые могли существовать в прошлом и, таким образом, вошли в набор сборок. В случае этого кратчайшего пути пространство сборки соответствует минимальной памяти, то есть минимальному количеству операций, необходимых для сборки данного объекта. Независимо от количества элементарных частей, минимальный индекс сборки объекта, состоящего из таких частей, определяется кратчайшей цепочкой сложения (последовательности OEIS A003313). Максимальный индекс сборки зависит от числа элементарных частей . Более того, определение индекса сборки является NP-полной задачей .
«Пространство сборки» можно определить как ориентированный ациклический граф последовательностей, где все последовательности единичной длины (элементарные части) являются недоступными исходными вершинами, а оставшиеся последовательности — вершинами второй степени, соответствующими этапам сборки. Вершины индексируются независимо от несомых ими строк, поэтому две различные вершины могут нести одну и ту же строку, если они имеют разные истории образования.
Понятие пространства сборки можно расширить до совместного пространства сборки, в котором одновременно собираются ансамбли объектов. Выделены три неэквивалентных совместных пространства сборки: единично оптимальное, в котором каждая цель собрана оптимально и каждая строка встречается один раз; кратностно оптимальное, в котором каждая цель собрана оптимально, но одну и ту же строку могут нести несколько вершин с различными историями образования; и коллективно оптимальное, минимизирующее размер всего пространства даже ценой сборки какой-либо цели неоптимальным планом. Коллективно оптимальное пространство не больше кратностно оптимального, а то — не больше единично оптимального, причём все три размера могут различаться. Задачи распознавания для этих трёх величин имеют различную сложность: для коллективно оптимального пространства задача NP-полна, а для двух остальных NP-трудна, причём её принадлежность классу NP остаётся открытой. Пространству сборки можно также сопоставить дискретную энергию Дирихле, причём индекс сборки, глубина пути и энергия Дирихле взаимно независимы.
Сборка
,
определяется как полный отбор (наложенный механизмом, основанным на информации, например, биологическим или технологическим отбором), необходимый для создания сборки, содержащей объектов, из которых являются уникальными объектами, где объекты типа встречаются раз и имеют индекс сборки .
Например, слово "абракадабра" содержит пять уникальных букв (а, б, р, к, д) и состоит из одиннадцати букв. Из её компонентов её можно собрать следующим образом: а+б --> аб + р --> абр + а --> абра + к --> абрак + а --> абрака + д --> абракад + абра --> абракадабра, что требует семи шагов, поскольку "абра" уже была собрана на предыдущем шаге. Похожая строка, "абракадрбаа", той же длины, не содержит повторений, поэтому её индекс сборки равен 10.
Например, две двоичные строки и имеют одинаковую длину бит и одинаковую энтропию . Однако индекс сборки последовательности и ((1.) составляет "01", вставляя его в набор сборки, (2.) объединяет "01" с "01" из набора сборки, вставляя "0101" в набор сборки, и (3.) объединяет "0101", составленный на втором шаге, с "0101", взятым из набора сборки), в то время как индекс сборки последовательности и , поскольку повторно может быть использован только "01" из набора сборки.
Примечания
Категория:Теория графов Категория:Теория сложных систем Категория:Междисциплинарные науки