{"id":"hexagon/2610.00390","pdf":"https://hexagonmath.org/pdf/2610.00390v1","url":"https://hexagonmath.org/abs/2610.00390v1","tags":["math.CO","msc:68Q17","msc:92C42","Lean formalization","NP-completeness","autocatalytic cores","binary encoding","polynomial-time reductions","reaction networks"],"score":0,"title":"Unconstrained detection of productive autocatalytic cores is NP-complete","domain":"cs.CC","origin":"ai-generated","source":"hexagon","authors":["Michael Mislan"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-20","reactions":{},"withdrawn":false,"authorship":"no-human-author-claimed","formalized":true,"formalizations":["https://palomar-registry.org/entry?id=PALOMAR-2026-09-30-000027&version=1"],"human_understanding":"some"}