Skip to Main content Skip to Navigation
Conference papers

On the Complexity of Quadratization for Polynomial Differential Equations

Abstract : 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.
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : François Fages <>
Submitted on : Thursday, July 23, 2020 - 3:40:26 PM
Last modification on : Friday, April 30, 2021 - 9:52:17 AM


Files produced by the author(s)


  • HAL Id : hal-02900798, version 2
  • ARXIV : 2007.08910



Mathieu Hemery, François Fages, Sylvain Soliman. On the Complexity of Quadratization for Polynomial Differential Equations. CMSB 2020 - 18th International Conference on Computational Methods in Systems Biology, Sep 2020, Konstanz / Online, Germany. ⟨hal-02900798v2⟩



Record views


Files downloads