Fundacja Naukowa im. O. Włodzimierza Zatorskiego OSB

Assembly Theory (AT)

  • 1

    ASI provides supreme compression by exploiting global combinatorial patterns.

  • 2

    NP-Completeness of the ASI problem

    Computing ASI is NP-complete, which follows from an explicit correspondence between assembly plans and straight-line grammars.

  • 3

    The assembly space is an acyclic, 2-in-regular digraph of strings, where edges preserve the commutativity of an assembly step and define the order of strings concatenation.

  • 4

    The ASI is bounded from below by the length of the shortest addition chain (OEIS A003313). A string of four symbols is the shortest one that can have two distinct ASIs depending on the symbols arrangement . This links AT with the Bekenstein entropy.

The minimum number of steps to construct a string by concatenating basic symbols and previously assembled strings.

assembly index (ASI)

ASD(Ck) := max(ASD(Cl), ASD(Cm))+1

where Cl and Cm are the substrings of the last assembly step for Ck, and the ASD of the basic symbols is zero.

assembly depth (ASD)

 

Assembly theory (AT) measures the structural complexity of an object (a string) by the minimum number of steps required to construct it in an assembly space, where each assembly step concatenates two (not necessarily distinct) strings previously assembled. The assembly index is the minimum number of such steps. AT does not introduce a new physics; it defines an object as the history of its formation.