组装理论

马兜铃酸的合成。
复杂化合物的合成需要多个步骤。合成特定化合物所需的步骤越多，其形成过程中发生选择过程（生物或技术选择）的可能性就越大。

组装理论并非将物体的复杂性视为空间中粒子的集合，而是通过其组装历史来表征。应用于化合物复杂性研究时，它是首个可进行实验验证的技术
，这与其他无法验证的算法截然不同。

组装理论由格拉斯哥大学化学家勒罗伊·克罗宁（Leroy Cronin）领导的团队于2017年提出。

在该理论中，物体并非被定义为空间中粒子的集合，而是由其可能的形成历史来定义。为了计算物体的复杂性，需要将其递归地分解为各个组成部分，并将物体的“组装空间”定义为由其组成元素组装而成的路径。

“组装指数”被定义为从组成元素以及过去可能存在并因此被添加到组装池中的物体组装一个物体所需的最小步骤数。对于这样的最短路径，组装空间对应于最小内存，或者组装给定对象所需的最小操作次数。无论组成元素的数量如何，由这些元素组成的对象的最小组装索引由最短加法链（OEIS 序列 A003313 ） 给出。此外，确定组装索引是一个 NP 完全问题。

“组装空间”可以定义为序列的有向无环图，其中所有单位长度序列（组成元素）都是不可访问的源顶点，其余序列是二度顶点，对应于组装步骤。在这个定义中，每个顶点的唯一性是引入组装池概念的充分条件：组装空间中存在的序列无法重新组装，即使通过不同的组装路径也不行，因为它们不再唯一。集合 

，

定义为生成包含  个对象（其中  个是唯一的）的集合所需的全部选择（通过信息机制，例如生物选择或技术选择）。其中，类型  的对象出现  次，且集合索引为 。

例如，字符串“abrakadabra”包含五个唯一的字母（a、b、k、d 和 r），共由十一个字母组成。它可以按如下方式由其组成部分组装：a + b → ab + r → abr + a → abra + k → abrak + a → abraka + d → abrakad + abra → abrakadabra。此组装需要七个步骤，因为“abra”已在前一步中组装完成。长度相同的类似字符串“abrakadrbaa”不包含重复项；因此，其组装索引为 10。

例如，两个二进制字符串  和  具有相同的长度  位，并且具有相同的香农熵 (信息论) 。然而，序列  的组装索引为 （(1) 将“01”插入组装池进行组合；(2) 将“01”与组装池中的“01”组合，方法是将“0101”插入组装池；(3) 将第二步组合的“0101”与组装池中的“0101”组合）。序列  的组装索引为 ，因为只能从组装池中重复使用“01”。

注释

Category:图论
Category:数据压缩
Category:热力学
Category:跨學科領域
Category:复杂系统理论