  Chemical reaction networks (CRNs) are a standard formalism used in chemistry
and biology to reason about the dynamics of molecular interaction networks. In
their interpretation by ordinary differential equations, CRNs provide a
Turing-complete model of analog computattion, in the sense that any computable
function over the reals can be computed by a finite number of molecular species
with a continuous CRN which approximates the result of that function in one of
its components in arbitrary precision. The proof of that result is based on a
previous result of Bournez et al. on the Turing-completeness of polyno-mial
ordinary differential equations with polynomial initial conditions (PIVP). It
uses an encoding of real variables by two non-negative variables for
concentrations, and a transformation to an equivalent quadratic PIVP (i.e. with
degrees at most 2) for restricting ourselves to at most bimolecular reactions.
In this paper, we study the theoretical and practical complexities of the
quadratic transformation. We show that both problems of minimizing either the
number of variables (i.e., molecular species) or the number of monomials (i.e.
elementary reactions) in a quadratic transformation of a PIVP are NP-hard. We
present an encoding of those problems in MAX-SAT and show the practical
complexity of this algorithm on a benchmark of quadratization problems inspired
from CRN design problems.
