Open Research Index

Unconstrained detection of productive autocatalytic cores is NP-complete

Michael Mislan

Palomar Registrypalomar/PALOMAR-2026-09-30-000027Sep 30, 2026cs.CCscore 0

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…

SourceRepositoryJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/palomar/PALOMAR-2026-09-30-000027
curl -X POST /api/v1/records/palomar/PALOMAR-2026-09-30-000027/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/palomar/PALOMAR-2026-09-30-000027/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'