HEXAGONbeta

Unconstrained detection of productive autocatalytic cores is NP-complete

Primarily AI-generated textHuman understanding: some partscs.CC — Computational Complexitymath.CO — Combinatorics

Contributed by Michael Mislan ↗

Version 1 / Oct 20, 2026 / CC BY 4.0

Abstract

We prove NP-completeness of deciding whether a finite reversible reaction network contains a productive autocatalytic core when neither a target species nor an allowed-food set is specified. The input is a binary encoding of literal nonnegative integer reactant and product matrices, with a signed real flow on each reaction identity. A nonsingular square-witness characterization gives polynomial certificates. A weighted incidence construction reduces prescribed two-path directed linkage to unrestricted core detection, and an explicit constant-size switch construction reduces SAT to the linkage instances. Actual machine-level NP membership and a total polynomial-time binary transducer complete the classification. The terminal theorem is verified in Lean 4. The result concerns structural possibility in this source model and imposes no elementary reaction arity or conservation constraint.

Provenance statement

The text is primarily AI-generated. AI systems assisted the mathematical development, computations and Lean formalization under human direction; human understanding covers some parts of the work.

Formalizations

References

  1. T. Kosc, D. Kuperberg, E. Rajon, and S. Charlat. Thermodynamic consistency of autocatalytic cycles. Proceedings of the National Academy of Sciences , 122(18):e2421274122, 2025. doi:10.1073/pnas.2421274122 (https://doi.org/10.1073/pnas.2421274122).DOI
  2. J. L. Andersen, C. Flamm, D. Merkle, and P. F. Stadler. Maximizing output and recognizing autocatalysis in chemical reaction networks is NP-complete. Journal of Systems Chemistry , 3:1, 2012. doi:10.1186/1759-2208-3-1 (https://doi.org/10.1186/1759-2208-3-1).DOI
  3. R. Golnik, T. Gatter, P. F. Stadler, and N. Vassena. Enumeration of autocatalytic subsystems in large chemical reaction networks. Journal of Chemical Theory and Computation , 22(10):4888--4907, 2026. doi:10.1021/acs.jctc.5c01979 (https://doi.org/10.1021/acs.jctc.5c01979).DOI

Version history

  1. v1Submitted by Michael MislanInitial depositCurrentOct 19, 2026