Minimum autocatalytic networks cannot be approximated within any constant factor

A reflexively autocatalytic and food-generated set (RAF) is a nonempty set of reactions in a catalytic reaction system whose reactants can all be built up from a designated food set and each of whose reactions is catalysed by a food molecule or by a product of the set. Steel, Hordijk and Smith (J. Theor. Biol., 2013) proved that finding a RAF of minimum size is NP-hard and asked whether the smallest RAF can be approximated in polynomial time within a constant factor of optimal. We answer this question negatively for general finite catalytic reaction systems: unless $\mathsf{P}=\mathsf{NP}$, no polynomial-time algorithm returns, on every system that contains a RAF, a RAF whose size is within any fixed constant factor of the minimum. The proof is an approximation-preserving reduction from SET COVER. For an instance with $m$ elements and $n$ sets and an amplification parameter $M\ge 1$, we construct a system with one food molecule and $m+nM$ reactions, each with at most two reactants and exactly one product, and prove an exact structural theorem: its RAFs are precisely the sets $\mathcal{R}(D)$ indexed by the set covers $D$, and $|\mathcal{R}(D)|=m+M|D|$. With $M\ge m$, a RAF within factor $c$ of optimal decodes in linear time to a cover within factor $2c-1$ of optimal, so the reduction is an AP-reduction with constant $2$. The same construction shows that estimating the minimum RAF size, even without producing a RAF, is NP-hard within any constant factor, that irreducible RAFs of the constructed systems are exactly the inclusion-minimal covers, and that a single system can contain two irreducible RAFs whose sizes differ by an arbitrarily large factor. The structural theorem, the objective identity, the decoding arithmetic and the conditional hardness transfer have been formalized and checked in the Lean 4 proof assistant with warnings promoted to errors.