pith. sign in

arxiv: 2604.16302 · v1 · submitted 2026-01-23 · 💻 cs.CC

Computational Complexity of Determining the Assembly Index

Piotr Masierak This is my paper

Pith reviewed 2026-05-16 11:55 UTC · model grok-4.3

classification 💻 cs.CC
keywords assembly indexNP-completenessstraight-line grammarssmallest grammar problemcomputational complexityassembly theoryoptimization hardness
0
0 comments X

The pith

Determining an object's assembly index is NP-complete by direct reduction to the smallest straight-line grammar problem.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that deciding whether an object has assembly index at most k is NP-complete. It does so by constructing an explicit, bidirectional mapping between any valid assembly plan and a straight-line grammar that generates the object's string representation. Because the smallest grammar problem is already known to be NP-hard and APX-hard, the same hardness immediately carries over to both the decision and optimization versions of the assembly index. A sympathetic reader cares because assembly theory is now being applied to chemical and biological objects; if the index cannot be computed efficiently, then claims about an object's complexity rest on intractable calculations.

Core claim

The study shows that the decision version of the assembly index problem is NP-complete through an explicit correspondence between assembly plans and straight-line grammars. This correspondence implies that the optimization version inherits NP- and APX-hardness from the classical smallest grammar problem. Complete, self-contained proofs are supplied for both variants.

What carries the argument

The explicit, sound-and-complete correspondence between assembly plans and straight-line grammars that equates the minimal number of assembly steps to the size of the smallest grammar generating the object's description.

If this is right

  • The decision problem of whether the assembly index is at most k is NP-complete.
  • Finding the exact assembly index is NP-hard.
  • Finding an approximation to the assembly index within any constant factor is APX-hard.
  • Any practical algorithm for the assembly index on general objects must therefore be heuristic or exponential in the worst case.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • In domains that apply assembly theory to molecules or organisms, exact indices will remain unavailable for all but the smallest objects, forcing reliance on proxies.
  • The reduction opens the door to importing approximation algorithms and parameterized-tractability results already developed for grammar compression.
  • Restrictions on object shape or component repertoire might render the problem fixed-parameter tractable; testing this would require only a modest extension of the existing proof.

Load-bearing premise

The mapping between assembly plans and straight-line grammars must be both sound and complete for the precise definition of assembly index used in the paper.

What would settle it

A polynomial-time algorithm that, for any finite object, outputs its exact assembly index would immediately falsify the NP-completeness claim.

read the original abstract

The assembly index of assembly theory quantifies the minimal number of composition steps required to construct an object from elementary components. The study proves that the decision version of the assembly index problem is NP-complete, through an explicit correspondence between assembly plans and straight-line grammars. This correspondence implies that the optimization version of the assembly index problem inherits NP- and APX-hardness from the classical smallest grammar problem. The study provides complete, self-contained proofs for both decision and optimization variants of the assembly index problem. These results establish that computing or approximating the assembly index is computationally intractable, placing it within the same complexity class as grammar-based compression.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper proves that the decision version of the assembly index problem is NP-complete via an explicit correspondence between valid assembly plans and straight-line grammars, reducing from the smallest-grammar problem. The optimization version inherits NP-hardness and APX-hardness from the same reduction. Complete self-contained proofs are supplied for both variants.

Significance. If the claimed bijection holds under the paper's definitions, the result places assembly-index computation in the same complexity class as grammar-based compression. The self-contained proofs and direct reduction from a known APX-hard problem are strengths that make the intractability claim falsifiable and reproducible.

minor comments (2)
  1. [Abstract] The abstract states that the optimization version inherits both NP- and APX-hardness; a brief sentence in §4 or the conclusion confirming the approximation-preserving nature of the reduction would help readers locate this inheritance without re-deriving it.
  2. [§3] Notation for assembly plans (sequences of composition steps) and grammar size should be aligned more explicitly in the statement of the main theorem to avoid any ambiguity about what quantity is being minimized.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive review and recommendation to accept the manuscript. We appreciate the recognition that the proofs are self-contained and that the direct reduction from the smallest-grammar problem makes the intractability claim clear and reproducible.

Circularity Check

0 steps flagged

Direct reduction to smallest-grammar problem via explicit bijection; self-contained proofs

full rationale

