{"id":"palomar/PALOMAR-2026-09-30-000027","url":"https://github.com/mmislan/palomar-p081-productive-core-np-completeness/tree/9a4508c8643310033182b18e1f348f5d786f7c28","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-09-30-000027-v1.json","repo":"https://github.com/mmislan/palomar-p081-productive-core-np-completeness","tags":["cs.CC","q-bio.MN","msc:68Q17","msc:92C42","computational-complexity","reaction-networks","autocatalysis"],"score":0,"title":"Unconstrained detection of productive autocatalytic cores is NP-complete","trust":"high","domain":"cs.CC","source":"palomar","authors":["Michael Mislan"],"reviews":0,"subject":"cs.CC","summary":"Kosc, Kuperberg, Rajon and Charlat (PNAS 122, e2421274122, 2025, Section 2.1) left open the complexity of detecting an autocatalytic core without a prescribed target species or allowed-food set. For finite reversible reaction networks with literal nonnegative integer reactant and product matrices, this unconstrained detection problem is proved NP-complete. A core is a nonempty entity/reaction pair, minimal under componentwise inclusion, with a selected reactant and product in every selected reaction and a signed real flow that strictly produces every selected entity. The input uses a…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"verified":true,"discussed":0,"published":"2026-09-30","reactions":{},"formalized":true,"formalizes":[{"title":"Unconstrained detection of productive autocatalytic cores is NP-complete","identifier":"","relationship":"formalizes"}]}