Assembly index calculation shown to be NP-complete
A new paper involving the Cronin group analyses assembly theory in the context of computational complexity, clarifying how the assembly index differs formally from common information and compression measures. The work presents counterexamples showing that assembly index is not equivalent to Huffman coding, Shannon entropy, or Lempel Ziv style compression, and demonstrates that computing the assembly index for a class of string assembly problems is NP-complete. The paper also discusses why these computational properties do not undermine the intended role of assembly index as a physically grounded, measurable quantity for characterising evolved complexity and supporting life detection metrology.
Full article available here