The paper establishes NP-completeness of the decision version of the assembly-index problem by exhibiting an explicit correspondence between assembly plans and straight-line grammars, then inherits NP- and APX-hardness from the classical smallest-grammar problem. It states that complete, self-contained proofs are supplied for both decision and optimization variants. No equation or definition equates the assembly index to itself by construction, no parameter is fitted to a subset and then relabeled as a prediction, and no load-bearing step rests on a self-citation chain that itself assumes the target result. The claimed bijection is presented as an independent mapping rather than a renaming or self-definition, placing the work in the standard category of complexity reductions with no enumerated circularity pattern.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the standard definition of NP-completeness and the known NP-completeness of the smallest straight-line grammar problem; no free parameters, ad-hoc constants, or new postulated entities are introduced.

axioms (2)
  • standard math The decision version of the smallest straight-line grammar problem is NP-complete (standard result in complexity theory).
    Invoked to transfer hardness via the explicit correspondence.
  • domain assumption The mapping between assembly plans and straight-line grammars is bijective and preserves minimality.
    This is the load-bearing step stated in the abstract; if the mapping is incomplete or inexact the reduction fails.

pith-pipeline@v0.9.0 · 5385 in / 1355 out tokens · 40342 ms · 2026-05-16T11:55:53.488687+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

  1. [1]

    A probabilistic framework for identifying biosig- natures using Pathway Complexity

    Marshall SM, Murray ARG, Cronin L. A probabilistic framework for identifying biosig- natures using Pathway Complexity. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences. 2017 Dec;375(2109):20160342. Avail- able from:https://royalsocietypublishing.org/doi/10.1098/rsta.2016.0342

    work page doi:10.1098/rsta.2016.0342 2017

  2. [2]

    Formalising the Pathways to Life Using Assembly Spaces

    Marshall SM, Moore DG, Murray ARG, Walker SI, Cronin L. Formalising the Pathways to Life Using Assembly Spaces. Entropy. 2022 Jun;24(7):884. Available from:https: //www.mdpi.com/1099-4300/24/7/884

    work page 2022

  3. [3]

    Assembly the- ory explains and quantifies selection and evolution

    Sharma A, Cz ´egel D, Lachmann M, Kempes CP , Walker SI, Cronin L. Assembly the- ory explains and quantifies selection and evolution. Nature. 2023 Oct;622(7982):321-8. Available from:https://www.nature.com/articles/s41586-023-06600-9

    work page 2023

  4. [4]

    Assembly Theory of Binary Messages

    Łukaszyk S, Bieniawski W. Assembly Theory of Binary Messages. Mathematics. 2024 May;12(10):1600. Available from:https://www.mdpi.com/2227-7390/12/10/1600

    work page 2024

  5. [5]

    Assembly theory and its relationship with computational complexity

    Kempes CP , Lachmann M, Iannaccone A, Matthew Fricke G, Redwan Chowdhury M, Walker SI, et al. Assembly theory and its relationship with computational complexity. npj Complexity. 2025 Sep;2(1):27. Available from:https://www.nature.com/articles/ s44260-025-00049-9

    work page 2025

  6. [6]

    On the ”Assembly Theory and its Relationship with Computational Com- plexity”

    Łukaszyk S. On the ”Assembly Theory and its Relationship with Computational Com- plexity”. IPI Letters. 2025 Jan:1-6. Available from:https://ipipublishing.org/index. php/ipil/article/view/157

    work page 2025

  7. [7]

    The small- est grammar problem

    Charikar M, Lehman E, Liu D, Panigrahy R, Prabhakaran M, Sahai A, et al. The small- est grammar problem. IEEE Transactions on Information Theory. 2005;51(7):2554-76. Available from:https://web.cs.ucla.edu/ ˜sahai/work/web/2005%20Publications/ TransOnInfoTheory2005.pdf

    work page 2005

  8. [8]

    Application of Lempel–Ziv factorization to the approximation of grammar- based compression

    Rytter W. Application of Lempel–Ziv factorization to the approximation of grammar- based compression. Theoretical Computer Science. 2003 Jun;302(1-3):211-22. Available from:https://linkinghub.elsevier.com/retrieve/pii/S0304397502007776

    work page 2003

  9. [9]

    On the Complexity of the Smallest Grammar Problem over Fixed Alphabets

    Casel K, Fernau H, Gaspers S, Gras B, Schmid ML. On the Complexity of the Smallest Grammar Problem over Fixed Alphabets. Theory of Computing Sys- tems. 2021 Feb;65(2):344-409. Available from:http://link.springer.com/10.1007/ s00224-020-10013-w. 12https://ipipublishing.org/index.php/ipil/

    work page 2021